Matematika | Diszkrét Matematika » Geleji János - Lineáris élszámú gráfok és hipergráfok Ramsey-számairól

http://www.doksihu Lineáris élszámú gráfok és hipergráfok Ramsey-számairól Geleji János 2008. június 5 Diplomamunka Eötvös Loránd Tudományegyetem Természettudományi Kar Témavezet®: Katona Gyula, MTA tag köszönetnyilvánítás: Katona Gyulának a 4. részbeli probléma felvetéséért és sok szakmai tanácsáért a felvetések megoldási módjaival kapcsolatban, Jordán Tibornak a matroidok összegzési problémájának felvetéséért, az 5. fejezet nagy része egy TDK dolgozat amelynek ® a témavezet®je, Hermann Györgynek a 3. fejezethez adott tanácsaiért és egy szerepeltetett probléma megoldását is t®le hallottam, Salát Máténak ábrák készítésében nyújtott segítségéért és ® különben is tipográfus is, Hubai Tamásnak aki megtanított az egyetemi számítógépes rendszer használatára 1 http://www.doksihu Tartalomjegyzék 1. Bevezetés 3 2. Jelölések 4 3. Néhány ismert Ramsey-szám 5 4. Baysa-feladat 8 5.

Lineáris élszámú gráfok halmazainak Ramsey számai 14 5.1 Motiváció . 5.2 Gráfok count matroidjai . 16 5.3 Konstrukció . 22 5.4 Hipergráfok count matroidjai 28 5.5 Hk,m,l típusú gráfhalmazok Ramsey-számainak meghatározása . count matroidok összegzésével . 2 14 31 http://www.doksihu 1. Bevezetés Egy összejövetelen egy társaság tagjai közül néhányan ismerik egymást, néhányan nem. Megkérdezhetjük, mennyi embernek kell összegy¶lnie ah- hoz, hogy biztosan legyen 3 ember akik páronként ismerik egymást, vagy 3 ember akik közül senki senkit nem ismer. Ha már hatan összejöttek, akkor tetsz®leges személynek van legalább 3 ismer®se vagy 3 nem-ismer®se. Ezen legalább három ember között ha kett® ismeretségi státusza megegyezik a kiindulási emberre vonatkozóval, máris megvan a 3 emberünk. Ha az ismeretségi

státusz eltér a 3 ember között a kiindulási embert®l, akkor ®k hárman adják a klikket. Ha csak öt ember gy¶lik össze és mindenkinek 2 ismer®se van úgy, hogy az ismeretségi gráf ötszög, akkor nem lesz hármas klikk sem hármas üres halmaz. Így lesz az R(3, 3) = 6 Ramsey-szám. Ugyanezt a kérdést feltehetjük 3 helyén nagyobb ismeretségi vagy ismeretlenségi klikk létezésére. Adott a síkon N általános helyzet¶ pont, keressünk n pontot közöttük úgy, hogy konvex sokszöget alkossanak. Ez a geometriai hangzású felvetés Ramsey-számos megoldást nyert. Az Erd®s-Szekeres tétel szerint ha N elég nagy, akkor van konvex n-szög. Felveszünk egy irányt vízszintesnek. Tet- sz®leges 3 pontra, amelyek közül a középs® a másik kett® egyenese felett van, rakjunk piros háromszöget, tetsz®leges 3 pontra, amelyek közül a középs® a másik kett® egyenese alatt van, rakjunk kék háromszöget. Ha van n darab pontunk csupa egyszín¶

háromszöggel, máris megvan a konvex n-szög. Ezek és ezekhez hasonló eredmények ösztönözték a korai kutatásokat a Ramsey-elméletben. F P Ramsey 1930-as megjelenés¶ cikke óta ez lett a kombinatorika egyik legjobban kifejlesztett területe, amely messze meghaladta az eredeti indíttatásait. Jelen diplomamunkában a 2. részben bevezetek néhány jelölést amely konzisztens az irodalomban használatossal, kicsit mégis más. A 3 fejezetben áttekintést adok a Ramsey-elmélet egy kis szeletének fejl®désér®l. A 4. részben vizsgált probléma nem tartozik szigorú értelemben a Ramsey-elmélethez, két külön térben választok ki halmazokat. Tekintsünk egy n pontú halmazt. Válasszunk ki néhány k és néhány k −1 elem¶ halmazt 3 http://www.doksihu úgy, hogy ne tartalmazzák egymást, ne legyen u pont kiválasztott k -as nélkül és ne legyen v pont kiválasztott (k − 1)-es nélkül. Azt fogjuk megmutatni, hogy ha n elég nagy, akkor ezt nem

lehet megtenni. Az 5. rész a korábbiaktól teljesen független, a TDK dolgozatomban, más indítékkal felvetett kérdésre adott választ használom egy Ramsey-elméletre emlékeztet® kérdésfeltevés alsó korlátjának. Hogy ugyanez a szám fels® korlát is, az könnyen látható. 2. Jelölések Legyen Tn az n pontú fa gráfok halmaza. Kt a t pontú teljes gráf, Ktu az u uniform teljes t pontú hipergráf. Ha a fels® indexet nem tüntetem fel, akkor 2 értend®, vagy ami a környezetben egyértelm¶. Legyen Kt − e az a gráf amelyet Kt egy élének elhagyása eredményez Majdnem teljes gráfnak fogom nevezni. Km,n a teljes páros gráf melynek osztályai m, n pontúak, nyilván Ki,1 az i + 1 pontú csillag. Pi az i pontú út, Ci az i pontú kör. Legyen Si az i pontú kett®scsillag gráfok halmaza, amelyet két, külön-külön nem megkötött pontszámú szokásos csillag középpontjának összekötése ad. Legyen H1 , H2 , . gráfok illetve közös k -ra

uniform hipergráfok (akár egyelem¶) halmazai. Ekkor Rk (H1 , H2 , . Ht ; t) legyen a legkisebb pozitív egész, melyre az ilyen pontszámú teljes gráf vagy k uniform hipergráf éleit t színnel színezve valamely i-hez lesz az i. színosztályban Hi -beli (hiper)gráf Ha nem írom ki k -t vagy t-t, akkor 2-nek értend®. Ha Hi helyébe egyetlen gráfot írok, akkor az ®t tartalmazó egyelem¶ halmaz, értelemszer¶en, ha egy s pozitív egészt írok, akkor értsük {Ks2 }-nek. Rk (H1 , H2 , . Ht ; t) valamely H1 , Ht k uniform hipergráfcsaládok esetén a legkisebb n amelyre az n pontú teljes k uniform hipergráf hiperéleit t színnel színezve valamely i-re az i-edik színosztályban lesz Hi -beli hipergráf (Nem feltétlenül feszített). Hk,m,l azon részgráfképzésre nézve minimális k uniform hipergráfok, 4 http://www.doksihu amely V (G) csúcshalmazára és E(G) élhalmazára teljesül |E(G)| = m|V (G)| + l. Az iménti jelölésekkel H3 ⊂ H2

esetén Rk (H1 , H2 ) ≤ Rk (H1 , H3 ) és ha H3 úgy kapható H2 -b®l, hogy néhány eleméhez (hiper)éleket adunk, akkor is Rk (H1 , H2 ) ≤ Rk (H1 , H3 ) teljesül, egyszer¶en azért mert egy Rk (H1 , H2 ) − 1 pontú egyik problémára jó konstrukció megengedett lesz a másik feladatra is. 3. Néhány ismert Ramsey-szám A Ramsey számokat a harmincas évek óta kutatják, kevés pontos szám ismert és sok cikkben vannak az eredmények szétosztva. A kutatott mennyiségek skálája jóval szélesebb, mint amivel itt foglalkozom Ebben a diplomamunkában csak olyan kérdéseket vizsgálok, ahol egy teljes gráf vagy teljes uniform hipergráf él illetve hiperélhalmazát partícionáljuk és a partíció osztályaiban keresünk tiltott részgráfokat. Az ismert értékek felkutatásában nagy segítség volt egy [6] erre a célra készített összefoglaló. Nem célom az összes ismert eredmény felsorolása, csak a kés®bbiek szempontjából érdekes és a valamiért

tetszet®s eredményeket írom ki. Alapesetben R(k, l)-et vizsgáljuk R(k, l) mindig létezik és véges, könnyen látható rekurzió R(k, l) ≤ R(k − 1, l) + R(k, l − 1) ugyanis egy pontot lerögzítve az ® kék és piros szomszédai között eggyel kisebb megfelel® szín¶ teljes gráf kiegészül megfelel® méret¶re. Ebb®l adódik  R(k, l) ≤  k+l−2 . k−1 Régóta ismert alsó becslés [7] k c · 2 2 ≤ R(k, k). 5 http://www.doksihu A következ® táblázatban R(k, l) néhány ismert értékét tüntetem fel. A bent lev® törtek számlálója a legjobb ismert alsó korlát, nevez®je a legjobb ismert fels® korlát, ha ezek különböz®k. k 3 4 5 6 7 8 9 6 9 14 18 23 28 36 25 35 41 58 87 102 165 49 61 80 143 113 298 205 540 56 84 101 216 127 495 216 1031 282 1870 73 115 125 316 169 780 233 1713 317 3583 565 6588 l 3 4 18 43 49 5 6 7 8 9 Két színnél maradva további sokat vizsgált kérdés bizonyos gráfok, gráfpárokhoz

tartozó legkisebb csúcsszám, amely esetén G vagy komplementere tartalmazza a pár megfelel® elemét. A jelölések részben feltüntetett gráfok párosításait sokat vizsgálták, úgymint teljes és majdnem teljes gráfok egymás ellen, majdnem teljes gráfok egymás közt, teljes páros gráfok egymás közt. Ebbe a legutóbbiba beleér- tend® a csillagok teljes páros gráfok ellen és a csillagok egymás közt kérdései is. R(K1,n , K1,m ) = n + m − ε ahol ε értéke 1, ha n és m egyaránt párosak, egyébként 0. Végtelen sok n-re R(K2,n , K2,n ) = 4n − 2 teljesül [1] Az R(G, H) Ramsey-szám már ismert minden legfeljebb 5 csúcsú G és H esetén kivéve 3 esetet: R(K5 , K5 ), R(K5 , K5 − e), R(K5 , K5 − P3 ) Magasabb k -ra uniform teljes hipergráfok Ramsey-számainál a következ® rekurzió érvényes: Rk (m, l) ≤ Rk−1 (Rk (m − 1, l), Rk (m, l − 1)) Ebb®l Rk (m, l) értékére egy k magasságú torony adódik [12] és létezik torony

nagyságú konstrukció nagy teljes vagy üres rész nélkül. Erd®s megjegyzése, hogy egy gráf vagy a komplementere összefügg®, az én jelölésemmel R(Tn , Tn ) = n. Szintén az összes fa tiltása mellett r szín 6 http://www.doksihu használatánál (r − 1)n ponton már nem tudunk jólszínezni [4]. Tetsz®leges rögzített fa esetén tehát valamely Tn ∈ Tn -re a k szín¶ R(Tn , Tn , . , Tn ; k) nem ismert k = 2 esetben sem Ismert azonban [5], p k(k − 1) ) + 2. Ekkora hogy a k szín¶ R(Tn , Tn , . , Tn ; k) ≤ (n − 1)(k + pontszám esetén azonban már ugyanazon gráf egyik színosztályában megvan az összes n pontú fa. Pontos érték ismert tetsz®leges rögzített T ∈ Tn esetén R(T, Km )-re [11]. Ha a kék élek osztályában tiltjuk a konkrét fát és a liláknál a teljes gráfot, akkor tekintsük a liláknál az m − 1 osztályú, összesen (n − 1)(m − 1) pontú Turán gráfot. A komplementer élei legyenek kékek Ez jó konstrukció,

ráadásul a pontszáma a lehet® legnagyobb A következ® konstrukciót adhatjuk. Legyenek T1 ⊂ T2 ⊂ ⊂ Tn egymásba skatulyázott fák sorozata ahol Ti pontszáma i. Értelemszer¶en Ti -hez megfelel® helyen levelet hoz- záadva kaphatjuk Ti+1 -et. Teljes indukció m-re. Az m = 2 eset triviális. Indirekt bizonyítás, tegyük fel, hogy (n − 1)(m − 1) + 1 pontunk van, az élek kiszínezve kékre és lilára, de nincs sem kék Tn sem lila Km . Legyen a sorozat szerinti legnagyobb kék fa amit megtalálunk a gráfban Ti . T1 biztos van. Rögzítsük le Ti egy el®fordulását Ebben van egy pont, ahol kék levél ragasztása Ti+1 -et adna, tehát ennek a pontnak minden kék szomszédja a Ti rögzített el®fordulásában van, tehát a lila szomszédainak halmaza legalább (n − 1)(m − 1) − i ≥ (n − 1)(m − 2) + 1 pontú tehát az indukciós feltevés miatt van benne lila Km−1 vagy kék Tn . A lila teljes gráfot pedig ki tudjuk egészíteni azzal a

ponttal, ahol a kék Ti illeszkedési pontja van. Különböz® színszámú Ramsey-számok között kapcsolatot teremthetünk: Rk (H1 , H2 , H3 ; 3) ≤ Rk (KRk (H1 ,H2 ) , H3 ; 2) Egyszer¶en az els® két színosztály összevonása igazolja ezt az állítást. Ezt és a fa versus teljes gráf Ramsey-számot felhasználva kétszín¶ klasszikus (teljes gráfos) Ramsey-számokra becslést kaphatunk egy fákat felvonultató, háromszín¶ Ramsey-számon keresztül. R(K(l−1)(m−1)+1 , Kn ) ≥ R(Tl , Km , Kn ) 7 http://www.doksihu Észrevehetjük továbbá, hogy az R(Km , Tn ) számos bizonyítás kicsit általánosabban is alkalmazható. R(Tl , Km , Kn ) ≥ (R(Km , Kn ) − 1)(l − 1) + 1 Ezt úgy tudjuk bizonyítani, hogy veszünk egy R(Km , Kn ) − 1 pontú konstrukciót kék és sárga színekkel kék Km és sárga Kn nélkül. Ennek minden csúcsa helyére befújunk egy l − 1 pontú zöld teljes gráfot, az új élek öröklik a megfelel® sárga és kék

élszíneket. Számoljuk össze a pontokat és vegyük észre, hogy nincs zöld l pontú fa, sem kék Km sem sárga Kn . Ezek érdekes speciális esete az l = 3, vagyis R(2m − 1, n) ≥ 2R(m, n) − 1 Ezt az okoskodást Hermann Györgyt®l hallottam. Ez a becslés csak lineáris, mégis sok esetben az ismert legjobb alsó becslést nyerhetjük vele. Egyforma n pontú utakra [2] ismert 2 színnél b 3n−2 c, 3 színnél 2n − 1 2 illetve 2n aszerint [3], hogy n páratlan vagy páros. R(Sn , Sn ) értéke konstans hibától eltekintve 4n 3 4. Baysa-feladat A feladat neve onnan ered, hogy egy mongol hallgató gondolkozott el®ször a problémán, az ® neve Balkhu Batbayasgalan, ezt idézi a mostani elnevezés. Rögzítsünk k, u, v paramétereket. Az alaphalmazon válasszunk ki néhány k és néhány k − 1 elem¶ részhalmazt úgy, hogy az alábbi három dolgot elkerüljük: (i) u pont úgy, hogy nem tartalmaznak egyetlen kiválasztott k -ast sem, (ii) v pont úgy,

hogy nem tartalmaznak egyetlen kiválasztott (k − 1)-est sem, (iii) Egy kiválasztott k -as tartalmaz egy kiválasztott (k − 1)-est. 8 http://www.doksihu A legkisebb egészt, amekkora alaphalmazon ezt nem lehet megtenni, jelölje Hk (u, v). Feltehet®, hogy k ≤ u, v 1. TÉTEL Hk (u, v) véges Bizonyítás. H k,u jelentse az olyan u pontú k − 1 uniform hipergráfok halmazát, ahol bármely k ponthoz van ®t részhalmazként lefogó hiperél. Egy Baysa-konstrukcióban a k − 1 pontú halmazok között nem lehet H k,u -beli részhipergráf, mert annak u pontján csak tartalmazással lehetne kiválasztott k -as, pedig nincs az üres u-as a k -asok között. Ha viszont nincs ilyen, akkor az összes k -as, aminek nem választottuk ki részhalmazát, jól egészíti ki a v konstrukciót. Hk jelölje azon v pontú k uniform hipergráfok halmazát, ahol minden k − 1 pontú részhalmazt tartalmaz valamely hiperél. Az el®bbihez v hasonlóan a k -asok között nem lehet

Hk -beli részhipergráf mert ennek a v pontján csak tartalmazással lehetne kiválasztott (k − 1)-es, ha pedig nincs, akkor üres v -esünk van a (k − 1)-esek között. Ezenkívül felhasználjuk, hogy egy Ramsey-szám fels® becslésének tekinthetjük, ha a tiltott hipergráf helyett egy ®t részgráfként tartalmazó hipergráfot tiltunk meg, valamint ha a tiltott gráfok halmazának egy részhalmazát vesszük. Hk (u, v) = Rk−1 (Kv , H k,u ) = Rk (Hkv , Ku ) ≤ Rk (Kv , Ku )  Ez alapján kijelenthet®, hogy Hk (u, v) ≤ tk (max{u, v}) ahol tk (x) a k magasságú 2-esekb®l álló torony függvény a legtetején x-szel megtoldva. Néhány esetben Hk (m, l)-et könny¶ megadni. Hk (k, v) = v , Hk (u, k) = u Egyszer¶ eset még k = 2, ekkor néhány élt és néhány csúcsot kell kiválasztani. Legfeljebb v − 1 darab nem kiválasztott csúcs lehet. A nem kiválasztott csúcsokon feltehet®, hogy az összes él ki van választva. A kiválasztott élek ekkor klikket

alkotnak, rajta kívül legfeljebb u−1 csúcs van, tehát H2 (u, v) = u + v − 1. A következ® esetekben arról van szó, hogy H gyelembevéve tudunk fels® becslést adni. 9 k,u elemei közül csak egyet http://www.doksihu k = 3 eset: háromszögeket és éleket választunk ki. H 3,u elemei egyszer¶ gráfok. u = 4 alesetben nem fordulhat el® két diszjunkt él, ezért a kiválasztott élek gráfja háromszög vagy csillag lehet. Háromszög esetén a háromszög pontjaihoz negyedik pont már nem választható, mert erre a négy pontra nem választható háromszög. Csillag alapján adható konstrukcióban a csillag középpontjától különböz® csúcsok már nem feszítenek élt ezért legfeljebb v − 1 darab van bel®lük tehát legfeljebb összesen v pontunk lehet, vagyis H3 (4, v) = v + 1. k = 3, u = 5-nél a gráfban nem fordulhat el® háromszög és t®le diszjunkt él, mert erre az 5 pontra nem férne háromszög. 1. eset: az élek gráfjában van

háromszög Ekkor minden további élnek van közös csúcsa a háromszöggel. A háromszögön kívüli csúcsoknak legfeljebb 2 élszomszédja lehet a háromszögben, különben K4 lenne ami láthatóan 10 http://www.doksihu nem lehet. A háromszögön kívüli csúcsok száma legfeljebb v − 1 mert ®k nem feszíthetnek élt, vagyis a háromszöges konstrukció pontszáma legfeljebb v + 2. 2. eset ha nincs háromszög Ekkor a pontszám legfeljebb  H3 (5, v) ≤ R2 (3, v) ≤  3+v−2 v(v + 1) . = 2 2 k = 3, u = 6-nál a gráfban nem fordulhat el® két diszjunkt háromszög, ezért  H3 (6, v) ≤ R2 (3, v) + 3 ≤  3+v−2 v(v + 1) +3= + 3. 2 2 Ilyen módszerrel általában kijelenthet®, hogy 2. LEMMA  juk ,v + . 2 2 u
u , v + 2 pontú Baysa-feladatra Tekintsünk egy R2 2 H3 (u, v) ≤ R2 Bizonyítás. adott konstrukciót. l u m Színezzük ugyanekkora ponthalmazon a teljes gráfot két színnel kékre színezve az éleit, lilára a neméleket. jes

gráf u 2 Van benne kék tel- pontú, vagy van lila Kv . Ha benne van a kék dolog, akkor a többi pont gráfja még mindig elég nagy, hogy legyen benne kék teljes u 2 vagy lila teljes v , mindkét esetben készen vagyunk ugyanis a kék teljes gráfpár üres a konstrukció szerinti háromszögekben, a lila dolog üres az élek között. Általában a H3 (u, v) próbáljuk meghatározni. kiszámolásához javasolt H 3,u halmaz  elemeit Nevezzünk egy hipergráfot lefogónak, ha minden k pontú csúcshalmazán van k − 1 pontú hiperél. k = 3 esetén van egy típusa ezeknek amelyek két diszjunkt teljes gráfból tev®dnek össze, a fenti esetekben mindig ezek közül a középs®t vettük gyelembe. Tetsz®leges hipergráfnak egy k −1 pontú hiperélét nevezzük kritikusnak, ha van olyan k pontú csúcshalmaz, amelyben ® az egyetlen hiperél. akkor van H k,u Egy hipergráf akkor és csak -ban, ha lefogó és minden hiperéle kritikus. H 3,u -beli

gráfok- nak minden csúcshármasán van legalább egy él és mivel élelhagyásra nézve minimális gráfjaink vannak, ezért itt minden élhez van tanúháromszög, mely 11 http://www.doksihu szerint ® kritikus. H 3,u−1 -beli gráfból kaphatunk olyan gráfot, amelynek részgráfja(vagy egyenl® vele, ha szerencsénk van) valamely H 3,u -beli gráf a következ®képpen: vegyünk egy új csúcsot és néhány pont kivételével vegyük fel az összes rá illeszked® élt. A néhány régit, akihez nem kötöttük hozzá, ha nem voltak eddig is egymás szomszédai, kössük össze éllel, hogy klikket alkossanak. Könnyen látható, hogy ilyen módon lefogó gráfot kaptunk, amelynek lehetnek nem kritikus élei Ha a kapott klikk tartalmazásra maximális klikk, akkor a kapott gráf minden hiperéle kritikus, vagyis H Adódik a kérdés: minden H ból ilyen módon? Egy k,u 3,u -beli gráfot megkaphatunk H -ban vagyunk. k,u−1 -beli gráf- u pontú lefogó

hipergráf egy csúcsát elhagyva is- mét lefogó hipergráfhoz jutunk. Az nem igaz, hogy egy H egy csúcsának elhagyása mindig H k,u−1 k,u -beli hipergráf -beli hipergráfot ad, a kritikusságot tanúsító háromszögeknek kihagyhatjuk a csúcsait. Egy H 3,u -beli gráfban egy tetsz®leges csúcs nemszomszédai klikket alkotnak. A klikk néhány élét elhagyva a maradék gráf minden éle kritikus, ugyanis a klikken kívüli élek tanúháromszöge nem tartalmazhatja az új csúcsot, lévén, hogy a klikken kívüli él egyik végpontja az új csúcsnak szomszédja. belit megkaphatunk ily módon H 3,u−1 Tehát minden H 3,u - -beli gráfból. Sajnos a klikkberajzolást nem mindig lehet megúszni, H 3,4 -ben csak 2 komponens¶ gráfok vannak, a 2 diszjunkt él és a háromszög plusz egy ponttal, míg H 3,5 -ben szerepel a C5 ötszög is, ami 2-összefügg® tehát nem kapható meg egy 2 komponens¶ gráfból egy új csúcs és az új csúcsra illeszked®

élek felvételével. Ha a berajzolt klikk része lesz egy nagyobb klikknek, akkor a nagyobb klikk csúcsait felesleges összekötni az új csúccsal. 3. TÉTEL Valamely k-tól függ®, u-tól és v-t®l független r > 1 és c > 0 konstansokkal Hk (u, v) ≥ rc·(min{u,v}) k−2 . Bizonyítás. Legyenek p+q = 1 pozitív valós számok, tekintsük a Gk−1 (n, p) véletlen hipergráfot, azaz minden k − 1 pontú halmazt egymástól függetlenül p valószín¶séggel választok ki. 12 http://www.doksihu v p(egy rögzített v pontú halmaz üres) = q (k−1) A kitev®ben szerepl® darabszámú hiperélnek kell nem kiválasztva lenni. Ezek hiperélenként független események. p(egy rögzített u pontú halmaz minden k -asa le van fogva) ≤ Az egyik esemény maga után vonja a másikat. ≤ p(egy rögzített u pontú halmazon egy független k -asokból álló rendszer minden eleme le van fogva) = = p(egy k -as le van fogva)a ≤ Ugyanúgy, mint el®bb, az száma, a

kitev® a független k -asokból álló rendszer elem- (k−1)u u ponton k ponton, az összes (k − 1)-esre rakhatok k -ast és a maradék k válogathatok k -adik csúcsokat hozzájuk úgy, hogy a k -asoknak ne legyen közös (k − 1)-esük vagyis függetlenek legyenek. u k ≤ (1 − q k )(k−1) Egy u-asból a lefogott u-asok számának várható értéke a lefogottság valószín¶sége, amit ezidáig becsültünk, hasonlóan van a helyzet az egy üres essel. Ezek alapján a lefogott valamely pozitív v- u-asok és az üres v -esek számának várható értékére c1 , c2 konstansokkal a várható érték additivitása miatt érvényes a következ® becslés:
k−1 n (kv ) q ≤ nv q c1 v v u
k ) k−1 n k (k−1 E(lefogott u-asok) ≤ u (1 − q ) ≤ nu (1 − q k )c2 u E(üres v -esek) ≤ Ha ezeknek a mennyiségeknek az összege kisebb, mint 1 akkor tudjuk, hogy v u van olyan kivitelezés amikor sem üres -es sem lefogott -asunk nincsen. Legyen

c1 v k−2 c2 uk−2 1 1 1 1 √ √ és . Ha értékét növelem akkor a két korlát v u k   n< 2 q  n< 2  q 1−q közül az els® csökken, a második növekszik, értelemszer¶en a két korlát minimuma akkor lesz a lehet® legnagyobb, amikor a korlátok egyenl®ek. behelyettesítést látjuk, hogy 13 Ha elvégezzük a http://www.doksihu E(üres v -esek) +E(lefogott u-asok) ≤ nv q c1 v k−1 k−1 +nu (1−q k )c2 u < 12 + 12 .  5. Lineáris élszámú gráfok halmazainak Ramsey számai Ebben a fejezetben Rk (Hk,m1 ,l1 , Hk,m2 ,l2 ) matroidokkal való kapcsolat révén megadjuk m2 m1 és törtek megegyeznek, értékét pontosan, ha l1 l2 vagy mindketten beleesnek ugyanabba az intervallumba az alábbiak közül: [−1, 0] és [0, +∞). A bebizonyított elmélet korábban is ismert speciális esete, ha minden színosztályban megtiltom, hogy létezzen kör, azaz csak fákat illetve erd®ket engedek meg, tehát azt kérdezem, hogy

hány darab erd®vel lehet lefedni a teljes gráf élhalmazát, erre a kérdésre választ ad a Nash-Williams tétel. Ezt általánosítjuk. Ezeknek a korlátoknak az éles voltát megmutatjuk Adott gráfban Hm (k, l) valamely elemével izomorf részgráfok halmaza legyen C . Ez a halmaz kielégíti a matroid köraxiómákat, nevezetesen • ∅∈ / C, • sosem lesz különböz® halmazokra A ⊂ B és A, B ∈ C , • ha A, B két különböz® C -beli elem és e ∈ A ∩ B egy él a metszetb®l, akkor van C ∈ C melyre C ⊂ A ∪ B {e}. Az ilyen módszerrel kapott matroid a count matroid. A köraxiómákat nem közvetlenül szokás belátni, hanem a rangfüggvény felhasználásával. 5.1 Motiváció Deníció. Adott G gráf E élhalmazán az Mk,l count matroidot adjuk meg: valamely F ⊂ E(G) esetén vegyük az r∗ (F ) = k|V (F )| + l függvényt, ahol 14 http://www.doksihu V (F ) jelöli az F élhalmaz által feszített csúcsok halmazát. Ez metsz®

szubmoduláris függvény, vegyük az alsó reszeltjét Az alsó reszeltet metszeni kell a csupa 1 vektorral. Ez adja meg Mk,l rangfüggvényét A count matroidok nyelvén le lehet írni Nash-Williams tételét, amely szerint egy G(V, E) irányítatlan gráf élhalmaza pontosan akkor fedhet® le k erd®vel, ha a csúcsok minden X részhalmazára iG (X) ≤ k|X| − k itt iG (X) az X csúcshalmaz által feszített élek halmazának elemszámát jelenti. Count matroidként megadható egy gráf grakus matroidja, ez M1,−1 , ennek függetlenjei a körmentes élhalmazok. Az írásban vizsgált kérdés nyelvén ez úgy hangzik, hogy Mk,−k = M1,−1 k db itt k darab count matroid összegeként állítunk el® egy másik count matroidot. Egy gráf síkon vett merevségi matroidja az M2,−3 count matroid, sima tóruszra vagy hengerpalástra rajzolt gráf merevségi matroidja dimenziós tóruszon M2,−2 , n- Mn,−n , kúpon tekintett hurokmentes gráfra ez M2,−1 , konvex

poliéderen szintén hurokmentes gráfra M2,0 [10]. Ezt a kérdést vizsgálták korábban is, egy tévedést [8] eloszlatunk. Egy ott hivatkozott cikk kimondja a következ® állítást 4. TÉTEL Ha µ1 , µ2 nem-csökken® egészérték¶ nemnegatív szubmoduláris függvények 2S -en, akkor M (µ1 ) ∨ M (µ2 ) = M (µ1 + µ2 ) Ebb®l téves következtetésre jut: 5. TÉTEL Ha m = m1 + m2 és k = k1 + k2 ahol mk > −2, mk > −2, akkor 1 1 Mm1 ,k1 ∨ Mm2 ,k2 = Mm,k 15 2 2 http://www.doksihu Erre a tételre ellenpélda adható, legyen G egy 4 pontú kör amelynek minden éle kétszeres, m1 = 1, m2 = 2, k1 = −1, k2 = −3. A teljes élhalmaz rangja M2,−3 -ban 4, M1,−1 -ben 3 és M3,−4 -ben 8. Egyszer¶ gráf ellenpélda is adható. 5.2 Gráfok count matroidjai Meggyelés. kl ≤ −2 esetén Mk,l csupa hurkokból áll, ugyanis egy él rangja 2k + l ≤ 0. A továbbiakban feltesszük, hogy kl > −2 k < 0 esetén r∗ nem lesz metsz®

szubmoduláris. k = 0 eset az uniform matroid Ha valamelyik tételben, lemmában osztok k, k1 , k2 valamelyikével, akkor azt az állítást csak pozitív esetre értelmezzük. Mk1 +k2 ,l1 +l2 rangfüggvénye a következ® [9]: ( r+ (E1 ) = min F ⊂E1 ,F |E1 F | + X ) ((k1 + k2 )|V (Fi )| + l1 + l2 ) Fi ∈F Itt a minimumot F összes lehetséges F partíciójára tekintjük. Mk1 ,l1 ∨ Mk2 ,l2 rangfüggvénye a következ® [9]: r∨ (E1 ) = min {|E1 F | + r1 (F ) + r2 (F )} = F ⊂E1 ( ( ) X = min |E1 F | + min |F H1 | + (k1 |V (Fi )| + l1 ) + F ⊂E1 H1 ⊂F,F1   + min H2 ⊂F,F2  itt a minimumoknál futnak. Fi ∈F1 |F H2 | + X Fj ∈F2 )  = (k2 |V (Fj )| + l2 )  F1 és F2 halmazcsaládok H1 és H2 összes partícióin A bels® minimumok monotonok arra a halmazra nézve, amelyre kiértékeljük ®ket, lévén, hogy ®k Mk1 ,l1 és Mk2 ,l2 rangfüggvényei. emiatt feltehet®, hogy a minimum olyan halmazokon (is) felvétetik, ahol H1 =

H2 = F . Emiatt egy minimummal a következ®képp írható a rangfüggvény: 16 http://www.doksihu     X X = min |E1 F | + (k1 |V (Fi )| + l1 ) + (k2 |V (Fj )| + l2 ) F ⊂E1 ,F1 ,F2   Fi ∈F1 Fj ∈F2 itt a minimumoknál F1 és F2 halmazcsaládok F összes partícióin futnak. A két matroid pontosan akkor egyezik meg, ha a két rangfüggvény minimum képletben minden élhalmazra ugyanazt a számot kapjuk. Vagyis: ∀E1 ⊂ E   min F ⊂E1 ,F  X |E1 F | + X (k1 |V (Fi )| + l1 ) + Fi ∈F Fj ∈F   (k2 |V (Fj )| + l2 ) =      X X = min |E1 F | + (k1 |V (Fi )| + l1 ) + (k2 |V (Fj )| + l2 ) (1) F ⊂E1 ,F1 ,F2   Fi ∈F1 A két képlet között az Fj ∈F2 a különbség, hogy az els®ben(amelyik a paraméterek összegzésével kapott count matroid) a két szummában ugyanaz a partíció szerepel, míg a count matroidok összegzésével kapott matroid rangfüggvényénél ez a két partíció nem

feltétlenül azonos. 6. LEMMA r∨ = r+ pontosan akkor teljesül minden G gráfra, ha bármilyen G1 gráf E1 élhalmazára min F  X  = min (k1 |V (Fi )| + l1 ) + Fi ∈F  X F1 ,F2  X (k2 |V (Fj )| + l2 ) Fj ∈F (k1 |V (Fi )| + l1 ) + Fi ∈F1 X Fj ∈F2    =   (k2 |V (Fj )| + l2 )  (2) Itt F, F1 , F2 tetsz®leges partíciói E1 -nek. Bizonyítás. Ha (2) tetsz®leges élhalmazra teljesül, akkor az (1) képletben az |E1 F | -t®l különböz® tagok egyenl®sége miatt a minimumértékek ezzel a - két képletben azonos - taggal megtoldva egyenl®ek maradnak. 17 http://www.doksihu Másfel®l, ha adunk egy G példát, amelyre (2) nem teljesül, akkor ezt felhasználva megadható olyan gráf konstrukciója, amelyre r∨ (G) 6= r+ (G). Ezen a ponton a bizonyítást kétfelé ágaztatom, az els® ág sokkal egyszer¶bb, hátránya annyi, hogy nem egyszer¶ gráfot ad konstrukcióként. Egyszer¶bb bizonyítás. Az éleket

mindenütt többszörözzük meg Ezzel elérhetjük, hogy a minimum képlet értékét olyan részpartíción vegye fel, amely lefedi az összes élt. Ezzel kész is a lemma Egyszer¶ gráfos bizonyítás. Legyen kl22 < kl11 A 0-val osztás eredményét itt vegyük +∞-nek. Tegyük fel, hogy a (2) képletben a minimumot adó partíciók F, F1 , F2 . Nézzük G helyett a következ® gráfot: G minden élére ragasszunk rá két 0 csúcsával egy-egy Kt nagy teljes gráfot, nevezzük a kapott gráfot G -nek. Legyen t elég nagy. F2 alapján kaphatunk egy F 0 partíciót G0 élhalmazán, amelyet úgy kapunk, hogy a ragasztással hozzáadott élek a G-beli eredetijükkel azonos részbe kerülnek. kapható G 0 G élhalmazának partícióiból ily módon élpartíciók közt ez biztosan legjobb. Legyen G 0 élhalmazának 00 optimális részpartíciója Mk2 ,l2 rangfüggvényében azaz az (1) képletben F . 1. állítás F 00 lefedi G0 teljes élhalmazát és nem osztja

szét semelyik ragasztott Kt élhalmazát sem(és emiatt F 0 = F 00 ). 2. állítás Az 1 állítás és az Mk1 ,l1 és Mk1 +k2 ,l1 +l2 -re vonatkozó analogonjai (közös, nagy t választásra) együtt igazolják a 3 lemmát 2. állítás bizonyítása A G0 -beli (1) szerinti, 1 állításnak megfelel® alakú különféle partíciók eltérései ugyanazok, mint a nekik megfelel® G-beli (2) szerintiek, mert a részek száma ugyanaz, a régi csúcsok szerepeltetése a partíciók részeiben ugyanaz és az új csúcsok mind pontosan 1 részben vannak benne az összes partícióban. 1. állítás bizonyítása Elég a G = K2 , G0 = Kt esetre igazolni, ugyanis ha ott minden másfajta részpartíciót érdemes az egyrészes teljesre bec- 18 http://www.doksihu serélni, akkor nagyobb gráfok esetén ezt minden ragasztott Kt -ben érdemes megtenni. A részpartícióban minden osztálynak legfeljebb egy közös csúcsa van egy másik osztállyal vagy a részpartíción kívüli

éllel. Ezért a részpartícióban minden osztály élhalmaza teljes gráfot feszít Nézzük, mikor éri meg egy Kr teljes gráfot részpartícióbeli élekre bontani: 2), rk2 + l2 − r(r−1) (2k2 + l2 ) < 0 ez pontosan akkor teljesül (r ≥ 2 ha r < − 2k2l2+l2 . Hasonlóan megvizsgáljuk, hogy mikor éri meg
Kr teljes gráfot részpartíción kívüli élekre bontani: rk2 + l2 > 2r √ 2k2 +1+ 4k22 +4k2 +1+8l2 Jelöljük r0 = ez pontosan akkor teljesül, ha r < 2 l  √ 2 m  2k2 +1+ 4k2 +4k2 +1+8l2 max − 2k2l2+l2 , , ekkor minden r0 -nál kisebb teljes 2 egy részgráfot érdemes valahogy bontani, ezért az optimális partícióban ilyenek nincsenek. F 00 nem lehet élenkénti(ez az üres részpartícióval egyenérték¶ a mi esetünkben), mert akkor érdemes lenne becserélni egyrészesre. Tehát van benne egy H ∈ F 00 élosztály. H = Kt esetben készen vagyunk Egyébként van raj- ta kívül egy v csúcs. Ekkor az összes olyan osztályt

és részpartíción kívüli élt, amelynek van H -val közös csúcsa és illeszkedik v -re is, hozzáragasztjuk H -hoz. Összesen |V (H)| ilyen objektum van Ezek között a partíción kívüli élek száma legyen s. A ragasztás nyeresége: (|V (H)| + 1)k2 + l2 − s − |V (H)|k2 − l2 − (|V (H)| − s)(2k2 + l2 )) ≤ ≤ k2 − s − (|V (H)| − s)(2k2 + l2 ) < 0 Felhasználtuk, hogy |V (H)| ≥ r0 > k2 A részpartíció összsúlyát csökken- tettük, tehát az nem lehetett optimális. Emiatt csak az egyrészes teljes  részpartícióra adódik az optimum. A következ®kben mindenhol a (2) képletet használjuk, az r∨ és r+ közötti összefüggés megállapításához elég annyit eldönteni, hogy van-e a teljes élhalmazt lefed® közös optimális F partíció minden G-re Mk1 ,l1 és Mk2 ,l2 szerinti következ® képletben 19 http://www.doksihu ( min F ) X (k|Fi | + l) (3) Fi ∈F 7. LEMMA Ha l ≥ 0, akkor (3) képletben az egyrészes

partíció optimális Ha l > 0, akkor csak ez a partíció optimális. Bizonyítás. legyen F1 tetsz®leges nem egyrészes partíció és legyen F2 ebb®l úgy származtatva, hogy F1 -ben két részt(Fi és Fj ) összevonunk. Ezáltal az összeg k|V (Fi )∩V (Fj )|+l -el csökken l > 0 esetén ez szigorú csökkenés l = 0 esetén az összeg biztosan nem növekedett.  8. LEMMA Ha −1 ≤ kl ≤ 0, akkor (3)-ban az összefügg®ségi kompo- nensenkénti partíció optimális. Ha −1 < kl < 0, akkor csak ez a partíció optimális. Bizonyítás. Adott F partícióra, ha van olyan F ∈ F amelyre F nem összefügg®, akkor F -et szétbonthatjuk két csúcsokban is diszjunkt F1 , F2 részre. Legyen F1 = F {F } ∪ {F1 , F2 } ekkor F1 -re az összeg l-el csökkent, l = 0 esetben nem növekedett. Ha van olyan F1 , F2 ∈ F , amelyre V (F1 )∩V (F2 ) 6= ∅, akkor legyen F = F1 ∪F2 és F1 = F {F1 , F2 }∪{F }, ezáltal az összeg k|V (F1 ) ∩ V (F2 )| + l

-el csökken. l > −1 ez szigorú csökkenés, k l = −k esetén ez nem növekedés.  9. TÉTEL Ha kl = kl , akkor r∨ = r+ 1 1 2 2 Bizonyítás. Ilyenkor a kétféle (3) típusú képletben az összes lehetséges partícióra egymás konstansszorosait kapjuk, tehát a minimumok felvétetnek  ugyanazon a partíción. 10. TÉTEL Ha l1 ≥ 0 és l2 ≥ 0, akkor r∨ = r+ Bizonyítás. Ilyenkor a 7. lemma szerint a kétféle (3)-képletben az  egyrészes partíció optimális. 20 http://www.doksihu 11. TÉTEL Ha 0 ≥ kl ≥ kl ≥ −1, akkor r∨ = r+ 1 1 2 2 Bizonyítás. Ilyenkor az 8 lemma szerint a gráf összefügg®ségi komponensei szerinti partíció optimális mindegyik (3) típusú képletben  12. TÉTEL Ha l1 > 0 > kl , akkor van olyan G amelyre r∨ 6= r+ 2 2 Bizonyítás. Legyen E1 két diszjunkt él egymás mellett Ekkor (k1 , l1 ) szerinti (3) képletben az egyetlen optimális partíció az egyrészes, ám a (k2 , l2 )  szerintiben

csak az összefügg®ségi komponensek szerinti. 13. LEMMA Ha kl ≤ −1 és G fa, akkor a (3) képletben az élenkénti partíció optimális. Ha kl < −1 és G fa, akkor a (3) képletben csak az élenkénti partíció optimális. Bizonyítás. Legyen az optimális partíció F Ha ez nem élenkénti, akkor ismételgessük a következ®t, amíg élenkénti partíciónk lesz. Egy fa gráf minden részgráfja erd® Ebben mindig akad 1 fokú csúcs Ha ezt leválasztjuk, a (3) képlet értékének megváltozása k +l , ez ≤ 0 az els® esetben, a másodikban  < 0. 14. TÉTEL Ha kl ≥ −1 > kl , akkor van olyan G amelyre r∨ 6= r+ 1 1 2 2 n Bizonyítás. Ilyenkor van olyan n, amelyre kl > − n−1 > kl Legyen G 2 2 1 1 egy n csúcsú kör. Ekkor a 7 és 8 lemmák miatt Mk1 ,l1 szerinti (3) képlet optimális partíciója az egyrészes. Minden nem élenkénti partíció vagy az egyrészes, vagy tartalmaz fát, amit Mk2 ,l2 -ben az 13. lemma miatt élekre

érdemes bontani. Ha az egyrészes partíciót élenkéntire cseréljük, a változás: n(2k2 + l2 ) − nk2 − l2 = nk2 + (n − 1)l2 < 0 ezért itt az élenkénti partíció a legjobb. 21  http://www.doksihu 5.3 Konstrukció Ebben a részben példát adok olyan G gráfra, amelynek a rangja különböz® lesz M∨ és M+ matroidokban −1 ≥ l1 > kl22 > −2 esetén. Ez a konstrukció k1 egyszer¶ gráfot ad. ∗ Legyen G csúcshalmaza V (G) = {v1 , v2 , . , vn } Az átlagos fokszám(d ) legyen 2k2 − ε 2k1 < d∗ = 2k1 + l1 2k2 + l2 ∗ racionális szám (d > 2). Nemüres intervallumban keressük Válasszuk úgy, hogy ne legyen egész szám. d∗ -ot. l2 > −2 miatt a nevez® pozitív. k2 d∗ racionális, ltehát felírható két egész hányadosaként. A nevez®je legyen t0 m 1 − 1 . S¶r¶n vannak olyan számok, amelyekre h0 relatív {d∗ } ∗ prím t0 -hoz, legyen d ilyen. Ebben a fejezetben valamilyen εi mindig az Legyen h0 =

itteni ε lineáris függvényét jelöli. Egy ilyen gráfban az élenkénti partíció Mk2 ,l2 -ben jobb, mint az egyrészes, ellenben kell®en nagy n-re Mk1 ,l1 -ben az egyrészes partíció jobb, mint az élenkénti. m az élszám 2mk2 + ml2 < nk2 + l2 2mk1 + ml1 > nk1 + l1 (2m − n)k2 + (m − 1)l2 < 0 felhasználva, hogy nd ∗ = 2m  ∗ n(d − 1)k2 + d∗ <  1 ∗ nd − 1 l2 < 0 2 2k2 + 2 ln2 2k2 + l2 ∗ ez elég nagy n-re teljesül, d deníciója miatt. Minden vi csúcs di fokszámát a kisebb meretében deniáljuk a következ®képpen: 22 index¶ek fokszámainak is- http://www.doksihu id∗ − i X dj ≤ j=1  1 ∗ Legyen f = d 2 1 2 Legyen {v1 , v2 , . , vt } az els® néhány csúcs úgy, hogy rájuk éppen ∗ td = t X dj j=1 Feltehet®, hogy t = t0 ∗ Legyen h egy indexek szerinti távolság, amely el®fordulhat két dd e fokszámú csúcs között. Ekkor h-ra adhatunk becslést: (h + 1)d∗ + 1 ≥ (h −

1)bd∗ c + 2dd∗ e 1 −1 {d∗ } h≥ ∗ ∗ Itt {d } a d törtrészét jelenti. Ez ihlette h0 denícióját, h ≥ h0 Vegyünk egy nagy N számot. Legyen n a csúcsszám többszöröse h0 N t0 nak Nézzünk néhány számot a következ®képpen: t1 < t2 < . < tf páratlanok, N t-vel együtt {N t, t1 , t2 , . , tf } elemei páronként relatív prímek, ti ≡ 1 (mod t) minden i-re és a N tλ0 + f X ti λi = 0 j=1 diofantikus egyenlet nemtriv(azaz nem csupa 0) megoldásaira f X |λi | ≥ N i=0 Legyen ∀i-re n ≡ 1 mod ti és legyen n legalább N -szerese ugyanezen számok legnagyobbikának. El®ször minden vi -re illesszünk di − 2f élt: amelyik csúcsokra ez 1 vagy 2, azokat kössük össze az N t-vel utána következ®kkel, kivéve, 23 http://www.doksihu ha ez 1 és korábban összekötöttük az N tvel el®tte lev®vel. di −2f megegyezik bármely két egymástól N t távolságra lev® csúcsra. Most minden csúcsra fennmaradt 2f fokszám

mindet kössük össze az ®t t1 , t2 , tf indexre követ® csúcsokkal. Tekintsük a di −2f = 1 csúcsokat Ezek között N t (behúzott vagy be nem húzott) húrél¶ körök szerint partíciót adhatunk meg. Egy ekvivalenciaosztályon belül az N t távolságú pontpárok összekötöttségét és össze-nemkötöttségét felcserélve az el®írt fokszámoknak továbbra is megfelel® gráfot kapunk. Alkalmazzuk ezt úgy, hogy bármely két, egymástól h0 távolságra lév® di − 2f = 1 csúcsból a kivezet® N t élek közül az egyik el®re, a másik mindig hátra mutasson. Ha t0 és h0 relatív prímek, akkor N választható úgy, hogy N t0 relatív prím h0 -hoz és ekkor ez megtehet® lesz. Mk1 ,l1 -ben nem optimális partíció az élenkénti: 2k1 + 2 ln1 2k1 < < d∗ 2k1 + l1 2k1 + l1 ebb®l számolható 2mk1 + ml1 > nk1 + l1 ez pedig azt jelenti, hogy az egyrészes partíció jobb, mint az élenkénti. Megmutatjuk, hogy G-nek Mk2 ,l2 -ben optimális

partíciója az élenkénti. Legyen adott egy tetsz®leges F nomítható partíció. Ezen javítunk egy picit Legyen H ∈ F egy nem egyél¶ rész. Ha H -ban van legfeljebb f fokú csúcs, akkor érdemes a ráilleszked® éleket leszedni és külön-külön venni a partícióba, ehhez kell: 2k2 f + l2 f < k2 k2 f< 2k2 + l2 ∗ ez pedig teljesül, ugyanis a baloldal kétszerese kisebb, mint d , a jobboldal kétszerese pedig nagyobb nála. 15. TÉTEL Bármilyen H -t érdemes élekre lebontani 24 http://www.doksihu Bizonyítás. Nevezzünk ívnek egy olyan élhalmazt, amelyek azonos indextávolságú pontokat összeköt® húrokból álló út élei Ez az azonos távolság legyen t1 , t2 , tf valamelyike bezáródik, mert akkor lenne. H -ban nem lehet olyan ív, amely kör- H az összes pontra illeszkedne, vagyis H = G H -ban minden csúcsra f darab tartalmazásra nézve maximális ív illeszkedik. Mivel ti ≡ 1 (mod t) ezért egy J ív mentén a G-beli fokszámok

ugyanúgy következnek, mint szomszédos pontok esetén, tehát a J -beli fokszámok összege X dv = v∈V (J) s+q X di − i=1 s X di ≤ (s + q)d∗ + i=1 1 1 − sd∗ + = |V (J)|d∗ + 1 2 2 Ezt minden tartalmazásra nézve maximális H -beli ívre összegezzük. 0 él¶ H -beli íveket is megengedünk. K jelentse a H -beli tartalmazásra nézve maximális ívek számát. Minden ilyen ív két végén van egy H-ból kivezet® ugyanolyan hosszúságú él, és minden H -ból kivezet® él legfeljebb egy tartalmazásra maximális ívnek a folytatása. X v∈H Legyen a dv = X X dv f J⊂H v∈V (J) H -ból kivezet® N t hosszú élek száma m− . H élszámáról a következ®t tudjuk mondani(J ívet jelöl, az összes H -t érint® ívre összegzek)    − X X dv X X X m− m  1 dv  − 1 − mH = − 1− = ≤ 2f 2 2f 2 J⊂H J⊂H J⊂H v∈V (J) ≤ X J⊂H v∈V (J)   X 1 1 m− 1 m− ∗ ∗ (|V (J)|d + 1) − 1 − = f nH

d + −1 − 2f 2 2f 2f 2 J⊂H Felhasználva, hogy 2mH = nH dH , és dH alsó becsléséb®l  X 1 1 ∗ nH ≤ nH dH ≤ f nH d + − 2 − m− 2k2 + l2 f f J⊂H 2k2 + 2 nlH2 ∗ ∗ Ha d deníciójából elhagyjuk az ε-t, akkor fels® becslését kapjuk d -nak, ezzel  X 1 2k2 nH ≤ nH + − 2 − m− 2k2 + l2 2k2 + l2 J⊂H f 2k2 + 2 nlH2 25 http://www.doksihu  X 1 2l2 ≤ − 2 − m− 2k2 + l2 J⊂H f Mindkét oldalon negatív számok állnak. (4) Ez akkor adja a keresett ellent- mondást, ha a tartalmazásra nézve maximális ívek száma, amikre összegzünk, az nagy. Legyen K a H tartalmazásra nézve maximális részíveinek száma Jelölés c = l2 2k2 −ε 2 ∗ , ekkor d = = 2+c − ε1 k2 2k2 +l2 l2 3 = c > − 2 Tudjuk, hogy f ≥ 1 k2 1. eset −2 · 32 2l2 > −K − m ≥ = −6 2k2 + l2 2 − 32 k  1 ∗  1 2
 j 1 ε1 Ilyenkor f = d = 2 2+c − ε1 ≤ 2− 3 − 2 = 1 és a gráfunk olyan, 2 − 2 hogy az ívek és az íven

kívüli, H -ra egy végponttal csatlakozó élek számának összege legfeljebb 5. d ∗ 2 < 2+c ≤4 1.a eset H -ban minden ív rövidebb, mint 2tn 1 1.ai) eset H -ban 1 ív van: ilyenkor H fa, tehát van legfeljebb f fokú csúcsa. 1.aii) eset H -ban 2 ív van: legalább 2 összeköt® él kell közöttük, különben H ismét fa lenne. ∗ 1.aiiα) eset d < 3 Ezeknek az összeköt®knek a távolsága h > h0 mert két t1 h0 távolságra lev® csúcsból kivezet® N t él különböz® irányba mutat ugyanis bármely h0 távolságra lév® párra ez igaz és t1 páratlan. Tehát a két ív összekötése között legalább h0 +1 él van külön-külön az íveken. H ilyenkor létra alakú. az egyik kezd® fül nagysága 2h0 + 3 él Ezt a fület érdemes lebontani, ha c < −1 − 2h01+3 ezt átrendezve h0 > − 4+3c ámde ilyenkor 2+2c {d∗ } = d∗ − 2 tehát h0 ≥ 1 d∗ − 2 −1> 1 4 + 3c −1=− 2 2 + 2c −2 2+c vagyis a fül lebomlik, az

optimális partícióban nem lehetett ilyen H - ellentmondás. 2 4 ∗ 1.aiiβ ) eset d > 3 ilyenkor c < −2 + ∗ = − Ebben az esetben minden d 3 legalább 3 élb®l álló fület érdemes lebontani, a létra végén mindig van egy ilyen. 26 http://www.doksihu 1.aiii) eset H -ban 3 ív van. A három közül az egyik középen van, a másik kett® legalább két-két N t éllel kapcsolódik hozzá. Ha az egyik széls® kapcsolatai közrefogják a másik széls® két kapcsolatát, akkor vagy a közrefogó kapcsolatú ív egy hosszú fület ad ki, vagy ez fel van osztva, ilyenkor azonban lesz 3 H -ra illeszked® küls® N t él a 3 ívvel együtt az 6, ellentmondás. Ha nem fogják közre, akkor 8-ashoz hasonló alakzatunk van. Itt van egy 3h + 2 hosszúságú fül, bomlik, mert 3h0 + 2 ≥ 2h0 + 3 és ez a nem nagyobb típusú fül is bomlik, mint az 1.aii) esetben 1.aiv) eset H -ban 4 ív van Ilyenkor két középs® ív van Az egyik széls® ív kapcsolódása nem

lehet kijjebb, mint a két középs® között, mert az 3h + 2 fül lenne. A korábbiak alapján még nem kizárható felállás csak az, amikor a két középs® ív két kapcsolata közrefogja a két széls® rész kapcsolatait. ilyenkor 4 darab harmadfokú csúcs van sok másodfokú között, az élszám legalább 8h + 6, a bontás nyereségének becslésénél felhasználjuk, hogy a 2h0 + 3 fülek bomlanak, azaz (2h0 + 3)(2 + c) < 2h0 + 4 + c (8h+6)(2k2 +l2 )−(8h+4)k2 −l2 < 1 ((6h+3)(2+c)+2h)0 +4+c−(8h+4)−c) < 0 k2 tehát érdemes bontani. 1.av) 5 ív eset a korábbiakhoz hasonló 1.b eset van 2tn -nél nem rövidebb ív H ponthalmazának komplemen1 tálása esetén olyan halmazhoz jutunk, amelyben ugyanannyi ív van, mint H -ban és a kivezet® N t élek száma is egyezik, ezek az élek ugyanazok. Ezért elég megmutatni, hogy minden legfeljebb n csúcsú részgráfra az ívek és a 2 kivezet® élek számának összege legalább 6. Nézzük az egyik

leghosszabb ívet A hossza t-nek tetsz®legesen nagy többszöröse, mert n-ben lineáris. Emiatt feltehet®, hogy tetsz®legesen sok N t él vezet ki bel®le. Lehetnek N t élek a pontjai között is, de mindenképp van az utolsó n n ∗ pontján darab dd e 2t1 2tt1 fokú csúcs, ezek között minden, az íven élenként számolt h0 hosszú szakaszon van irányváltás tehát legalább n darab N t él vezet kifelé. Kell®en nagy 2th0 t1 n-re ez szintén tetsz®legesen nagy lehet, tehát ezek legalább 1, legfeljebb 4 darab új ívre vezetnek amelyek leghosszabbikának a hossza n-ben lineáris függvény lesz, a m¶veletet ismételhetjük, amíg elérjük a 6 ívet. 27 http://www.doksihu 2. eset c < − 32 , ekkor f ≥ 2  1 K 2− f 2.a eset  + m− ≤ − Minden 4 2c = − 2 = 2d∗ − 2 + ε2 < 4f + 2 2+c 2+c H -beli ív rövidebb tnf -nél. Feltehet®, hogy ∀i ∈ {1, 2, . f − 1}-re ti < 12ti+1 2.ai) eset Van legalább 9 csúcsú ív, akkor a

csúcsain szerepl® ívek közül mind különböz® kivéve a legalább 9 csúcsút, ami alapján választottunk. Ha az ív csúcsszáma s, akkor ez összesen 1 + s(f − 1) ≥ 4f + 2 darab ív. 2.aii) eset Minden ív legfeljebb 8 csúcsú Ekkor H egy fa 2.b eset van tn -nél nem rövidebb ív Ugyanúgy kezelhet® mint az 1b f eset. 5.4 Hipergráfok count matroidjai Deníció. Adott H hipergráf E hiperélhalmazán az Mk,l count matroidot ∗ adjuk meg: valamely F ⊂ E esetén vegyük az r (F ) = k|V (F )|+l függvényt, ahol V (F ) jelöli az F hiperélhalmaz által feszített csúcsok halmazát. Ez metsz® szubmoduláris függvény, vegyük az alsó reszeltjét. Az alsó reszeltet messük a csupa 1 vektorral, ez adja meg Mk,l rangfüggvényét. Meggyelés. kl ≤ −r esetén Mk,l -ben minden legfeljebb r csúcsú él hurok, ugyanis rangja rk + l ≤ 0 A továbbiakban feltesszük, hogy kl > −r ahol r a legkisebb hiperél csúcsszáma. k < 0 esetén r∗ nem lesz

metsz® szubmoduláris k = 0 eset az uniform matroid. Azt vizsgáljuk, mikor lesz Mk1 ,l1 ∨ Mk2 ,l2 = Mk1 +k2 ,l1 +l2 két count matroid összegmatroidja a paraméterek összegzésével kapott count matroid. Mk1 +k2 ,l1 +l2 rangfüggvénye a következ®: ( ) X r+ (E1 ) = min |E1 F | + ((k1 + k2 )|V (Fi )| + l1 + l2 ) F ⊂E1 ,F Fi ∈F Ahol a minimumot F összes lehetséges F partíciójára tekintjük. Mk1 ,l1 ∨ Mk2 ,l2 rangfüggvénye, mint láttuk, a következ®: 28 http://www.doksihu     X X r∨ (E1 ) = min (k2 |V (Fj )| + l2 ) |E1 F | + (k1 |V (Fi )| + l1 ) + F ⊂E1 ,F1 ,F2   Fi ∈F1 Fj ∈F2 itt a minimumoknál F1 és F2 halmazcsaládok F összes partícióin futnak. Szokás szerint kiiktatjuk a |E1 F | tagot. Ebben a lemmában az a jó, hogy a konstrukciót úgy is meg lehet csinálni, hogy r -gráfból továbbra is r-gráfunk lesz, de vegyes elemszámú hiperélek esetén is igaz marad. 16. LEMMA r∨ = r+ pontosan akkor teljesül minden H

hipergráfra, ha bármilyen H1 hipergráf E1 élhalmazára min F  X  = min (k1 |V (Fi )| + l1 ) + Fi ∈F  X F1 ,F2  X (k2 |V (Fj )| + l2 ) Fj ∈F (k1 |V (Fi )| + l1 ) + Fi ∈F1 X Fj ∈F2    =   (k2 |V (Fj )| + l2 )  (5) Itt F, F1 , F2 tetsz®leges partíciói E1 -nek. Bizonyítás. Ha (5) tetsz®leges hiperélhalmazra teljesül, akkor az eredeti képletben az |E1 F | -t®l különböz® tagok egyenl®sége miatt a minimumértékek ezzel a - két képletben azonos - taggal megtoldva egyenl®ek maradnak. 0 Másfel®l, ha adunk egy H példát, amelyre (5) nem teljesül, akkor ezt felhasználva megadható olyan hipergráf konstrukciója, amelyre r∨ (H) 6= r+ (H). A sima gráfos esetnek megfelel®en lehet a hiperéleket többszörözni vagy t r
alakú gubancokat ragasztani a hiperélekre. A következ®kben mindenhol a 16. lemma szerinti képletet használjuk, az r∨ és r+ közötti összefüggés megállapításához

elég annyit eldönteni, hogy van-e a teljes élhalmazt lefed® közös optimális F partíció minden H-ra Mk1 ,l1 és Mk2 ,l2 szerinti következ® képletben 29 http://www.doksihu ( min F ) X (k|Fi | + l) (6) Fi ∈F Szó szerint, bizonyítással együtt másolhatóak a 7. és 8 lemmák illetve a a 9-12. Tételek 17. LEMMA Ha l ≥ 0, akkor (6) képletben az egyrészes partíció opti- mális. Ha l > 0, akkor csak ez a partíció optimális 18. LEMMA Ha −1 ≤ kl ≤ 0, akkor (6)-ben az összefügg®ségi kompo- nensenkénti partíció optimális. Ha −1 < kl < 0, akkor csak ez a partíció optimális. 19. TÉTEL Ha kl = kl , akkor r∨ = r+ 2 2 1 1 20. TÉTEL Ha l1 ≥ 0 és l2 ≥ 0, akkor r∨ = r+ 21. TÉTEL Ha 0 ≥ kl ≥ kl ≥ −1, akkor r∨ = r+ 1 1 2 2 22. TÉTEL Ha l1 > 0 > kl , akkor van olyan H amelyre r∨ 6= r+ 2 2 A maradék állítások is másolhatóak. Hipergráfot itt akkor célszer¶ fának tekinteni, ha bármely két u, v

csúcsa között egyértelm¶en van v = v0 ∈ H0 3 v1 ∈ H1 3, . , Hn−1 3 vn = u ismétl®désmentes sorozat felváltva csúcsokból és hiperélekb®l. 23. LEMMA Ha kl ≤ −1 és H fa, akkor a (6) képletben az élenkénti partíció optimális. Ha kl < −1 és H fa, akkor a (6) képletben csak az élenkénti partíció optimális. Bizonyítás. Legyen az optimális partíció F. Ha ez nem élenkénti, akkor ismételgessük a következ®t, amíg élenkénti partíciónk lesz. Egy fa gráf minden részgráfja erd®. Ebben mindig akad a többihez csak egy csúcsban illeszked® hiperél. Ha ezt leválasztjuk, a (6) képlet értékének megváltozása k + l, ez ≤ 0 az els® esetben, a másodikban < 0. 30 http://www.doksihu Mondjuk n hosszú körnek az olyan hipergráfot, amely a sima n hosszú kör gráfból kapható néhány csúcs egy-egy élhez hozzávételével, tehát minden csúcsot csak 1 élhez vehetünk hozzá. 24. TÉTEL Ha kl ≥ −1 > kl ,

akkor van olyan G amelyre r∨ 6= r+ 1 1 2 2 Bizonyítás. Mint gráfoknál 25. TÉTEL Ha kl < kl ≤ −1, akkor van oyan hipergráf, amelyen a ma1 1 2 2 troidok nem összegz®dnek. Bizonyítás. A [−2, −1] intervallumon s¶r¶n megadtunk elválasztópontokat az 53 alfejezetben A hipergráf minden pontját megkett®zzük úgy, hogy minden hiperél egy másolat pontot pont akkor tartalmaz, amikor az eredetit. Ezzel a módszerrel konstruálhatunk ellenpéldát amikor a hányadosok a [−4, −2] intervallumba esnek, azt megint megkett®zhetjük, stb. 5.5 Hk,m,l típusú gráfhalmazok Ramsey-számainak meghatározása count matroidok összegzésével Egy teljes hipergráf élhalmazát akarjuk felbontani néhány részre úgy, hogy az i-edik részben ne legyen Hk,mi ,li +1 -beli elem, ez pontosan azt jelenti, hogy az i-edik hiperélhalmaz független Mmi ,li -ben. Legyen t a legnagyobb pozitív egész, amelyre teljesül a következ®.   X r t ≤ (tmi + li ) k i=1 (7)

Észrevétel. Rk (Hk,m1 ,l1 +1 , Hk,m2 ,l2 +1 , , Hk,mr ,lr +1 ; r) ≤ t + 1 Azért igaz ez, mert t + 1 ponton valamelyik színosztályban már biztosan túl sok hiperél lesz egyszer¶ skatulyaelv okán. az Egy k -uniform hipergráfon Mmi ,li count matroidban Hk,mi ,li elemei még függetlenek, de Hk,mi ,li +1 elemei már függ®k. Ha a megfelel® count matroidok összege a paraméterek összegzésével kapott count matroid, akkor a Ramsey-szám pontosan ennyi. Ha ez nem teljesül, a fels® becslés akkor is érvényben marad, a tényleges Ramsey-szám azonban ennél kisebb lehet. 31 http://www.doksihu 26. TÉTEL Legyen (m1 , l1 ), , (mt , lt ) olyan egész számpárok, hogy ∀i- re 1 ≤ i ≤ r esetén mi > 0 és az mlii hányadosok mind egyenl®ek vagy mind benne vannak az alábbi két intervallum közül ugyanabban: [−1, 0] és [0, +∞). Legyen t a legnagyobb pozitív egész amely kielégíti (7) egyenl®tlenséget. Ekkor Rk (Hk,m1 ,l1 +1 , Hk,m2 ,l2 +1 , .

, Hk,mr ,lr +1 ; r) = t + 1  Hivatkozások [1] Exoo, Georey; Harborth, Heiko; Mengersen, Ingrid On Ramsey numbers of K2,n . Graph theory, combinatorics, algorithms, and applications (San Francisco, CA, 1989), 207211, SIAM, Philadelphia, PA, 1991. [2] Gyárfás, András; Gerencsér, László; On Ramsey-type problems. Ann Univ. Sci Budapest Eötvös Sect Math 10 1967,167-170 [3] Gyárfás, András; Ruszinkó, Miklós; Sárközy, Gábor N.; Szemerédi, Endre Three-color Ramsey numbers for paths Combinatorica 27 (2007), no. 1, 3569 (Reviewer: R H Schelp) [4] Gyárfás, András; Partíciófedések és lefogó halmazok hipergráfokban Communications of the Computer and Automation Institute of the Hungarian [5] Gyárfás, András; Tuza, Zsolt An upper bound on the Ramsey number of trees. Discrete Math 66 (1987), no 3, 309310 Academy of Sciences 71 (1977) 62 pp. [6] Radziszowski, Stanisªaw P. Small Ramsey numbers Electron J Combin 1 (1994), Dynamic Survey 1, 30 pp [7] Erd®s, P. Some

remarks on the theory of graphs Bull Amer Math Soc. 53, (1947) 292294 32 http://www.doksihu [8] Whiteley, Walter: Some Matroids from Discrete Applied Geometry, Contemporary Mathematics, Volume 197 (1996) proposition A.21 [9] Frank András: http://www.cseltehu/∼frank/jegyzet/matroid/ulmat2007pdf [10] Whiteley, Walter: The Union of Matroids and the Rigidity of Frameworks, SIAM J. Disc Math Vol1, No 2, May 1988, Society for Industrial and Applied Mathematics [11] Chvátal, V. Tree-complete graph Ramsey numbers J Graph Theory 1 (1977), no. 1, 93 [12] Graham, Ronald L.; Rothschild, Bruce L; Spencer, Joel H John Wiley & Sons, Inc., New York, 1990 Ramsey theory 33