Matematika | Diszkrét Matematika » Herskovics Dávid - Euklideszi Ramsey Elmélet

http://www.doksihu Euklideszi Ramsey Elmélet Herskovics Dávid Témavezető: Hegyvári Norbert Eötvös Lóránd Tudományegyetem Budapest, 2009 Június http://www.doksihu Tartalomjegyzék 1. Bevezetés 1.1 Megjegyzések 2 3 2. Halmazok, amik Ramsey-k 5 2.1 Minden Ramsey-halmaz szférikus 5 2.2 Ha X és Y Ramsey, akkor X×Y is Ramsey 8 2.3 Függelék 10 3. Szimmetrikus és aszimmetrikus Ramsey 15 4. Egyéb fogalmak és megoldatlan problémák 20 4.1 Sı́kszı́nezések 20 4.2 Szférikus, Ramsey és Gömb-Ramsey 21 4.3 Kromatikus szám 22 1 http://www.doksihu 1. fejezet Bevezetés A Ramsey tételkör alapproblémája a következő: S legyen egy halmaz, F az S részhalmazainak egy családja, r pedig egy pozitı́v egész. A vizsgált kérdés, hogy S bármely C1 ,C2 ,.,Cr

partı́ciójára létezik-e Ci , mely tartalmaz F - beli elemet. A szemléletesség kedvéért S r halmaz partı́ciójára bontását S r szı́nnel való szı́nezéseként (röviden r-szı́nezéseként) szokás tekinteni, ı́gy átfogalmazva a feladatot S tetszőleges r-szı́nezése esetén keresünk egyszı́nű r F -beli elemet. Ha ilyen S bármely r-szı́nezésekor létezik, arra a S F jelölést használjuk. Az euklideszi Ramsey-tételkörben S halmaz egy valahány dimenziós euklideszi tér, F pedig általában egy geometriai tulajdonsággal definiált ponthalmazok családja., leggyakrabban F = Cong(X) = { g·X | g ∈ SO(N)}={X-szel egybevágó ponthalmazok }, ahol X egy E N -beli véges ponthalmaz. 1.01 Definı́ció X véges ponthalmaz Ramsey , ha minden r > 0-ra elég r nagy N esetén E N Cong(X) r r Megjegyzés. Az E N Cong(X) jelölést röviden E N X formában is szokás jelölni, ahol nem okoz

kavarodást. Ezen a ponton felmerülhet, miért csak véges X-eket vizsgálunk, vagy miért csak az X -szel egybevágó halmazokat. Nem juthatunk-e további eredményekre, ha például egy megszámlálható X-et veszünk, és a hozzá hasonló X’-k között keresünk egyszı́nűt? Az alábbi két tétel szerint nem igazán: 1.02 Tétel Minden X Ramsey halmaz véges Bizonyı́tás. (vázlat) A logikai kompaktsági tételt alkalmazva igaziból r azt az erősebb állı́tást bizonyı́tjuk, hogy E N X esetén létezik véges Y r részhalmaza E N -nek, melyre Y X. 2 http://www.doksihu  r 1.03 Tétel (Gallai) E N Hom(X) teljesül minden pozitı́v r-re és véges E N -beli véges X-re, ahol Hom(X) az X ponthalmaz eltolások és nagyı́tások által generált csoportra vett képei ( Hom(X) = { a·X + t }). Egyszerűbben megfogalmazva az akárhány dimenziós teret akárhány szı́nnel kiszı́nezve akármelyik véges

X-re létezik egyszı́nű X’, ahol X’ az X egy kicsinyı́tésének agyı́tásának eltoltja. 1.1 Megjegyzések r 1. Megjegyzés A 102 tétel bizonyı́tása szerint E N X esetén létezik r véges Y részhalmaza E N -nek, melyre Y X. Ez természetesen igaz lesz Y minden eltoltjára is, Y végessége miatt végtelen diszjunkt eltoltja van, amiből r következik, hogy E N X esetén minden r-szı́nezésre végtelen sok az X-szel egybevágó halmaz lesz egyszı́nű. Sőt, Y végessége miatt létezik ε > 0, melyre Y bármely két pontja nagyobb, mint ε távolságra van egymástól. Jelöljünk ki egy tetszőleges irányt, jelölje ennek az (egységhosszú) irányvektorát e. Ekkor Y + t · e, 0 ≤ t ≤ ε/2 kontinuum sok diszjunkt eltoltja Y-nak: ha lenne 0 ≤ t1 < t2 ≤ ε/2, melyre Y + t1 · e és Y + t2 · e metszik egymást, akkor a metszet nem lehet Y-nak ugyanannak a pontjának a két eltoltja, ezért a

háromszög-egyenlőtlenség miatt lenne Y-nak két olyan pontja, amik maximum ε távolságra vannak egymástól, ami ellentmondás. r Így végül azt kaptuk, hogy ha E N X, akkor E N tetszőleges r-szı́nezése esetén kontinuum sok egyszı́nű X-szel egybevágó halmaz lesz. r r 2. Megjegyzés Ha E N X, akkor E N a · X is igaz minden a > 0-ra, hiszen ha E N egy r-szı́nezését 1/a aránnyal középpontosan nagyı́tjuk, akkor is E N egy r-szı́nezését kapjuk, amiben a feltétel szerint van egyszı́nű X-szel egybevágó halmaz. Ennek a halmaznak a középpontos nagyı́tásra vett őse egy egyszı́nű a · X-szel egybevágó halmaz az eredeti r-szı́nezésben. 3. Megjegyzés Felmerülhet a Gallai-tételt látva, hátha a Ramsey halmazok definiciójánál sincs szükség az összes egybevágóság csoportjára, lehet, hogy csak az eltolásokra is ugyanazt kapnánk. Ez sajnos nincs ı́gy A 303 részben

bemutatott módon 2-szı́nezhetjük a sı́kot úgy, hogy ne legyen benne egységoldalú szabályos háromszög, de a későbbiekben látni fogjuk, hogy a szabályos háromszög Ramsey. Emiatt bár egy tetszőleges dimenziós teret 2szı́nezhetünk úgy, hogy a megadott szabályos háromszögünkkel párhuzamos sı́kszeletei ne tartalmazzanak egyszı́nű vele egybevágó halmazt – azaz csak 3 http://www.doksihu az eltoltjai között nincs egyszı́nű –, mégis kellően nagy dimenzió esetén lesz egyszı́nű egységoldalú szabályos háromszög. 4. Megjegyzés Legyen F véges ponthalmazok egy családja Ha minden r r-re létezik olyan E N euklideszi tér, melyre E N F, akkor F-re mondjuk azt, hogy Ramsey-tulajdonságú. Ha F1 ∪ F2 Ramsey-tulajdonságú, akkor F1 és F2 közül legalább az egyik szintén Ramsey-tulajdonságú, ugyanis: Tegyük fel, hogy sem F1 , sem F2 nem Ramsey-tulajdonságú. Ekkor létezik

r, melyre tetszőleges N -re E N -nek van olyan r-szı́nezése, amiben nincs egyszı́nű F1 -beli halmaz, illetve van olyan r-szı́nezése is, amiben nincs egyszı́nű F2 -beli halmaz. Ezt a két szı́nezést összefésüljük egy r2 -szı́nezéssé: két pontnak pontosan akkor lesz azonos a szı́ne, ha mindkét r-szı́nezésben is azonos volt a szı́nük. Ezzel olyan szı́nezését kaptuk tetszőleges E N -nek, melyre nem lesz egyszı́nű F1 ∪ F2 -beli halmaz, tehát F1 ∪ F2 nem Ramseytulajdonságú. S Igyanı́gy kiterjeszthetjük n darab halmazcsalád uniójára is: ha nk=1 Fk Ramsey-tulajdonságú, akkor van i, melyre Fi is Ramsey-tulajdonságú. A triviális esetek kizárására tegyük fel, hogy a halmazcsaládokban csak minimum két pontból álló ponthalmazok vannak. A fenti megállapı́tás szerint ekkor egy véges sok ponthalmazból álló F halmazcsalád nem lehet Ramseytulajdonságú, mert az elemei

uniójaként felı́rva véges sok nem Ramsey-tulajdonságú halmazcsalád uniója. Tehát egy Ramsey-tulajdonságú halmazcsalád csak végtelen lehet. Másik következmény, hogy nem létezik minimális Ramsey-tulajdonságú halmazcsalád, hiszen felbonthatom két nem üres halmazcsalád uniójára, ezekből az egyik szintén Ramsey-tulajdonságú lesz. Sőt, ha úgy bontom fel, hogy az egyik halmazcsalád véges legyen, akkor arról tudom, hogy nem lehet Ramsey-tulajdonságú, tehát a másik az lesz. Ezzel azt kaptuk, hogy ha egy Ramsey-tulajdonságú halmazcsaládból elveszünk véges sok ponthalmazt, attól még Ramsey-tulajdonság megmarad. 5. Megjegyzés Legyen X = { 1,2, , m} Ekkor Gallai tétele szerint r E Hom(X) minden r-re. Hom(X) ebben az esetben az m-hosszú számtani sorozatok halmaza, a kompaktsági tétel szerint létezik véges Y halmaz, melyre r E N Hom(X) , feltehető, hogy Y elemei természetes számok.

Ezzel azt kaptuk, hogy minden m-re létezik W(m), melyre 1,2,3,., W(m) természetes számokat r szı́nnel szı́nezve mindig lesz egyszı́nű m-hosszú számtani sorozat. Ez a Van der Waerden-tétel. 4 http://www.doksihu 2. fejezet Halmazok, amik Ramsey-k A témakör egyszerűen megfogalmazhatósága ellenére meglepően keveset tudunk, mely halmazok Ramsey-k. Ebben a részben a Ramsey-halmazok felépı́tését vizsgálom, felsorolom az ismert elégséges vagy szükséges feltételeket, hogy egy halmaz Ramsey legyen. 2.01 Állı́tás Egy n csúcsú szabályos szimplex Ramsey Következésképpen minden szakasz Ramsey. Bizonyı́tás. Vegyünk egy r·(n-1)+1 csúcsú szabályos szimplexet azonos oldalhosszal, ennek a csúcsait r szı́nnel szı́nezve lesz n darab egyszı́nű. Ezek kiadják a keresett n csúcsú egyszı́nű szabályos szimplexet.  A következő tételhez előbb egy új fogalmat vezetünk be: 2.02 Definı́ció

X ponthalmaz szférikus, ha létezik egy gömb, aminek a felszı́ne tartalmazza X-et. Másképp: létezik x középpont és r sugár, hogy minden y ∈ X-re |y − x| = r. 2.1 Minden Ramsey-halmaz szférikus 2.11 Tétel Minden Ramsey-halmaz szférikus Bizonyı́tás. A tétel ekvivalens átfogalmazását bizonyı́tjuk: ha K nem szférikus, akkor nem is Ramsey Ehhez két lemmát használunk fel 5 http://www.doksihu 1. lemma A K={v0 , v1 , , vk } halmaz nem szférikus ⇔ létezik c1 ,,ck nem mind 0 skalár, melyekre k X ci (vi − v0 ) = 0, (2.1) ci (|vi |2 − |v0 |2 ) = b 6= 0 (2.2) i=1 k X i=1 Bizonyı́tás. Jelöljük az egyszerűség kedvéért |vi |2 -et vi2 -tel Legyen K szférikus, jelölje a gömb középpontját w, a sugarát r. Tegyük fel, hogy 21 teljesül. Ekkor vi2 − v02 = (vi − w)2 − (v0 − w)2 + 2(vi − v0 ) · w = 2(vi − v0 ) · w, amit behelyettesı́tve 2.2-be k X ci (vi2 − v02 ) = 2w · i=1 k

X ci (vi − v0 ) i=1 egyenletet kapjuk, ami – mivel feltettük, hogy 2.1 teljesül –, ezért ez egyenlő 0. Tehát 22 nem teljesül A visszafelé irányhoz tegyük fel, hogy K nem szférikus. K véges, ezért biztosan létezik egy minimális nem szférikus részhalmaza, vegyük ezt K helyett. Feltehetjük tehát, hogy K minimális nem szférikus Minden nem elfajuló szimplex szférikus, ezért a vi − v0 vektorok lineárisan függenek, tehát létezik nem triviális nulla összegű lineáris kombinációjuk. Jelöljük ennek a lineáris kombinációnak az együtthatóit ci -vel, a lineáris függés pont azt jelenti, hogy ezekre a ci -kre teljesül 2.1 A ci együtthatók nem mind 0-k voltak, tegyük fel például, hogy ck 6= 0. A K halmaz minimalitása miatt minden részhalmaza már szérikus, ı́gy Kvk ={v1 , . , vk−1 } is az, jelölje a ráı́rt gömb sugarát r, a középpontját w Ekkor teljesül az

alábbi egyenlet: k X i=1 ci (vi2 − v02 ) = k X ci ((vi − w)2 − (v0 − w)2 ) = ck (vk2 − v02 ) 6= 0 i=1 Ami a 2.2 Ezzel be is láttuk a lemmát 6 http://www.doksihu 2. lemma Legyenek c1 , , ck ,b valós számok, b 6= 0 Ekkor a valós számok r-szı́nezhetők (megfelelő r természetes számra) úgy, hogy k X ci (xi − x0 ) = b 6= 0 (2.3) i=1 egyenletnek nincs egyszı́nű x0 , . , xk megoldása Bizonyı́tás. A dolgozat során később bizonyı́tandó Rado tétel speiális esete (ld. a fejezet végén, a Függelék c részben)  Most, hogy megvannak az eszközeink, következik a tétel bizonyı́tása. K={v0 , . , vk } legyen nem szférikus halmaz, belátjuk, hogy ekkor nem is Ramsey. Ehhez minden n természetes számhoz megadjuk E n egy oyan szı́nezését, amelyikben nincs egyszı́nű K-val egybevágó halmaz. 1. lemma szerint létezik c1 , , ck nem mind 0 valós számok, melyekre 2.1 és 22

teljesül Ezekre a ci valós számokra és a 22-ben szereplő b-re a 2 lemma szerint a valós számoknak létezik olyan r-szı́nezése (megfelelő r-re), melyre 2.3 egyenletnek nincs egyszı́nű megoldása Jelöljük ezt a kitüntetett szı́nezést χ-vel. Fontos érteni, hogy χ egy valós számokon értelmezett, {1,. ,r}-re képező függvény Ezzel a jelöléssel egy v valós szám ”szı́nét” χ(v)-vel jelöljük, hasonlóan szı́nosztályokra a szintén természetesen adódó χ−1 (j), 1 ≤ j ≤ r jelölést alkalmazzuk. A következő lépésként valós számok χ szı́nezése segı́tségével megadjuk n E egy χ∗ szı́nezését, legyen ez χ∗ (v) = χ(v 2 ). Ez az új szı́nezés E n 0 középpontú gömbfelszı́nein konstans, tehát ha K szférikus lenne, akkor elég nagy n-re ezzel a szı́nezéssel biztosan kapnánk K egyszı́nű eltoltját. Azt kell bebizonyı́tanunk, hogy ha K nem

szférikus, akkor erre a szı́nezésre egyetlen n-re sem lesz K-val egybevágó egyszı́nű halmaz. Ennek belátásához az első észrevétel, hogy 2.1 és 22 bármely K-val egybevágó halmazra is teljesül, ráadásul ugyanazokkal a ci együtthatókkal és b-vel: • 2.1 invariáns bármilyen affin leképezésre, tehát speciálisan egybevágóságokra is; • 2.2 invariáns 0 középpontú forgatásokra – hiszen vi2 -ek változatlanok maradnak –, a tetszőleges z-vel való eltolással kapott v0 + z, . , vk + z pon- 7 http://www.doksihu tokra is gyors számolással az alábbit kapjuk: k X ci ((vi +z)2 −(v0 +z)2 ) = i=1 k X k k X X ci (vi2 −v02 )+2z· ci (vi −v0 ) = ci (vi2 −v02 ) = b i=1 i=1 i=1 Ezzel beláttuk, hogy 2.1 és 22 minden K-val egybevágó halmazra is teljesül Legyen K 0 = {v00 , . , vk0 } egy tetszőleges K-val egybevágó halmaz Ha K egyszı́nű lenne, az azt jelentené, hogy χ∗

(v00 ) = · · · = χ∗ (vk0 ), ami χ∗ 0 2 0 2 definiciója szerint χ(x0 ) = · · · = χ(xP ) , 0 ≤ i ≤ k. k ), ahol xi = (vi ) − (v0P k k 0 2 0 2 De az előbbi észrevétel szerint b = c (|v | − |v | ) = i 0 i=1 i i=1 ci · xi = Pk i=1 ci (xi − x0 ), azaz az x0 , . , xk 23 egy egyszı́nű megoldását adnák, ami ellentmond a χ választásának. Következésképp E n olyan szı́nezését adtuk meg, amiben egyetlen K-val egybevágó halmaz se lehet egyszı́nű. Ezt bármely n-re eljátszhatjuk, ı́gy K nem lehet Ramsey. Ezzel a tételt beláttuk.  2.2 Ha X és Y Ramsey, akkor X×Y is Ramsey. 2.21 Tétel Ha X és Y Ramsey, akkor X×Y is Ramsey Bizonyı́tás. Rögzı́tsünk egy tetszőleges r > 1 természetes számot X Ramr sey, tehát létezik m természetes szám, melyre E N X. A bevezetőben emlı́tett kompaktsági tétel szerint létezik T ⊂ E n véges halmazok, melyre r T X. Legyen |T | = t Hasonlóan

létezik olyan n természetes szám és rt S ⊂ E n véges halmaz, melyre és S Y . Legyen |S| = s Vegyük T × S ⊂ E n+m egy tetszőleges r-szı́nezését, jelöljük ezt χvel. Ezt a χ szı́nezést felhasználva készı́tünk T -nek és S-nek olyan r- illetve rt -szı́nezését, melyekben az egyszı́nű X-szel illetve Y-nal egybevágó X’,Y’ direktszorzata egyszı́nű lesz χ szerint. Legyen χ∗ az S rt -szı́nezése megadva a következőképpen: χ∗ (u) = χ∗ (u0 ) , u, u0 ∈ S, akkor és csak akkor, ha χ(v × u) = χ(v × u0 ), ∀v ∈ T − re. Ez valóban egy rt -szı́nezése S-nek, ezért S-ben van Y-nal egybevágó Y’, mely χ∗ szı́nezéssel egyszı́nű – azaz χ∗ -re nézve konstans. Legyen u0 ∈ Y 0 Legyen χ∗∗ a T r-szı́nezése a következő: χ∗∗ (v) = χ(v × u0 ). Ekkor létezik T-ben χ∗∗ -ra konstans, X-szel egybevágó halmaz, jelöljük X’-vel. 8 http://www.doksihu

Állı́tjuk, hogy X’×Y’ konstans lesz χ-re nézve. Valóban, χ∗ választása miatt minden rögzı́tett x ∈ X 0 pontra x× Y’ konstans χ-re, és χ∗∗ választása miatt minden rögzı́tett y ∈ Y 0 -re X’×y is konstans χ-re. Így az egész X’×Y 0 konstans χ-re, ezáltal megadtunk egy euklideszi teret – E n+m –, melynek tetszőleges r-szı́nezésében létezik X×Y-nal egybevágó egyszı́nű halmaz. Tehát X×Y Ramsey  Következmény. Mivel minden szakasz Ramsey (2 csúcsú szimplex), ezért minden tégla is szimplex. Következmény. Bármely tégla csúcsainak részhalmaza is Ramsey 2.22 Tétel Legyen dij 1 ≤ i, j ≤ 4 hat távolság, melyekre teljesül d2ij + d2jk ≥ d2ik minden i,j,k-ra. Ekkor létezik egy 6-dimenziós tégla, melynek 4 csúcsa pont ezeket a távolságokra vannak egymástól. Bizonyı́tás. Konstruktı́van megadunk v1 , v2 , v3 , v4 pontokat úgy, hogy egyrészt egy

6-dimenziós csúcsai legyenek, másrészről a távolságaik pont a megadottak legyenek Ehhez először egy 7-dimenziós tégla csúcsaiként fogjuk keresni az alkalmas vi -ket, innen fogunk következő lépésben 6-dimenziós téglát kapni. v1 = (0, 0, 0, 0, 0, 0, 0), v2 = (0, 0, 0, a4 , a5 , a6 , a7 ), v3 = (0, a2 , a3 , 0, 0, a6 , a7 ), v4 = (a1 , 0, a3 , 0, a5 , 0a7 ). Megmutatjuk, hogy ai -k választhatóak nem negatı́vnak úgy, hogy az egyik 0 lesz (tehát a tégla igaziból csak 6-dimenziós), és a 4 csúcs távolsága rendre dij .A tetraéder mind a hat élére van egyenletünk: d212 d213 d223 d214 d224 d234 = a21 + a23 + a25 + a27 = a22 + a23 + a26 + a27 = a22 + a23 + a24 + a25 = a21 + a23 + a25 + a27 = a21 + a23 + a24 + a26 = a21 + a22 + a25 + a26 9 http://www.doksihu Vizsgáljuk a tetraéder egyik háromszöglapjához tartozó éleket, például az 12, 23,13 éleket,ekkor az alábbi összefüggéseket kapjuk: d223 +

d213 − d212 2 2 d + d223 − d213 a24 + a25 = 12 2 2 2 2 d + d 13 − d23 a26 + a27 = 12 2 a22 + a23 = Ezek a feltétel szerint mind nem negatı́vak, a tetraéder mind a 4 oldalára megcsinálva ezt az összes a2i + a2j (i=3,5,6; j=1,2,4,7) párra kapunk egy nem negatı́v megoldást. Válasszuk ki a legkisebbet, legyen például a21 + a23 Ekkor a1 -et 0-nak választva a többi ai -re kapunk egy egyértelmű nem negatı́v megoldást.  Következmény. Minden nem tompaszögű háromszög csúcsai egy alkalmas tégla csúcsainak részhalmaza, ı́gy minden nem tompaszögű háromszög Ramsey. 2.3 Függelék 2.31 Tétel (Rado) Legyen c1 , , ck és b 6= 0 egy F test elemei Ekkor létezik olyan χ véges szı́nezése az F testnek, melyre k X ci (xi − x0i ) = b (2.4) i=1 egyenletnek nem létezik egyszı́nű x1 , x01 , . , xk , x0k megoldása az F testen Bizonyı́tás. Először belátjuk, hogy elég a tételt F0 = Π(c1 ,

, ck ) testre belátni, ahol Π az F prı́mteste: Tegyük fel, hogy F0 -ra teljesül a tétel, legyen χ egy olyan szı́nezés, amire 2.4-nek nincs egyszı́nű megoldása b=1-re F0 -ban Vegyünk fel egy B Hamelbázist F-re, mint vektortérre F0 felett úgy, hogy b ∈ B legyen A b bázisvektor által kifeszı́tett lineáris altérre vetı́tés egy lineáris művelet, jelöljük xi erre a vetı́tésre vett képét xbi -vel. Ha xi , x0i ∈ F, 1 ≤ i ≤ k megoldása 24-nek, akkor alkalmazva a vetı́tést xbi , x0bi ∈ F0 , 1 ≤ i ≤ k is megoldása 2.4-nek b=1-re a linearitás miatt, ezért nem mind egyszı́nűek χ-re nézve. Legyen 10 http://www.doksihu χ∗ (xi ) = χ(xbi ), ez egy olyan szı́nezése F-nek, melyre 2.4-nek nincs egyszı́nű megoldása. Ezzel beláttuk, hogy elég F0 -ra bizonyı́tani a tételt Ezek után esetszétválasztunk : 0. eset F maga prı́mtest Ha F véges, akkor minden F-beli elemet különböző

szı́nnel szı́nezve már kész is vagyunk, hizsen csak akkor lehetne egszı́nű megoldásunk, ha xi = x0i lenne, de ekkor az összeg 0 lenne, nem pedig b 6= 0. Marad, ha F=Q, a racionális számok teste. Feltehetjük, hogy ci -k és b egészek.PLegyen p egy prı́m, ami nem osztja b-t, M pedig egy elég nagy egész, melyre ki=1 |ci | ≤ M . Legyen a racionális számok χ szı́nezése a következő: χ(x) = χ(y) ⇔ [x] ≡ [y](modp) és [M {x}] = [M {y}], ahol [x] az x egészrésze, {x} a törtrésze. Ez egy M · p-szı́nezés Rövid számolással belátjuk, hogy ha χ(xi ) = χ(x0i ), ∀i-re, akkor xi , x0i , 1 ≤ i ≤ k nem megoldása 2.4-nek: b= k X ci (xi − x0i ) = k X i=1 ci ([xi ] − [x0i ]) i=1 + k X ci ({xi } − {xi − x0i }), i=1 az első tagja a jobboldali összegnek osztható p-vel, ezért nem egyenlő b-vel. A második tag abszolút értékére adunk egy felső becslést: | k X i=1 ci ({xi } − {x0i

})| ≤ k X |ci ||M {xi } − M {x0 }| i M i=1 < k X |ci | i=1 M ≤ 1. Ez ellentmondás, hiszen az első tag egész volt, ı́gy minimum 1-gyel tért el b-től. 1. eset Transzcendens bővı́tésre Tegyük fel, hogy egy F testre teljesül a tétel, belátjuk, hogy ekkor minden F(y)-ra is, ahol y transzcendens F felett. A ci -k és b F(y)-beliek, azaz előállnak . , y −2 , y −1 , y, y 2 , közül végesnek az F feletti lineáris kombinációjaként, ezért ha felszorozzuk a ci -ket és b-t egy megfelelően nagy y-hatvánnyal – ami a linearitás miatt úgyse rontja el az egyenlőséget –, tekinthetjük őket F[y]-beli polinomoknak. Első észrevételként feltehetjük,hogy b(0) 6= 0. Ha F végtelen test, akkor y helyett használhatunk y − a-t bármely a ∈ F -re, hiszen F(y)=F(y-a), ugyanazt a testet kapjuk. A b polinom viszont eltolódik a-val, ı́gy b(0) most b(a) lesz. Mivel b 6= 0 volt F-ben, ezért b(y) egy nem

0 fokú polinom lesz, aminek van nem 0 értéke, ı́gy a választható úgy, hogy b(a) 6= 0 legyen. Ha F véges, akkor vehetjük egy F’ véges bővı́tését úgy, hogy b(y) polinom nem mindenhol nulla legyen F’-n, és y helyett ismét y − a-t veszünk egy alkalmas a-val. 11 http://www.doksihu P j Legyen m = max1≤i≤k deg ci (y) és ı́rjuk a ci polinomokat ci = m j=1 cij y 0 alakban. Az xi , xi ∈ F (y) elemek is felı́rhatók véges sok y-hatványok (akár negatı́v kitevős is) F feletti lineáris kombinációjaként, ezért őket Laurentsorként tekintjük az alánni alakban: xi = ∞ X ∞ X j dij y + j=1 ∞ X x0i = j=1 d0ij y −j j=0 eij + ∞ X e0ij y −j , j=0 ahol a jobboldali összegben csak véges sok nem nulla tag van, dij , d0ij , eij , e0ij ∈ F. Most feltéve, hogy az xi , x0i elemek megoldásai 2.4-nek, behelyettesı́thetjük őket az egyenletbe, csak a konstans tagot nézve a következőt

kapjuk: k X m X cij (d0ij − e0ij ) = b(0) 6= 0. i=1 j=0 Ebben az egyenletben már csupa F-beli elem van, ezzel visszavezettük az eredeti egyenletet és annak megoldásait egy F feletti egyenelet F-beli megoldásaira. Ez utóbbira a kezdeti feltevés szerint van olyan χ szı́nezése F-nek, amelyre nincs egyszı́nű d0ij , e0ij megoldása az egyenletnek. Ezzel a χ szı́nezéssel definiálunk F(y)-on χ∗P szı́nezést, ami kielégı́ti a tételt: minden x ∈ F (y) P∞ is egy 0 −j j alakban, az x χ∗ szerinti ”szı́nét” a felı́rható x = j=1 aj y + ∞ j=0 aj y következő ”szı́nkód” határozza meg: χ∗ (x) = (χ(a0 ), . , χ(am )) Ez megegyezik azzal, hogy két F(y)-beli elem pontosan akkor lesz azonos szı́nű, ha a Laurent-soruk főrészének együtthatói megegyeznek. Ez a fenti F-re való visszavezetés miatt azt jelenti, hogy nem lesz egyszı́nű megoldás. 2. eset Véges bővı́tés Most feltesszük, hogy

a tétel teljesül F testre, és belátjuk, hogy ekkor egy L véges bővı́tésére is teljesülni fog. Legyen |L : F | = d, és ω1 , . , ωd az L egy bázisa F felett Ekkor a ci , xi , x0i , b L-beli elemeket felı́rhatjuk az ωi -k lineáris kombinációjaként: 12 http://www.doksihu ci = d X cij ωj , j=1 xi = d X aij ωj , j=1 x0i = d X a0ij ωj , j=1 b= d X bj ωj , b1 6= 0 j=1 továbbá ω α ωβ = d X λαβγ ωγ , λαβγ ∈ F. γ=1 Mindent visszahelyettesı́tünk 2.4-be, de csak az ω1 együtthatóit nézzük: k X d X d X λαβγ ciα (aiβ − a0iβ ) = b1 6= 0. i=1 α=1 β=1 A kezdeti feltevés szerint létezik χ szı́nezése F-nek, hogy ennek nincs megoldása, melyre χ(aiβ = χ(a0iβ , 1 ≤ i ≤ k, 1 ≤ β ≤ d)). Ekkor L χ∗ szı́nezését ismét ”szı́nkóddal” adjuk Pd meg, csak úgy,∗ mint az 1. esetben: minden x ∈ L -et felı́runk x = j=1 aj ωj lakban, χ (x) = (χ(a1 ), . ,

χ(ad )) Ezzel az eddigiek alapján olyan szı́nezést kaptunk L-ben, amire 24-nek nincs egyszı́nű megoldása. Ezzel a tételt beláttuk.  Most már teljes a bizonyı́tásunk arra a tételre, hogy minden Ramsey halmaz szférikus, és azt is láttuk, hogy minden tégla csúcshalmaza, vagy annak egy részhalmaza (például a nem tompaszögű háromszögek) Ramsey-k. Szintén Ramsey-halmazok a szabályos szimplexek. A következő kérdés, ami adná magát, vajon egy szabályos n-szög Ramseye? A kérdés elemi jellege ellenére sokáig eldöntetlen maradt, végül Kr̆iz̆ egyáltalán nem elemi tétele adott rá választ: 13 http://www.doksihu 2.32 Tétel (Kr̆iz̆) Ha X szimmetria csoportja tranzitı́v és feloldható, akkor X Ramsey Jelenleg is ez minden, amit a Ramsey-halmazokról tudunk. 14 http://www.doksihu 3. fejezet Szimmetrikus és aszimmetrikus Ramsey Ebben a fejezetben olyan tı́pusú tételekből mutatok be

egy-egy példát, amelyek tetszőleges 2-szı́nezésekre tesznek alábbi tı́pusú állı́tásokat: - Ha a sı́kon van egyszı́nű A, akkor van egyszı́nű B is (szimmetrikus eset). - Ha a sı́kon nincs kék A, akkor van piros B (aszimmetrikus). 3.03 Tétel Ha a sı́k egy 2-szı́nezésekor (legyen kék és piros) van egyszı́nű d oldalú szabályos háromszög, akkor minden olyan háromszög is előfordul ebben a szı́nezésben egyszı́nűként, amelyiknek van d hosszú oldala. Bizonyı́tás. Legyen az egyszı́nű (például kék) d oldalú szabályos háromszögünk ABC A keresett d oldalú háromszöget jelöljük T-vel A bizonyı́tás folyamán elemien végiggondoljuk, hogy ha el akarjuk kerülni, hogy legyen egyszı́nű T, akkor mely pontokat milyen szı́nre kell szı́nezni, amiből aztán mégis kijön egy egyszı́nű T. Nézzük a 31 ábrát Az ABE, DBC, GFC, EFH, ACH, DEG háromszögek mind

egybevágóak T-vel, ezért ha A,B,C kékek, akkor az egyszı́nű T-t elkerülendő ezek nem lehetnek egyszı́nű háromszögek. Ebből máris kijön, hogy D és E is piros (ABE és DBC háromszögekből), amiből G kék (DEG), amiből F piros (GFC), következésképpen H kék (EFH), amiből viszont ACH háromszög kék lesz. Ezzel kész vagyunk.  3.04 Tétel Ha a sı́k egy 2-szı́nezésekor van olyan d távolság, hogy nincs két kék pont egymástól d távolságra, akkor bármely T = {t1 , t2 ,3 } 3 elemű halmaznak létezik piros eltoltja. 15 http://www.doksihu 3.1 ábra 16 http://www.doksihu 3.2 ábra Bizonyı́tás. Legyen M az ábrán látható gráf (32) Legyen az M-ben minden él hossza d Ha a sı́kon nincs két kék pont egymástól d távolságra, akkor ti + M -ban csak két kék pont lehet minden i-re, amiből következik, hogy van olyan m ∈ M , melyre T + m piros.  Megjegyzés. A fenti M

gráfot Moser-gráfnak hı́vják Itt azt a tulajdonságát használtuk ki, hogy minden éle ugyanolyan hosszú (feltehetjük, hogy egység), és ha már három kék pontunk van benne, akkor ebből lesz kettő szomszédos. A 43 részben bemutatom a Moser-gráf egy általánosı́tását, amelyik ugyanezekkel a tulajdonságokkal bı́r N dimenzióban és 2N + 3 pontra Ezzel az általánosı́tott Moser-gráffal a fenti tétel nem csak sı́kra, hanem tetszőleges E N -re is kimondható: 3.05 Tétel Adva van E N egy 2-szı́nezése Ha ebben egy tetszőleges d távolságra nincsen két kék pont egymástól d távolságra, akkor tetszőleges T = {t1 , . , tN +1 } N+1 elemű halmaznak létezik piros eltoltja 17 http://www.doksihu Most ezt a tételt fogjuk tovább általánosı́tani nem csak két szı́nre és nem csak két pontú halmaz tiltására egy szı́nben. A tétel bizonyı́tásához azt használtuk ki, hogy van

véges halmazok olyan sorozata (jelen esetben MN ), melyre a halmaz elemszáma ”lényegesen” gyorsabban nő, mint a legnagyobb olyan részhalmazának elemszáma, melyben nincs két pont egységtávolságra. Ezt a gondolatot fogjuk kiterjeszteni általánosabb esetre: Legyen T = {t1 , . , tk } egy (valamilyen E N -beli) véges ponthalmaz Szı́nezzük E N -t 2-szı́nnel, úgy hogy az egyik szı́nben ne legyen T-vel egy0 bevágó halmaz. Tetszőleges G (valamilyen E N -beli) véges halmazra jelöljük MT (G)-vel azt a számot, ahány pontot maximum kiválaszthatunk G-ből úgy, hogy a kiválasztott pontok között ne legyen T-vel egybevágó. Ekkor 0 tetszőleges k-elemszámú K halmazra, ha k · MT (G) < |G|, akkor E max(N ;N ) t úgy 2-szı́nezve, hogy az egyik szı́nben nem lesz T-vel egybevágó halmaz, a másik szı́nben lesz K-nak eltoltja. Ez ugyanaz a logika szerint működik, mint az elején emlı́tett tételben |T | =

2-re: nézzük K + G-t, ha az egyik szı́nben (kék) nincsen T-vel egybevágó halmaz, akkor ∀k ∈ K-ra k + G-ben maximum MT (G) darab kék pont lehet, amiből következik, hogy K + G-ben maximum k ·Gk . Ha k · MT (G) < |G| teljesül, akkor lesz olyan g ∈ G, melyre K + g piros. Ennek következménye, hogy ha egy adott T véges halmazra találunk olyan n n| ∞, akkor Gn , n = 1, 2, . véges ponthalmazok sorozatát, melyre M|G T (Gn ) minden k-ra lesz olyan N, hogy E N -t 2-szı́nnel szı́nezve vagy lesz T-vel egybevágó kék halmaz, vagy lesz tetszőleges k-elemű halmaznak piros eltoltja. Most tegyük fel, hogy egy adott T véges halmazhoz létezik ilyen Gn r sorozat, ráadásul valamilyen r és N természetes számokra E N T . Ekkor 0 r+1 igaz lesz az is, hogy valamilyen alkalmas N’-re E N T : r r Ha E N T , akkor létezik véges Y ⊂ E N , melyre Y T . Legyen 0 |Y | = k. Ekkor létezik olyan N’, hogy E N -t 2-szı́nezve vagy

lesz benne kék 0 T 0 ∈ Cong(X) vagy Y piros eltoltja. Nézzük E N egy (r+1)-szı́nezését, erre 0 tekinthetünk 2-szı́nezésként is: az első szı́n kék, a többi piros. Ekkor E N ben vagy lesz kék T-vel egybevágó halmaz, vagy piros Y eltoltja Visszatérve az eredeti (r+1)-szı́nezéshez azt kapjuk, ha nincs 1 szı́nben T-vel egybevágó r halmaz, akkor van r szı́nnel szı́nezett Y eltolt, amiből Y T miatt lesz 0 r+1 egyszı́nű T-vel egybevágó halmaz. Tehát E N T r Mivel r = 1-re mindig teljesül E N T , ezért ezzel a következőt kaptuk: Ha T véges halmazhoz létezik Gn véges halmazok olyan sorozata, n n| melyre M|G ∞, akkor T Ramsey. T (Gn ) 18 http://www.doksihu Megjegyzés. Ugyanehhez az eredményhez a Ramsey tulajdonság definı́ciójából közvetlenül is eljuthatunk Ha egy X halmaz nem Ramsey, akkor létezik r természetes szám, melyre bármely E N -nek van olyan r-szı́nezése, melyben nincs

egyszı́nű X 0 ∈ Cong(X). Ebből következik, hogy minden véges G halmaznak is lesz ilyen r-szı́nezése. Egy ilyen szı́nezésben van olyan pont van, tehát MX|G|(G) ≤ r lesz minden X nem szı́n, amiben mininum |G| r Ramsey halmazra és G véges halmazra. Ez ugyanaz az állı́tás (csak másik irányból), mint fent. 19 http://www.doksihu 4. fejezet Egyéb fogalmak és megoldatlan problémák 4.1 Sı́kszı́nezések Ebben a részben a sı́k szı́nezéseivel, elsősorban 2-szı́nezéseivel fogunk foglalkozni. A legegyszerűbb halmaz a két pont, de ezt az esetet a kromatikus szám fejezetben fogjuk tárgyalni. Így a következő legegyszerűbb eset az egységoldalú szabályos háromszög. Első fontos észrevétel, hogy a sı́knak van olyan 2-szı́nezése, melyben nincs egyszı́nű egységoldalú szabályos √háromszög:√ a sı́kot ”sávosan” szı́nezzük, (x,y) pontot kék lesz, ha x ∈ [2n 23 , (2n +

1) 23 ), piros különben. 1. Sejtés (100$) A sı́kot tetszőlegesen 2-szı́nezve egy d távolságot leszámı́tva minden d0 6= d-re lesz egyszı́nű d0 oldalú szabályos háromszög. Ez a sejtés a 3.03 miatt lesz érdekes számunkra, hiszen nem szabályos háromkszögnek van két különböző hosszúságú oldala, tehát bármely 2-szı́nezésnél az egyikkel megegyező oldalhosszúságú egyszı́nű szabályos háromszög, amiből 3.03 szerint: 2 2. Sejtés Minden T nem szabályos háromszögre E 2 T Amennyiben megengedünk végtelen szı́nezéseket, akkor lehetőségünk van érdekes halmazelméleti tételeket is megfogalmazni: 4.11 Tétel (Kunen) Ha feltesszük a Kontinuum Hipotézist, akkor létezik a sı́knak olyan ℵ0 -szı́nezése, melyben nem lesz egyszı́nű racionális területű háromszög. 20 http://www.doksihu 0 g·alap Bizonyı́tás. Transzfinit rekurzióval Egy háromszög

területe magassa , 2 tehát ha van két például kék pontunk egy e egyenesen, akkor az a feltétel, hogy ne legyen egyszı́nű racionális területű háromszög, az megszámlálhatóan sok e-vel párhuzamos egyenesről zárja ki a kék pontokat. Ha már megszámlálhatóan sok pontot kiszı́neztünk, akkor ezzel megszámlálhatóan sok azonos szı́nű pontpárt kaptunk, ezáltal a további szı́nezésekre nézve megszámlálhatóan sok egyenesre van megkötésünk, hogy egy adott szı́nben nem lehet rajta pont. Nevezzük ezeket az egyeneseket valamilyen szı́nt ”tiltónak”, hiszen egy következő pont kiszı́nezésével pontosan akkor képezünk racionális területű háromszöget, ha a pontot olyan szı́nűre festjük, amilyen szı́nt tiltó egyenesen volt a pont. Először azt látjuk be, hogy megszámlálhatóan sok pontot ki lehet úgy ℵ0 szı́nezni, hogy a sı́k minden pontján maximum véges

sok szı́nt ”tiltó” egyenes menjen át. Ez triviális, elég például az összes pontot különbözőre szı́nezni Ebből már következik a tétel. Ha már megszámlálhatóan sok pontot kiszı́neztünk a fenti módon, akkor veszünk a sı́kon egy még ki nem szı́nezett pontot. Azon csak véges sok szı́nt ”tiltó” egyenese mehet át, emiatt ki tudjuk szı́nezni, anélkül,hogy egyszı́nű racionális területű háromszöget képeznénk. Az új ponttal új ”tiltó” egyeneseket is kaptunk, de mivel ezek mind egy szı́nt tiltanak, ezért a minden pontban továbbra is véges sok szı́nt tiltunk csak. Így transzfinit rekurzióval igazoltuk, hogy megszámláhatónál nagyobb ponthalmazt ki tudunk úgy szı́nezni, hogy ne legyen benne egyszı́nű racionális háromszög. Ez a Kontinuum Hipotézist feltéve azt jelenti, hogy kontinuum ponthalmazokat is, ı́gy az egész sı́kot is.  Ennél erősebb

tétel: 4.12 Tétel (Erdős) A Kontinuum Hipotézis ekvivalens a sı́k egy olyan ℵ0 -szı́nezésének létével, amiben nem lesz egyszı́nű derékszögű háromszög. 4.2 Szférikus, Ramsey és Gömb-Ramsey Azt már korábban láttuk, hogy minden Ramsey halmaz szférikus. Nyitott kérdés, hogy ez visszafelé is igaz-e, azaz minden szférikus-halmaz Ramsey-e. 3. Sejtés (1000$) Minden szférikus halmaz Ramsey A kérdés nehézségét mutatja, hogy már az egyik legegyszerűb |K| = 4 sı́kbeli esetre sincs még válasz: 21 http://www.doksihu 4. Sejtés (100$) Egy körön négy pont az Ramsey 4.21 Definı́ció Egy X halmazt gömb-Ramsey-nek nevezünk ha minden r természetes számhoz létezik olyan N temészetes szám és r valós szám, melyekre az N dimenziós r sugarú gömb felszı́nét bárhogy r-szı́nezve lesz egyszı́nű X’∈Cong(X). Ez hasonló tı́pusú definició, mint a Ramsey halmazoknál,

csak itt E N egy alkalmas részcsoportjára nézzük az r-szı́nezéseket. Ebből adódik, ha egy halmaz gömb-Ramsey, akkor a halmaz Ramsey Visszafelé is felmerül a kérdés, ha egy halmaz Ramsey, abból következik-e, hogy gömb-Ramsey is? 5. Sejtés (1000$) Minden Ramsey halmaz gömb-Ramsey Megjegyzés. Egy szabályos szimplex mindig beı́rható egy gömbbe, ezért ugyanazt a bizonyı́tás, amivel az egész téren bizonyı́tottuk, hogy egy szabályos szimplex Ramsey, ugyanaz a bizonyı́tás megfelelő mérető és dimenziós gömbön is működik, ezért minden szabályos szimplex egyben gömb-Ramsey is. Speciálisan bármely szakasz két végpontja is gömb-Ramsey. Megjegyzés. Minden N-dimenziós gömb belefoglalható egy nagyobb dimenziós gömbbe Sőt, bármely két gömb direktszorzata is belefoglalható egy elég nagy dimenziós gömbbe. Ezzel a megfigyeléssel a ”két Ramsey direktszorzata is Ramsey”

tételre adott bizonyı́tás gömb-Ramsey halmazokra is ugyanúgy működik, tehát két gömb-Ramsey halmaz direktszorzata is gömbRamsey. Speciálisan ekkor bármely k db szakasz végpontjainak direktszorzata is gömb-Ramsey, tehát minden tégla csúcshalmaza is Ramsey. 4.3 Kromatikus szám Arra a szabályos háromszög esetében korábban is láttunk példát, hogy egy K halmazra egy N dimenziós térnek volt olyan r-szı́nezése, ahol nem volt egyszı́nű K 0 ∈ Cong(K), de az N+1 dimenziós tér minden r-szı́nezése már tartalmazott ilyen egyszı́nű K’-t. Ebből kiindulva a gráfokhoz hasonlóan bevezethetünk az euklideszi terek egy tulajdonságát, a kromatikus számot. Célszerű ehhez a lehető legegyszerűbb K ponthalmazt venni, nevezetesen két pontot egység távolságra. 22 http://www.doksihu 4.31 Definı́ció Egy E n tér kromatikus számának nevezzük azt a legkisebb r természetes számot,

melyre E n -nek létezik olyan r-szı́nezése, ami nem tartalmaz két egyszı́nű egységtávolságra lévő pontot. Jelölje E N kromatikus számát χ(E N ). Megjegyzés. Ha E N -nek van olyan r-szı́nezése, melyben nincs két egyszı́nű egységtávolságra lévő pont, akkor egy d-szeres nagyı́tást végezve E N -nek olyan r-szı́nezését kapjuk,melyben nincs két egyszı́nű a távolságra lévő pont. Tehát a kromatikus szám definı́ciójában szereplő egységtávolság csak konvenció, helyette bármilyen más a távolságot is beı́rhattunk volna. Ebből kiindulva a fenti definı́ciónak felı́rható egy másik, vele ekvivalens változata: 4.32 Definı́ció Egy tér kromatikus számának azt a legkisebb r természetes számot nevezzük, amiben nem minden d távolság fordul elő egyszı́nű pontok távolságaként. r Ez a definició hasonlı́t a bevezetőben az E N X-re addot ekvivalens

definicióra. 4.33 Állı́tás A kromatikus szám létezik minden E N -re Bizonyı́tás. Elég belátni, hogy minden E N -nek van véges szı́nezése, mely√ ben nincs két egyszı́nű egységtávolságú pont. E N -ben vegyünk fel egy 1/2 N oldalhosszú kockarácsot. Ebben egy kocka átmérője 1/2 lesz. Vegyünk √ √ N (2[ N ]+2) kockát, amik együtt egy 2[ N ]+2 kiskocka élű nagykockát adnak. Ezeket mind különböző szı́nűre szı́nezzük, majd ezt a szı́nezést mindig eltolva a szomszédos nagykockára a kockarács többi kockáját is ciklikusan kiszı́nezzük – a kockák lapjait, amik több szomszédos kockához is tartoznak, tetszőlegesen választjuk ki, melyik kockához tartozónak tekintjük. Ezzel olyan véges szı́nezését kaptuk a kockarácsnak, ahol egy kockához a legközelebbi √ azonos szı́nű kocka ”2[ N ] + 1 kocka távolságra” van, ami több, mint 1 távolság. Ekkor

két azonos szı́nű pont vagy ugyanabban a kockában van – ekkor a távolságuk kisebb,mint egy –, vagy különbözőben – és ekkor a távolságuk nagyobb, mint egy.  Megjegyzés. Az E N kromatikus száma minimum N+1 Vegyünk egy N+1 csúcsú szabályos egységoldalú szimplexet E N -ben, ezt N-szı́nnel szı́nezve lesz kettő azonos szı́nnel, ezek egységtávolságra vannak egymástól 4.34 Állı́tás 4 ≤ χ(E 2 ) ≤ 7 23 http://www.doksihu 4.1 ábra Bizonyı́tás. Az alsó határ onnan jön, hogy a Moser-gráf (M) kromatikus száma 4, a tartalmazás miatt 4 = χ(M ) ≤ (E 2 ). A felső határhoz a sı́kot bontsuk fel 1 − ε átmérőjü hatszögek diszjunkt uniójára – hogy az élek és a csúcsok melyik hatszöghöz tartozzanak, azt tetszőleges eldönthetjük. Ekkor elég kicsi ε-ra két pont csak akkor lehet egységtávolságra eymástól, ha két olyan különböző hatszögben

vannak, amelyek között egy hatszög van köztük (”egy hatszög távolságra vannak”). A hatszögeket jól 7-szı́nezve (lásd a 4.1 ábra) olyan szı́nezést kapunk, ahol bármely két azonos szı́nű hatszög egymástól minimum ”két hatszög” távolságra van egymástól, ami több, mint 1. Ezzel olyan szı́nezést kaptunk, melyben nem lesz két egségtávolságra lévő pont egyszı́nű.  Érdemes nézegetni itt egy kicsit még az alsó becslés bizonyı́tását, azon belül is a Moser-gráfot. A Moser-gráf ”lényege”, hogy egy alkalmas kicsi részhalmazzal belátjuk, hogy ha sı́kot ki lehet szı́nezni 3 szı́nnel úgy, hogy ne legyen két azonos szı́nű pont egységtávolságra, akkor egy alkalmas d távolságra bármely két egymástól d távolságra lévő pontnak azonos szı́nűnek kell lennie. Ekkor 24 http://www.doksihu viszont felrajzolhatunk egy egyenlőszárú

háromszöget, ahol az alap 1, a szárak pedig d hosszúak, ennek minden csúcsának azonos szı́nűnek kéne lennie, azaz lenne egységtávolságra két azonos szı́nű pont. Ezt általánosı́thatjuk N dimenzióra is, ı́gy az előbbi megjegyzésben szereplőnél eggyel jobb általános alsó korlátot kapunk: 4.35 Állı́tás Az E N kromatikus száma minimum N+2 Bizonyı́tás. E N -ne egy N csúcsú egységoldalú szabályos szimplexet két ponttal is kiegészı́thetünk egy N+1 csúcsú szabályos szimplex-szé. Álljon MN az N csúcsú szimplexből és ebből a két pontból. Ha úgy akarjuk kiszı́nezni a MN -t N+1 szı́nnel, hogy ne legyen két azonos szı́nű egységtávolságra lévő pont, akkor ez a két utóbbi pont azonos szı́nű kell, hogy legyen. Ezzel a kontrukcióval beláttuk, hogy ha E N -t úgy akarjuk kiszı́nezni N+1 szı́nnel, hogy ne legyen benne egységtávolságra azonos szı́nű

pontok, akkor alkalmas d távolságra, minden egymástól d távolságra lévő pontnak azonos szı́nűnek kell lennie. Ez ellentmondás, mint ahogy fent láttuk  25 http://www.doksihu Felhasznált irodalom: [1] P. Erdős - RL Graham - P Montgomery - BL Rotschild - J Spencer, E.G Straus: Euclidean Ramsey Theorems I, JOURNAL OF COMBINATORIAL THEORY (A) 14, 3 4 1 -363 (1973) [2] P. Erdős - RL Graham - P Montgomery - BL Rotschild - J Spencer EG Straus: Euclidean Ramsey Theorems II, COLLOQUIA MATHEMATICA SOCIETATIS JÁNOS BOLYAI 10 INFINITE AND FINITE SETS, KESZTHELY (HUNGARY), 1975. [3] R. L Graham: Topics in Euclidean Ramsey theory, Mathematics of Ramsey Theory, Springer-Verlag, New York (1990) [4] R.L Graham: Open problems in Euclidean Ramsey Theory, University of California, San Diego La Jolla CA 92093-0114 [5] R.L Graham: Euclidean Ramsey Theory, http://wwwmsriorg/publications/ln/msri /2003/introdcgeom/graham/1/banner/30.html [6] R.L Graham: Some of my favorite

problems in Ramsey Theory, ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7(2) (2007) 26