Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

Ramsey-típusú tételek és feladatok

Ramsey-típusú tételek és feladatok

Tóth, Géza


1. Ramsey tétele gráfokra

Középiskolai matematikai versenyek közismert feladata a következő.

1.1. Feladat. Bizonyítsuk be hogy hat ember között mindig van három olyan, akik ismerik egymást, vagy három olyan, akik nem ismerik egymást. (Az ismeretséget kölcsönösnek tételezzük föl.)

A bizonyítás nem nehéz. Legyen A az egyik ember. A maradék öt ember közül A vagy legalább hármat ismer, vagy legalább hármat nem ismer. Tegyük fel, hogy három embert ismer, B -t, C -t és D -t (a másik eset ugyanígy elintézhető). Ha e három ember közül bármelyik kettő ismeri egymást, akkor A -val együtt megvan a három egymást ismerő ember. Ha pedig B , C és D közül semelyik kettő sem ismeri egymást, akkor éppen ők alkotják a keresett hármast.

1. ábra. Nincs teljes négyes és nincs három független csúcs

Vajon igaz marad-e az állítás, ha három helyett négy egymást ismerő vagy egymást nem ismerő embert akarunk találni? Az 1. ábra mutatja, hogy nem. A pontok jelentik az embereket, és két ember pontosan akkor ismeri egymást, ha a megfelelő pontok össze vannak kötve. Nem található az ábrán négy pont úgy, hogy köztük mind a hat él be van húzva, és nincs négy olyan pont sem, amelyek között egyáltalán nincs él (sőt, még három sem!). Ha viszont hat helyett sokkal több, mondjuk száz embert tekintünk, akkor újra igaz állítást kapunk.

1.2. Feladat. Bizonyítsuk be, hogy száz ember között mindig van négy olyan akik ismerik egymást vagy négy olyan akik nem ismerik egymást.

Ezekben a feladatokban a mi szempontunkból az egyetlen érdekes információ az emberekről az, hogy melyik kettő ismeri egymást és melyik kettő nem. Tehát tetszőleges száz tagú társaságot leírhatunk az ismerős párok felsorolásával. Ez éppen az egyszerű gráf definíciója.

Definíció. Legyen V egy véges halmaz, E pedig V elemeiből alkotott párok egy halmaza. A G = ( V , E ) párt egyszerű gráfnak hívjuk, V elemei a gráf csúcsai, E elemei pedig a gráf élei.

Egy gráfot sok esetben érdemes lerajzolni, ahogy az 1. ábrán is tettük, a csúcsokat pontokkal reprezentáljuk, és két pontot pontosan akkor kötünk össze, ha a megfelelő két csúcs egy élet alkot a gráfban. Teljes gráfnak nevezzük azt a gráfot, amelynek bármely két csúcsa össze van kötve. Egy G = ( V , E ) gráfnak G ' = ( V ' , E ' ) a részgráfja, ha V ' ? V és E ' ? E , vagyis G ' minden csúcsa (éle) G -nak is csúcsa (éle). Egy G = ( V , E ) gráfban V ' ? V csúcsai független halmazt alkotnak, ha nem fut közöttük él G -ben.

Ezzel a terminológiával az 1.1. feladat állítása azt mondja ki, hogy minden hat csúcsú gráf tartalmaz egy három csúcsú teljes részgráfot vagy független halmazt.

Legyen R ( k , l ) az a legkisebb R szám, amelyre igaz, hogy bármely R csúcsú gráf tartalmaz egy k csúcsú teljes részgráfot vagy egy l csúcsú független halmazt. (Ha nem létezne ilyen R , legyen R ( k , l ) = ? .) A 1.2. feladat állítása szerint R ( 4 , 4 ) ? 100 . Ramsey híres tétele szerint R ( k , l ) véges minden k , l ? 2 esetén. Más szóval, még a legnagyobb rendetlenségben is találunk egy kis rendet. Hogy pontosan mekkorát, arra a következő eredmény ad becslést.

1.3. Feladat. Bizonyítsuk be, hogy minden k , l ? 2 -re

(i) R ( k , 2 ) = k

(ii) R ( 2 , l ) = l

(iii) R ( k + 1 , l + 1 ) ? R ( k + 1 , l ) + R ( k , l + 1 ) .

Bizonyítás. (i) Ha egy k csúcsú gráf teljes, akkor természetesen tartalmaz egy k csúcsú teljes részgráfot, ha nem teljes, akkor van két pontú független halmaz. A teljes k - 1 csúcsú gráf viszont nem tartalmaz sem k csúcsú teljeset, sem két független pontot.

(ii) Ha egy l csúcsú gráfnak nincs egyáltalán éle, akkor tartalmaz egy k csúcsú független halmazt, ha viszont van éle, akkor van két pontú teljes részgráf. A k - 1 csúcsú él nélküli gráf pedig nem tartalmaz se két csúcsú teljeset, se k független pontot.

(iii) A bizonyítás ötlete ugyanaz mint az 1.1. feladat esetén. Legyen G egy R ( k + 1 , l ) + R ( k , l + 1 ) csúcsú gráf, és legyen v az egyik csúcsa. Ezen kívül még R ( k + 1 , l ) + R ( k , l + 1 ) - 1 csúcs van, tehát vagy van R ( k + 1 , l ) csúcs, amelyekkel össze van kötve v , vagy van R ( k , l + 1 ) csúcs, amelyekkel nincs összekötve v . Tegyük fel, hogy az első eset áll fent, vagyis van v -nek R ( k + 1 , l ) szomszédja. R definíciója szerint a szomszédok között találhatunk vagy egy teljes k - 1 csúcsú részgráfot, ekkor ez v -vel kiegészítve éppen egy k csúcsú teljes részgráfot ad, vagy egy l csúcsú független halmazt, ekkor azonnal készen vagyunk. A másik esetben, ha v -nek R ( k , l + 1 ) nem-szomszédja van, hasonlóan fejezhetjük be a bizonyítást.

Ebből azonnal következik indukcióval, hogy R ( k , l ) ? 2 k + l , sőt, valamivel jobb korlát adódik, de itt nem térünk ki a részletekre, csak néhány speciális esetre.

1.4. Feladat. Bizonyítsuk be, hogy R ( k , 3 ) ? k ( k + 1 ) 2 .

1.5. Feladat. Bizonyítsuk be, hogy az 1.1. feladatban a korlát nem javítható, azaz R ( 3 , 3 ) = 6 .

1.6 Feladat. Bizonyítsuk be, hogy R ( 3 , 4 ) = 9 .

Segítség: Az 1.4. feladat alapján R ( 3 , 4 ) ? 10 , ezt a felső korlátot eggyel kell megjavítani egy kis esetszétválasztással. Az alsó korláthoz kell mutatni egy nyolc pontú gráfot, amely nem tartalmaz sem háromszöget (három pontú teljes részgráfot) sem négy független pontot. Tekintsünk egy szabályos nyolcszöget, és ennek bizonyos húrjait. A húrok felelnek meg a konstruálandó gráf csúcsainak, két csúcsot összekötünk egy éllel, ha a megfelelő húroknak van közös pontja (közös csúcs vagy metszéspont). Megfelelő nyolc húr választásával éppen a kívánt gráfot kapjuk. (Még egy kis segítség: legyenek a húrok egyenlő hosszúak.)

Megemlítjük a Ramsey-tételnek egy általánosabb változatát is.

Általános Ramsey-tétel gráfokra. Tetszőleges k 1 , k 2 , , k m ? 2 számokra létezik olyan R szám, hogy bármely R csúcsú teljes gráf, amelynek az élei m színnel vannak színezve, valamilyen 1 ? i ? m -re tartalmaz egy k i csúcsú teljes részgráfot, amelynek az összes éle az i -edik színnel van színezve.

A feltételt kielégítő legkisebb R számot R ( k 1 , k 2 , , k m ) -mel jelöljük. A bizonyítást nem nehéz rekonstruálni az alábbi feladat általánosításával.

1.7. Feladat. Bizonyítsuk be, hogy minden k ? 2 -re

(i) R ( 2 , 2 , k ) = R ( 2 , k , 2 ) = R ( k , 2 , 2 ) = k .

(ii) R ( k , l , 2 ) = R ( k , 2 , l ) = R ( 2 , k , l ) = R ( k , l ) .

(iii) R ( k 1 , k 2 , k 3 ) ? R ( k 1 - 1 , k 2 , k 3 ) + R ( k 1 , k 2 - 1 , k 3 ) + R ( k 1 , k 2 , k 3 - 1 ) - 1 .

(iv) R ( k 1 , k 2 , k 3 ) ? 3 k 1 + k 2 + k 3 .

1.8. Feladat. Bizonyítsuk be, hogy R ( 3 , 3 , 3 ) ? 17 .

Végül egy még általánosabb változata a Ramsey-tételnek. Eddig „él” alatt csúcsok egy párját értettünk, vagyis egy él két csúcsot köt össze. Az r -uniform hipergráfban egy él egy csúcs r -est jelent.

Definíció. Legyen V egy véges halmaz, E pedig V elemeiből alkotott r -esek egy halmaza. A H = ( V , E ) párt r -uniform hipergráfnak hívjuk, V elemei a hipergráf csúcsai, E elemei pedig a gráf hiperélei.

Általános Ramsey-tétel uniform hipergráfokra. Tetszőleges r ? 2 , k 1 , k 2 , , k m ? r számokra létezik olyan R szám, hogy bármely R csúcsú teljes r -uniform hipergráf, amelynek az élei m színnel vannak színezve, valamilyen 1 ? i ? m -re tartalmaz egy k i csúcsú teljes rész-hipergráfot, amelynek az összes éle az i -edik színnel van színezve.

A feltételt kielégítő legkisebb R számot R r ( k 1 , k 2 , , k m ) -mel jelöljük.

A bizonyításra itt sem térünk ki, hasonló, mint az 1.3. és 1.7. feladatok megoldása, csak jóval bonyolultabb. Nézzünk csak egy speciális esetet.

1.9. Feladat. Bizonyítsuk be, hogy R 3 ( 4 , 4 ) véges.

Segítség: Bizonyítsuk be, hogy R 3 ( 4 , 4 ) ? R ( 3 , 4 ) + 1 = 10 . Tekintsünk egy tíz csúcsú 3-uniform H hipergráfot; be akarjuk bizonyítani, hogy vagy van négy csúcs amelyek között minden hármas szerepel, vagy van négy csúcs amelyek között egyik hármas sem szerepel. Legyen v egy tetszőleges csúcs. A maradék kilenc ponton definiáljunk egy G gráfot a következő szabállyal. Két csúcs, u és w akkor és csak akkor van összekötve G -ben, ha u v w éle H -nak. G tartalmaz vagy egy teljes négyest, vagy egy üres hármast. A többit az olvasóra bízzuk.

1.10. Feladat. Legyen G egy megszámlálható végtelen teljes gráf amelynek csúcsai v 1 , v 2 , = v i i ? 0 egész .

(i) Színezzük ki G éleit két színnel. Bizonyítsuk be, hogy található akármilyen nagy teljes egyszínű részgráf, azaz tetszőleges N -re vannak olyan v i 1 , v i 2 , , v i N csúcsok, amelyek közötti összes él ugyanolyan színű.

(ii) Bizonyítsuk be, hogy található végtelen sok csúcsú teljes egyszínű részgráf, azaz vannak olyan v i 1 , v i 2 , csúcsok, amelyek közötti összes él ugyanolyan színű.

(iii) Bizonyítsuk be, hogy (i) és (ii) állítása igaz marad akkor is, ha kettő helyett tetszőleges r ? 2 színnel színezünk.

Segítség: (i) Közvetlenül következik a véges Ramsey-tételből.

(ii), (iii) Egy észrevételre van szükség, hogy végtelen sok, véges sok színnel színezett él között mindig található végtelen sok ugyanolyan színű. Ennek és a véges Ramsey-tétel bizonyításának alapján már nem nehéz bebizonyítani az állítást.