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

2. Euklideszi Ramsey elmélet

2. Euklideszi Ramsey elmélet

A Ramsey elmélet egyik szép, geometriai vonatkozású ága az Euklideszi Ramsey-elmélet, amelyet elsősorban Erdős, Graham, Montgomery, Rothschild, Spencer és Straus alapoztak meg egy 1975-ös cikksorozatukkal. Az általános kérdés a következő: Egy véges dimenziós euklideszi tér pontjait kiszínezzük véges sok színnel (minden pont egy színt kap), és bizonyos követelményeknek eleget tevő egyszínű konfigurációkat keresünk. A leghíresebb kérdés a máig megoldatlan Hadwiger–Nelson probléma: Hány színre van szükség, ha úgy akarjuk kiszínezni a sík pontjait, hogy ne legyen két, egységnyi távolságra levő pont ugyanolyan színű. A feladat külön érdekessége, hogy a legjobb ismert alsó és felső korlát bizonyítása egyaránt nagyon egyszerű.

2.1. Feladat. (i) (Nelson 1950) Bizonyítsuk be, hogy három színnel színezve a síkot mindig található két egyszínű pont egymástól egységnyi távolságra.

(ii) (Isbell 1950) Mutassunk olyan színezését a síknak hét színnel, amelyben bármely két, egységnyi távolságra levő pont különböző színű.

Segítség: (i) Elég a 2. ábrán látható Moser-gráf csúcsait tekinteni.

2. ábra. Moser-gráf: minden él hossza 1

(ii) Rakjuk ki a síkot egybevágó szabályos hatszögekkel, amelyeknek az átmérője valamivel kevesebb mint egy. Minden hatszöget kiszínezünk a hét szín valamelyikével. Egy hatszögön belül nincs két pont egységtávolságra, és a színek megfelelő (periodikus) választása esetén két egyforma színű hatszög egységnyinél messzebb lesz egymástól.

Természetesen vizsgálták a kérdést magasabb dimenzióban is. A térben a legjobb ismert korlátok 6 (Nechushtan 2000), illetve 15 (Radoièiæ, Tóth 2000), de ezek bizonyítása már nem olyan könnyű, mint a síkbeli legjobb korlátoké. Viszont valamivel gyengébb korlátokat könnyű bizonyítani (néhány éve még ezek voltak a legjobb ismert korlátok).

2.2. Feladat. (i) (Raiskii 1970) Bizonyítsuk be, hogy négy színnel színezve a teret mindig található két egyszínű pont egymástól egységnyi távolságra.

(ii (Székely, Wormald 1989) Mutassunk olyan színezését a térnek 21 színnel, amelyben bármely két, egységnyi távolságra levő pont különböző színű.

Segítség: (i) Általánosítsuk a Moser-gráfot a tér esetére, szabályos háromszögek helyett tekintsünk szabályos tetraédereket. Egy kilenc pontú konfigurációt kapunk, 19 egységtávolsággal a pontok között.

(ii) Tekintsük a 2.1. feladatban kapott színezést, és egészítsük ki a hatszögeket hatszög alapú egyenes hasábokká. Így megkapjuk egy „réteg” színezését, hét színnel. A következő réteget színezzük másik hét színnel, az azutánit a harmadik hét színnel. Ezután már használhatjuk az első hét színt, ha a rétegeket megfelelő vastagságúnak választottuk.

Általában a d -dimenziós tér esetén a legjobb ismert alsó korlát, 1 , 2 d , Frankl és Wilson (1981) híres eredménye. Larman és Rogers (1972) pedig megmutatták, hogy valamivel több mint 3 d szín elegendő.

2.3. Feladat. (i) Bizonyítsuk be, hogy a d -dimenziós teret d + 1 színnel színezve mindig található két egyszínű pont egymástól egységnyi távolságra.

(ii) Legyen d ? 3 . Mutassunk olyan színezését a d -dimenziós térnek d d színnel, amelyben bármely két, egységnyi távolságra levő pont különböző színű.

Segítség: A megoldás nagyon hasonló az előző két feladat megoldásához. (i) Általánosítsuk a Moser-gráfot a d -dimenziós tér esetére, szabályos háromszögek, illetve tetraéderek helyett tekintsünk szabályos egységnyi oldalú szimplexeket.

(ii) Tekintsünk egy d -dimenziós egységoldalú kockarácsot. Minden kocka megfelel egy ( x 1 , x 2 , , x d ) egész szám d -esnek. A színeket is egész szám d -eseknek feleltetjük meg, minden szín egy ( y 1 , y 2 , , y d ) d -es, ahol 0 ? y i ? d - 1 . Ez éppen d d szín. Végül az ( x 1 , x 2 , , x d ) kocka pontjainak a színe legyen ( y 1 , y 2 , , y d ) , ha minden i -re x i ? y i mod d . Könnyen belátható, hogy nincs két egyszínű pont egymástól d + ? távolságra; megfelelő kicsinyítéssel elérhetjük, hogy éppen ez legyen az egységtávolság.

Egy aszimmetrikus változata a Hadwiger–Nelson problémának a következő. Színezzük ki a sík pontjait pirossal és kékkel, és tegyük föl, hogy nincs két piros pont egymástól egységnyi távolságra. Ez valamilyen értelemben azt jelenti, hogy nem lehet „túl sok” pont piros. Milyen egyszínű kék konfigurációkat találhatunk? Például a fentiek alapján nyilván van két kék pont egymástól egységnyi távolságra. Elég egy egységnyi oldalú szabályos háromszög csúcsait tekinteni.

2.4. Feladat. Színezzük ki a sík pontjait pirossal és kékkel úgy, hogy nincs két piros pont egymástól egységnyi távolságra. Legyen T egy tetszőleges háromszög. Bizonyítsuk be, hogy van egy T -vel egybevágó háromszög, amelynek mind a három csúcsa kék.

Segítség: Könnyebb bebizonyítani az állítást, ha T valamelyik oldala legfeljebb 2. Az általános esetben legyen a a T egyik oldalának a hossza, és különböztessünk meg két esetet: van két piros pont egymástól a távolságra, illetve nincs.

Juhász Rozália (1979) bebizonyította, hogy az állítás háromszögek helyett négyszögekre is igaz. Vajon igaz az állítás négy helyett több csúcsú konfigurációkra is? Erdős és társszerzői az említett cikksorozatukban megmutatták, hogy az állítás nem igaz minden 10 12 pontú konfigurációra!

2.5. Feladat. Mutassunk egy olyan piros–kék színezését a síknak és egy olyan K véges pont-konfigurációt, hogy nincs két piros pont egymástól egységnyi távolságra, és nincs K -val egybevágó konfiguráció, amelynek minden pontja kék.

Segítség: Legyen K egy megfelelő méretű négyzetrács megfelelő részlete.

Sikerült kevesebb mint 10 12 csúcsú példát találni? Gratulálunk! Ez már Juhász Rozáliának is sikerült, ő egy 12 pontú példát (és egy megfelelő színezést) talált. Ezt tovább javítottuk Csizmadia Györggyel (1994), egy nyolc pontú példával. Az viszont máig nem ismert, hogy mi az igazság öt-, hat-, és hétszögekre.

2.6. Feladat. Mutassunk olyan színezését a síknak két színnel, amelyben nem található olyan egységnyi oldalú szabályos háromszög, amelynek mind a három csúcsa ugyanolyan színű.

Segítség: Gondoljunk a zebrára.

2.7. Feladat. (i) Legyen T egy egyenlő szárú derékszögű háromszög. Mutassunk olyan színezését a síknak három színnel, amelyben nem található egy T -vel egybevágó háromszög, amelynek mind a három csúcsa ugyanolyan színű.

(ii) Színezzük ki a sík pontjait két színnel. Bizonyítsuk be, hogy van egy T -hez hasonló háromszög, amelynek mind a három csúcsa ugyanolyan színű.

(iii) Színezzük ki a sík pontjait két színnel. Bizonyítsuk be, hogy található három egyszínű pont, A , B és C úgy, hogy B az A C szakasz felezőpontja.

2.8. Feladat. Legyen T egy tetszőleges háromszög. Bizonyítsuk be, hogy van olyan színezése a síknak hét színnel, amelyben nem található olyan T -vel egybevágó háromszög, amelynek mind a három csúcsa ugyanolyan színű.