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 nagy, akkor van konvex n-szög. N Felveszünk egy irányt vízszintesnek. elég 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 pontunk csupa egyszín¶

háromszöggel, máris megvan a konvex n darab 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. egy n pontú halmazt. Válasszunk ki néhány 3 Tekintsünk k és néhány k −1 elem¶ halmazt http://www.doksihu úgy, hogy ne tartalmazzák egymást, ne legyen és ne legyen hogy ha n v (k − 1)-es pont kiválasztott u pont kiválasztott k -as nélkül nélkül. Azt fogjuk megmutatni, 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 Kt Tn a az t n pontú fa gráfok halmaza. 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 ményez. az a gráf amelyet Kt egy élének elhagyása ered- Majdnem teljes gráfnak fogom nevezni. melynek osztályai pontú út, Kt − e Ci az i m, n pontúak, nyilván pontú kör. Legyen Si Ki,1 az Km,n i+1 a teljes páros gráf pontú csillag. Pi az i az i pontú kett®scsillag gráfok hal- maza, 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 , H 2 , . egyelem¶) halmazai. gráfok illetve közös Ekkor k -ra Rk (H1 , H2 , . Ht ; t) egész, melyre az ilyen pontszámú teljes gráf vagy színnel színezve valamely Ha nem írom ki k -t vagy i-hez t-t, lesz az i. uniform hipergráfok (akár legyen a legkisebb pozitív k uniform hipergráf éleit színosztályban akkor 2-nek értend®. Ha Hi -beli Hi t (hiper)gráf. 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 Rk (H1 , H2 , . Ht ; t) etén a legkisebb n valamely amelyre az színnel színezve valamely i-re n {Ks2 }-nek. H1 , . H t k pontú teljes az i-edik k uniform hipergráfcsaládok esuniform hipergráf hiperéleit színosztályban lesz Hi -beli t hipergráf (Nem feltétlenül feszített). Hk,m,l azon részgráfképzésre nézve minimális 4 k uniform hipergráfok, 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 úgy kapható H2 -b®l, H3 ⊂ H2 esetén Rk (H1 , H2 ) ≤ Rk (H1 , H3 ) és ha 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 gáljuk. R(k, l) R(k, l)-et vizs- 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 − ε egyébként 0. Végtelen sok Az ahol ε értéke 1, ha n és n-re R(K2,n , K2,n ) = 4n − 2 m egyaránt párosak, teljesül [1] R(G, H) Ramsey-szám már ismert minden legfeljebb 5 csúcsú G és H esetén kivéve 3 esetet: Magasabb R(K5 , K5 ), R(K5 , K5 − e), R(K5 , K5 − P3 ) 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 6 r szín 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 R(Tn , Tn , . , Tn ; k) hogy a k szín¶ nem ismert k = 2 Tn ∈ Tn -re esetben sem. a k szín¶ Ismert azonban [5], p R(Tn , Tn , . , Tn ; k) ≤ (n − 1)(k + k(k − 1) ) + 2 Ekkora 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 T1 ⊂ T2 ⊂ . ⊂ Tn adhatjuk. Legyenek ahol Ti pontszáma záadva kaphatjuk i. Értelemszer¶en Ti+1 -et. egymásba skatulyázott fák sorozata Ti -hez Teljes indukció Indirekt bizonyítás, tegyük fel, hogy A következ® konstrukciót megfelel® helyen levelet hoz- m-re. Az m = 2 (n − 1)(m − 1) + 1 élek kiszínezve kékre és lilára, de nincs sem kék Tn eset triviális. pontunk van, az sem lila Km . sorozat szerinti legnagyobb kék fa amit megtalálunk a gráfban van. Rögzítsük le ragasztása Ti+1 -et Ti Legyen a Ti . T1 biztos egy el®fordulását. Ebben van egy pont, ahol kék levél 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 miatt van benne lila Km−1 vagy kék egészíteni azzal a ponttal, ahol a kék Tn . Ti pontú tehát az indukciós feltevés A lila teljes gráfot pedig ki tudjuk 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 ál- talánosabban is alkalmazható. R(Tl , Km , Kn ) ≥ (R(Km , Kn ) − 1)(l − 1) + 1 Ezt úgy tudjuk bizonyítani, hogy veszünk egy

strukciót kék és sárga színekkel kék l−1 csúcsa helyére befújunk egy Km és sárga R(Km , Kn ) − 1 pontú konKn nélkül. Ennek minden 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 speciális esete az l l = 3, pontú fa, sem kék Km sem sárga Kn . Ezek érdekes 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 illetve 2n pontú utakra [2] ismert 2 színnél aszerint [3], hogy R(Sn , Sn ) 4. n n b 3n−2 c, 2 3 színnél 2n − 1 páratlan vagy páros. értéke konstans hibától eltekintve 4n 3 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 k, u, v és néhány paramétereket. k−1 Az alaphalmazon válasszunk ki néhány 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 (ii) v pont úgy, hogy nem tartalmaznak egyetlen kiválasztott (k − 1)-est sem, (iii) Egy kiválasztott k -as tartalmaz egy kiválasztott 8 sem, (k − 1)-est. http://www.doksihu A legkisebb egészt, amekkora alaphalmazon ezt nem lehet megtenni, jelölje 1. Hk (u, v). Feltehet®, hogy k ≤ u, v . TÉTEL. H (u, v) véges k Bizonyítás. H k,u jelentse az olyan halmazát, ahol bármely k Baysa-konstrukcióban a pedig nincs az üres az összes k -as, konstrukciót. minden k−1 hasonlóan a pontú k−1 uniform hipergráfok pontú halmazok között nem lehet H k,u -beli u pontján csak tartalmazással lehetne kiválasztott u-as a k -asok között. Ha viszont nincs ilyen, akkor aminek nem választottuk ki

részhalmazát, jól egészíti ki a Hkv jelölje azon v pontú k uniform hipergráfok halmazát, ahol pontú részhalmazt tartalmaz valamely hiperél. Az el®bbihez k -asok Hkv -beli között nem lehet részhipergráf mert ennek a pontján csak tartalmazással lehetne kiválasztott akkor üres k−1 ponthoz van ®t részhalmazként lefogó hiperél. Egy részhipergráf, mert annak k -as, u v -esünk van a (k − 1)-esek (k − 1)-es, v ha pedig nincs, 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}) magasságú 2-esekb®l álló torony függvény a legtetején Néhány esetben Egyszer¶ eset még Legfeljebb v−1 x-szel

ahol  tk (x) a k megtoldva. Hk (m, l)-et könny¶ megadni. Hk (k, v) = v , Hk (u, k) = u k = 2, ekkor néhány élt és néhány csúcsot kell kiválasztani. 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 gyelembevéve tudunk fels® becslést adni. 9 H k,u elemei közül csak egyet http://www.doksihu k=3 gráfok. eset: háromszögeket és éleket választunk ki. H 3,u elemei egyszer¶ 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 10 K4 lenne ami láthatóan http://www.doksihu nem lehet. v−1 A háromszögön kívüli csúcsok száma legfeljebb 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) ≤ k = 3, u = 6-nál  3+v−2 v(v + 1) . = 2 2 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. H3 (u, v) ≤ R2 Bizonyítás. Tekintsünk egy adott konstrukciót. l u m R2  juk ,v + . 2 2 u
u , v + 2 pontú 2 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 Baysa-feladatra pontú, vagy van lila Kv . Van benne kék tel- 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 teljes v, u 2 vagy lila 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. k kiszámolásához javasolt H 3,u halmaz  elemeit Nevezzünk egy hipergráfot lefogónak, ha minden 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 -ban, Egy hipergráf akkor és csak 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 H 3,u -ban vagyunk. klikk, akkor a kapott gráf minden hiperéle kritikus, vagyis Adódik a kérdés: minden ból ilyen módon? Egy u H k,u -beli gráfot megkaphatunk H k,u−1 -beli gráf- pontú lefogó hipergráf egy csúcsát elhagyva is- mét lefogó hipergráfhoz jutunk. Az nem igaz, hogy egy egy csúcsának elhagyása mindig H k,u−1 H 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 -beli Tehát minden H 3,u -

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 valószín¶séggel választok ki. 12 p http://www.doksihu p(egy rögzített v pontú halmaz üres) v = 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 = a le van fogva) Ugyanúgy, mint el®bb, az száma, u k ponton, az összes válogathatok (k − 1)-esük k -adik a ≤ kitev® a független k -asokból álló rendszer elem- (k − 1)-esre rakhatok k -ast és a maradék csúcsokat hozzájuk úgy, hogy a k -asoknak (k−1)u k ponton ne legyen közös 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 c1 , c2 u-asok és az üres v -esek v- számának várható értékére konstansokkal a

várható érték additivitása miatt érvényes a következ® becslés:
(v ) k−1 q k ≤ nv q c1 v u
k ) k−1 n k (k−1 u-asok) ≤ u (1 − q ) ≤ nu (1 − q k )c2 u E(üres v -esek) ≤ E(lefogott n v 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 q 1−q k   n< 2  n<  q 2 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 matroidokkal való kapcsolat révén megadjuk m2 m1 és

törtek megegyeznek, értékét pontosan, ha l1 l2 Rk (Hk,m1 ,l1 , Hk,m2 ,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 legyen C. Hm (k, l) valamely elemével izomorf részgráfok halmaza Ez a halmaz kielégíti a matroid köraxiómákat, nevezetesen • ∅∈ / C, • sosem lesz különböz® halmazokra • ha A, B két különböz® akkor van C∈C C -beli melyre A⊂B elem és és A, B ∈ C , e ∈ A∩B egy él a metszetb®l, 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ó. valamely Adott G F ⊂ E(G) gráf E élhalmazán az esetén vegyük az ∗ Mk,l count matroidot adjuk meg: r (F ) = k|V (F )| + l 14 függvényt, ahol http://www.doksihu V (F ) jelöli az F élhalmaz által feszített csúcsok halmazát. Ez metsz® szub- modulá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 erd®vel, ha a csúcsok minden X k részhalmazára iG (X) ≤ k|X| − k itt iG (X) az X csúcshalmaz által feszített élek halmazának elemszámát je- lenti. Count matroidként megadható egy gráf grakus matroidja, ez M1,−1 , en- nek 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 Mn,−n , M2,−2 , n- kúpon tekintett hurokmentes gráfra ez konvex poliéderen szintén hurokmentes gráfra M2,0 M2,−1 , [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 2 -en, akkor M (µ1 ) ∨ M (µ2 ) = M (µ1 + µ2 ) S Ebb®l téves következtetésre jut: 5. TÉTEL. Ha m = m + m 1 2 és k = k1 + k2 ahol Mm1 ,k1 ∨ Mm2 ,k2 = Mm,k 15 m1 k1 > −2, mk22 > −2, akkor http://www.doksihu G Erre a tételre ellenpélda adható,

legyen minden éle kétszeres, rangja M2,−3 -ban 4, egy 4 pontú kör amelynek m1 = 1, m2 = 2, k1 = −1, k2 = −3. M1,−1 -ben M3,−4 -ben 3 és A teljes élhalmaz 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 azt az állítást csak pozitív esetre értelmezzük. valamelyikével, akkor Mk1 +k2 ,l1 +l2 rangfüggvénye a következ® [9]: ( r+ (E1 ) = min F ⊂E1 ,F Itt a minimumot Mk1 ,l1 ∨ Mk2 ,l2 F X |E1 F | + ) ((k1 + k2 )|V (Fi )| + l1 + l2 ) Fi ∈F összes lehetséges F partíciójára tekintjük. 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.  F1 Fi ∈F1 |F H2 | + X Fj ∈F2 és F2 )  = (k2 |V (Fj )| + l2 )  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. feltehet®, hogy a minimum olyan halmazokon (is) felvétetik, ahol F. H1 = H2 = Emiatt egy minimummal a következ®képp írható a rangfüggvény: 16 emiatt http://www.doksihu     X X = min |E1 F | + (k1 |V (Fi )| + l1 ) + (k2 |V (Fj )| + l2 ) F ⊂E1 ,F1 ,F2   Fi ∈F1 itt a minimumoknál F1 és F2 Fj ∈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 ) F ⊂E1 ,F1 ,F2   Fi ∈F1 A két képlet között az (1) 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ármi- lyen G1 gráf E1 élhalmazára min F  X  (k1 |V (Fi )| + l1 ) + Fi ∈F = min  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éplet- |E1 F | -t®l különböz® tagok egyenl®sége

miatt a minimumértékek ben az ezzel a - két képletben azonos - taggal megtoldva egyenl®ek maradnak. 17 http://www.doksihu G Másfel®l, ha adunk egy 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. +∞-nek. itt vegyük partíciók G < l1 A 0-val osztás eredményét k1 Tegyük fel, hogy a (2) képletben a minimumot adó helyett a következ® gráfot: csúcsával egy-egy t l2 k2 F, F1 , F2 . Nézzük Legyen Legyen Kt elég nagy. G minden élére ragasszunk rá két nagy teljes

gráfot, nevezzük a kapott gráfot F2 alapján kaphatunk egy F0 partíciót G0 amelyet úgy kapunk, hogy a ragasztással hozzáadott élek a tijükkel azonos részbe kerülnek. kapható G0 1. állítás F 00 Kt 2. állítás Mk2 ,l2 G0 lefedi erede- Legyen G0 élhalmazának F 00 . teljes élhalmazát és nem osztja szét semelyik Az 1. állítás és az t G-beli rangfüggvényében azaz az (1) képletben élhalmazát sem(és emiatt gonjai (közös, nagy élhalmazán, élhalmazának partícióiból ily módon élpartíciók közt ez biztosan legjobb. optimális részpartíciója ragasztott G G0 -nek. Mk1 ,l1 F 0 = F 00 ). és Mk1 +k2 ,l1 +l2 -re vonatkozó analo- 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) sze- rintiek, 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, ugya- nis ha ott minden másfajta részpartíciót érdemes az egyrészes teljesre bec- 18 http://www.doksihu Kt -ben serélni, akkor nagyobb gráfok esetén ezt minden ragasztott é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 Kr teljes gráfot részpartícióbeli élekre bonr(r−1) tani: rk2 + l2 − (2k2 + l2 ) < 0 ez pontosan akkor teljesül (r ≥ 2 l2 2), ha r < − 2k2 +l2 . Hasonlóan megvizsgáljuk, hogy mikor éri meg
r egy Kr teljes gráfot részpartíción kívüli élekre bontani: rk2 + l2 > 2 √ 2k2 +1+ 4k22 +4k2 +1+8l2 Jelöljük r0 = ez pontosan akkor

teljesül, ha r < 2    Nézzük, mikor éri meg egy l m max − 2k2l2+l2 , 2k2 +1+ √ 4k22 +4k2 +1+8l2 2 , ekkor minden r0 -nál kisebb teljes 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 es- etünkben), mert akkor érdemes lenne becserélni egyrészesre. Tehát van benne egy H ∈ F 00 ta kívül egy élosztály. v esetben készen vagyunk. Egyébként van raj- csúcs. Ekkor az összes olyan osztályt és részpartíción kívüli élt, amelynek van H -hoz. H = Kt Összesen H -val |V (H)| élek száma legyen s. közös csúcsa és illeszkedik v -re is, hozzáragasztjuk ilyen objektum van. Ezek között a partíción kívüli 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 következ® képletben 19 G-re Mk1 ,l1 és Mk2 ,l2 szerinti http://www.doksihu ( min F 7. ) X (k|Fi | + l) (3) Fi ∈F LEMMA. Ha l ≥ 0, akkor 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 l=0 8. F2 tetsz®leges nem egyrészes partíció és legyen ebb®l úgy származtatva, hogy tal az összeg (3) F1 -ben két részt(Fi és Fj ) összevonunk. Ezál- k|V (Fi )∩V (Fj )|+l-el csökken. l > 0 esetén ez szigorú csökkenés  esetén az összeg biztosan nem növekedett. LEMMA. Ha −1

≤ ≤ 0, akkor l k (3) nensenkénti partíció optimális. Ha −1 < optimális. Bizonyítás. Adott nem összefügg®, akkor F1 , F 2 részre. csökkent, Legyen l=0 F l k -ban az összefügg®ségi kompo< 0, akkor csak ez a partíció F ∈ F partícióra, ha van olyan F -et amelyre F szétbonthatjuk két csúcsokban is diszjunkt F1 = F {F } ∪ {F1 , F2 } ekkor esetben nem növekedett. Ha van olyan F1 -re az összeg F1 , F 2 ∈ F , l-el amelyre V (F1 )∩V (F2 ) 6= ∅, akkor legyen F = F1 ∪F2 és F1 = F {F1 , F2 }∪{F }, ezáltal az összeg l = −k 9. k|V (F1 ) ∩ V (F2 )| + l-el csökken. l k > −1  esetén ez nem növekedés. TÉTEL. Ha Bizonyítás. l1 k1 = l2 k2 ez szigorú csökkenés, , akkor r∨ = r+ 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 l 1 Bizonyítás.

≥ 0 és l2 ≥ 0, akkor r∨ = r+ Ilyenkor a 7. lemma szerint a kétféle (3)-képletben az  egyrészes partíció optimális. 20 http://www.doksihu TÉTEL. Ha 0 ≥ 11. Bizonyítás. l1 k1 ≥ l2 k2 ≥ −1, akkor r∨ = r+ Ilyenkor az 8. lemma szerint a gráf összefügg®ségi kompo-  nensei szerinti partíció optimális mindegyik (3) típusú képletben. TÉTEL. Ha l 12. 1 Bizonyítás. >0> , akkor van olyan G amelyre r∨ 6= r+ 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 ) Legyen E1 l2 k2  szerintiben csak az összefügg®ségi komponensek szerinti. LEMMA. Ha 13. partíció optimális. Ha partíció optimális. Bizonyítás. ≤ −1 és G fa, akkor a l k l k képletben az élenkénti < −1 és G fa, akkor a (3) képletben csak az élenkénti Legyen az optimális partíció F. (3) 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 Bizonyítás. egy n l1 k1 ≥ −1 > l2 k2 , akkor van olyan G amelyre r∨ 6= r+ Ilyenkor van olyan n, amelyre l1 k1 csúcsú kör. Ekkor a 7 és 8 lemmák miatt optimális partíciója az egyrészes. n > − n−1 > Mk1 ,l1 l2 Legyen k2 G szerinti (3) képlet 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 −1 ≥ l1 k1 lesz M∨ M+ és

matroidokban gráfra, amelynek a rangja különböz® > > −2 l2 k2 esetén. Ez a konstrukció egyszer¶ gráfot ad. G Legyen 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∗ l2 k2 > −2 d∗ -ot. miatt a nevez® pozitív. racionális, tehát felírható két egész hányadosaként. A nevez®je legyen l Legyen prím itteni h0 = t0 -hoz, ε 1 {d∗ } m −1 . legyen d∗ S¶r¶n vannak olyan számok, amelyekre ilyen. Ebben a fejezetben valamilyen lineáris függvényét jelöli. Mk2 ,l2 -ben εi h0 t0 . relatív mindig az Egy ilyen gráfban az élenkénti partíció jobb, mint az egyrészes, ellenben kell®en nagy egyrészes partíció jobb, mint az élenkénti. m n-re Mk1 ,l1 -ben az fokszámainak is- 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∗ < ez elég nagy Minden n-re vi teljesül, csúcs di d∗  1 ∗ nd − 1 l2 < 0 2 2k2 + 2 ln2 2k2 + l2 deníciója miatt. fokszámát a kisebb meretében deniáljuk a következ®képpen: 22 index¶ek http://www.doksihu i X id∗ − dj ≤ j=1 1 Legyen  f = 2 d∗ Legyen {v1 , v2 , . , vt } 1 2 az els® néhány csúcs úgy, hogy rájuk éppen ∗ td = t X dj j=1 Feltehet®, hogy Legyen h t = t0 egy indexek szerinti távolság, amely el®fordulhat két számú csúcs között. Ekkor h-ra dd∗ e fok- 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 Vegyünk egy nagy N számot. Legyen h0 n denícióját, h ≥ h0 . 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, ti ≡ 1 (mod N t-vel együtt {N t, t1 , t2 , . , tf } elemei páronként relatív prímek, 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 legnagyobbikának. El®ször minden n legalább N -szerese ugyanezen számok vi -re illesszünk di − 2f sokra ez 1 vagy 2, azokat kössük össze az 23 élt: amelyik csúc- N t-vel utána következ®kkel, kivéve, http://www.doksihu ha ez 1 és korábban összekötöttük az bármely két egymástól nmaradt 2f N tvel el®tte lev®vel. di −2f N t távolságra lev® csúcsra. fokszám. mindet kössük össze az ®t csúcsokkal. Tekintsük a di −2f = 1 csúcsokat. megegyezik Most minden csúcsra fen- t1 , t2 , . tf Ezek között indexre követ® 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 Nt távolságú pontpárok összekötöttségét és össze-nem- kö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 di − 2f = 1 lév® csúcsból a kivezet® mindig hátra mutasson. Ha t0 és hogy N t0 Mk1 ,l1 relatív prím h0 -hoz h0 Nt h0 távolságra élek közül az egyik el®re, a másik relatív prímek, akkor N választható úgy, és ekkor ez megtehet® lesz. -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 Legyen adott egy tetsz®leges Legyen Ha H∈F F optimális partíciója az élenkénti. nomítható partíció. Ezen javítunk egy picit egy nem egyél¶ rész. 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 kétszerese pedig nagyobb nála. 15. TÉTEL. Bármilyen H -t érdemes élekre lebontani 24 d∗ , a jobboldal http://www.doksihu Bizonyítás. Nevezzünk ívnek egy olyan élhalmazt, amelyek azonos in- dextávolságú pontokat összeköt® húrokból álló út élei. Ez az azonos távolság legyen t1 , t2 , . tf H bezáródik, mert akkor lenne. H -ban ti ≡ 1 nem lehet olyan ív, amely kör- az összes pontra illeszkedne, vagyis f minden csúcsra illeszkedik. Mivel H -ban valamelyike. (mod t) H = G darab tartalmazásra nézve maximális ív ezért egy J ív mentén a G-beli ugyanúgy következnek, mint szomszédos pontok esetén, tehát a fokszámok J -beli fok- számok összege X dv = v∈V (J) s+q X s X di − i=1 di ≤ (s + q)d∗ + i=1

Ezt minden tartalmazásra nézve maximális H -beli K íveket is megengedünk. maximális ívek számát. 1 1 − sd∗ + = |V (J)|d∗ + 1 2 2 H -beli jelentse a ívre összegezzük. H -beli 0 él¶ tartalmazásra nézve 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 tartal- mazásra maximális ívnek a folytatása. X dv = v∈H Legyen a H -ból kivezet® Nt X X dv f J⊂H v∈V (J) hosszú élek száma következ®t tudjuk mondani(J ívet jelöl, az összes  m− . H -t H élszámáról a é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 , 2k2 + 2 nlH2 2k2 + l2 Ha d∗ ezzel és dH alsó becsléséb®l  X 1

1 ∗ nH ≤ nH dH ≤ f nH d + − 2 − m− f f J⊂H deníciójából elhagyjuk az 2k2 + 2 nlH2 2k2 + l2 ε-t, akkor fels® becslését kapjuk  X 1 2k2 nH ≤ nH + − 2 − m− 2k2 + l2 J⊂H f 25 d∗ -nak, 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, K az nagy. Legyen Jelölés c= a H tartalmazásra nézve maximális részíveinek száma. l2 2k2 −ε 2 ∗ , ekkor d = = 2+c − ε1 k2 2k2 +l2 l2 3 = c > − 2 Tudjuk, hogy f ≥ k2 1. eset 1 −2 · 32 2l2 > −K − m ≥ = −6 2k2 + l2 2 − 32 k  1 ∗  1 2
 j 1 ε1 f = 2 d = 2 2+c − ε1 ≤ 2− 3 − 2 = 1 és − Ilyenkor a gráfunk olyan, 2 hogy az ívek és az íven kívüli, d∗ < összege legfeljebb 5. 1.a eset 1.ai) eset H -ban 2 2+c H -ra egy végponttal csatlakozó élek számának

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

> 3 ilyenkor c < −2 + d2∗ = − 34 Ebben az esetben minden 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 Nt éllel kapcsolódik hozzá. Ha az egyik széls® másik kett® legalább két-két 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® Nt é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 hosszúságú fül, bomlik, mert 3h0 + 2 ≥ 2h0 + 3 3h + 2 é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 bomlanak, azaz 2h0 + 3 fülek (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 n -nél nem rövidebb ív. 2t1 H ponthalmazának komplemen- 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, elég megmutatni, hogy minden legfeljebb ezek az élek ugyanazok. Ezért 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 feltehet®, hogy tetsz®legesen sok Nt n-ben lineáris. Emiatt él vezet ki bel®le. Lehetnek Nt élek a n n pontjai között is, de mindenképp van az utolsó pontján darab 2t1 2tt1 fokú csúcs, ezek között minden, az íven élenként számolt van irányváltás tehát legalább n-re n darab 2th0 t1 Nt h0 dd∗ e hosszú szakaszon él vezet kifelé. Kell®en nagy 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 függvény lesz, a m¶veletet ismételhetjük, amíg elérjük a 6 ívet. 27 lineáris http://www.doksihu 2. eset c < − 32 , ekkor f ≥ 2   4 1 2c = − 2 = 2d∗ − 2 + ε2 < 4f + 2 K 2− + m− ≤ − f 2+c 2+c 2.a eset Minden H -beli ív rövidebb n -nél. tf 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 s, az ív csúcsszáma akkor ez összesen 1 + s(f − 1) ≥ 4f + 2 2.aii) eset Minden ív legfeljebb 8 csúcsú Ekkor 2.b eset H darab ív. egy fa. n -nél nem rövidebb ív. Ugyanúgy kezelhet® mint az 1b van tf eset. 5.4 Hipergráfok count matroidjai Deníció. Adott H adjuk meg: valamely ahol V (F ) hipergráf F ⊂E E hiperélhalmazán az esetén vegyük az Mk,l count matroidot r∗ (F ) = k|V (F )|+l függvényt, 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®: ( r+ (E1 ) = min F ⊂E1 ,F Ahol a minimumot Mk1 ,l1 ∨ Mk2 ,l2 F |E1 F | + X ) ((k1 + k2 )|V (Fi )| + l1 + l2 ) Fi ∈F összes lehetséges F partíciójára tekintjük. 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 itt a minimumoknál F1 és F2 Szokás szerint kiiktatjuk a Fj ∈F2 halmazcsaládok |E1 F | F összes partícióin futnak. tagot. Ebben a lemmában az a jó, hogy a konstrukciót úgy is meg lehet csinálni, hogy r-gráfunk 16. r-gráfból továbbra is lesz, de vegyes elemszámú hiperélek esetén is igaz marad. LEMMA. r ∨ = r+ pontosan

akkor teljesül minden H hipergráfra, ha bármilyen H1 hipergráf E1 élhalmazára min F  X  = min F1 ,F2 (k1 |V (Fi )| + l1 ) + Fi ∈F  X  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. deti képletben az Ha (5) tetsz®leges hiperélhalmazra teljesül, akkor az ere- |E1 F | -t®l különböz® tagok egyenl®sége miatt a min- imumértékek ezzel a - két képletben azonos - taggal megtoldva egyenl®ek maradnak. Másfel®l, ha adunk egy H0 példát, amelyre (5) nem teljesül, akkor ezt fel- használva megadható olyan hipergráf konstrukciója, amelyre r∨ (H) 6= r+ (H).
t A sima gráfos esetnek megfelel®en lehet a hiperéleket többszörözni vagy r alakú gubancokat ragasztani a hiperélekre. A következ®kben mindenhol a 16. az r∨ és r+ lemma szerinti képletet használjuk,

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 és Mk2 ,l2 szerinti következ® képletben 29 F partíció minden H-ra Mk1 ,l1 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 18. LEMMA. Ha −1 ≤ képletben az egyrészes partíció optimális. Ha l > 0, akkor csak ez a partíció optimális (6) ≤ 0, akkor l k (6) nensenkénti partíció optimális. Ha −1 < optimális. l k -ben az összefügg®ségi kompo< 0, akkor csak ez a partíció TÉTEL. Ha = , akkor r = r 20. TÉTEL Ha l ≥ 0 és l ≥ 0, akkor r = r 21. TÉTEL Ha 0 ≥ ≥ ≥ −1, akkor r = r 22. TÉTEL Ha l > 0 > , akkor van olyan H amelyre r 19. l2 k2 l1 k1 ∨ 1 + ∨ 2 l1 k1 l2 k2 + ∨ + l2 k2 1 ∨ 6= r+ 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 v1 ∈ H1 3, . , Hn−1 3 vn = u csúcsa között egyértelm¶en van v = v0 ∈ H0 3 ismétl®désmentes sorozat felváltva csúcsokból és hiperélekb®l. 23. LEMMA. Ha partíció optimális. Ha partíció optimális. Bizonyítás. ≤ −1 és H fa, akkor a l k l k képletben az élenkénti < −1 és H fa, akkor a (6) képletben csak az élenkénti Legyen az optimális partíció (6) 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 30 < 0. 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 Bizonyítás. 25. l1 k1 ≥ −1 > l2 k2 , akkor van olyan G amelyre r∨ 6= r+ Mint gráfoknál. TÉTEL. Ha l1 k1 < l2 k2 ≤ −1, akkor van oyan hipergráf, amelyen a ma- troidok nem összegz®dnek. Bizonyítás. A [−2, −1] intervallumon s¶r¶n megadtunk elválasztópon- tokat az 5.3 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] 5.5 intervallumba esnek, azt megint megkett®zhetjük, stb. 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 az i-edik Hk,mi ,li +1 -beli hiperélhalmaz független elem, ez pontosan azt

jelenti, hogy 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 Mmi ,li count matroidban Hk,mi ,li Egy k -uniform hipergráfon 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 (m , l ), , (m , l ) olyan egész számpárok, hogy ∀i1 1 t t hányadosok mind egyenl®ek vagy mind re 1 ≤ i ≤ r esetén mi > 0 és az 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 li mi 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