Ramsey-tétel

A Wikipédiából, a szabad enciklopédiából

Ramsey tétele, melynek névadója Frank P. Ramsey brit matematikus-filozófus-közgazdász, a kombinatorika, de tulajdonképpen a matematika egészének fontos tétele.

A tétel véges formája[szerkesztés]

Ha pozitív egész számok, akkor van olyan (legkisebb) pozitív egész szám, hogy igaz a következő állítás: ha tetszőleges S halmazra és S összes r elemű részhalmazának halmazát s részre bontjuk (s színnel színezzük) akkor valamelyik i-re igaz, hogy van az alaphalmaznak olyan -elemű részhalmaza, aminek összes r elemű részhalmaza az i-edik osztályba esik (i-edik színt kapja).

Az r=1 eset egyszerűen a skatulyaelv: ha egy -elemű halmazt kiszínezzük az színekkel, akkor valamelyik i-re van legalább számú pont ami az i színt kapja.

Minden r-re nyilvánvaló az s=1 eset: .

Az r=2, s=2 eset[szerkesztés]

E speciális eset a tétel legismertebb formája: ha a és b pozitív egész számok, akkor van olyan (legkisebb) R(a,b) pozitív egész szám, hogy ha egy R(a,b) pontból álló teljes gráf éleit kékkel és zölddel színezzük, akkor van teljes a-as kék színben vagy teljes b-es zöld színben.

Már Erdős és Szekeres a következő korlátot nyerte R(a,b) értékére:

.

Ez -re való indukcióval igazolható. Nyilvánvalóan teljesül és . Ha belátjuk, hogy teljesül

akkor a binomiális együtthatókra vonatkozó

azonosság miatt készen vagyunk.

Színezzük tehát egy teljes R(a-1,b)+R(a,b-1)-gráf éleit kék és zöld színnel. Legyen p egy csúcs. Legyen a p-ből kiinduló kék színű élek másik végpontjainak halmaza A, a zöldeké B. Mivel , vagy vagy teljesül. Az első esetben vagy A-ban van egy teljes, zöld színű b-es gráf (amivel készen vagyunk), vagy van egy teljes kék színű a-1-es gráf (ami p-vel egy teljes kék a-ast alkot). A második esetben vagy van egy teljes kék a-as gráf (amivel készen vagyunk) vagy van egy teljes zöld b-1-es (ami p-vel egy teljes zöld b-est alkot).

Erre lényeges javítás csak ötven évvel később született:

Rödl (1986): alkalmas c, d>0 konstansokkal
Thomason (1987):
Conlon (2009):

Ramsey-számok[szerkesztés]

A Ramsey-tételben (és több színre való kiterjesztéseiben) szereplő R(a,b) számokat Ramsey-számoknak nevezik. A tétel bizonyításából adódik egy felső korlát R(a,b) számokra, alsó korlátok pedig máshonnan. Azonban a legjobb alsó korlátok és a legjobb felső korlátok között elég nagy űr tátong. Következésképpen, nagyon kevés a és b számra ismerjük R(a,b) pontos értékét. Az L alsó korlát kiszámítása R(a,b)-re általában a KL‒1 olyan kék-piros színezéséből áll, ami nem tartalmaz kék Ka részgráfot, sem piros Kb részgráfot. Egy Kn gráf összes lehetséges kiszínezésének a vizsgálata hamar számításigényessé válik, ahogy n értéke növekszik; a színezések száma exponenciálisnál gyorsabban növekszik.

Az R(a,b) értékei 11-nél kisebb a és b-kre megtalálhatók a lenti táblázatban. Ahol a pontos érték ismeretlen, az eddigi legjobb alsó és felső korlátokat adjuk meg. R(a,b) értékét, ahol akár a vagy b 3-nál kisebb, megadják az R(1,b) = 1 és R(2,b) = b képletek minden b-re. A Ramsey-számok kutatását Stanisław Radziszowski tekintette át, aki Brendan McKay-jel együtt kiszámította az R(4,5) pontos értékét.

a,b 1 2 3 4 5 6 7 8 9 10
1 1
2 1 2
3 1 3 6
4 1 4 9 18
5 1 5 14 25 43–49
6 1 6 18 36–41 58–87 102–165
7 1 7 23 49–61 80–143 113–298 205–540
8 1 8 28 56–84 101–216 127–495 216–1031 282–1870
9 1 9 36 73–115 125–316 169–780 233–1713 317–3583 565–6588
10 1 10 40–43 92–149 143–442 179–1171 289–2826 ≤ 6090 580–12677 798–23556

Triviális, hogy a táblázat szimmetrikus az átlóra nézve, ezért az áttekinthetőség kedvéért az átló fölötti elemeket elhagytuk.

A táblázat kivonat Stanisław Radziszowski részletesebb táblázatából [1].

Az R(a,a) átlós Ramsey-számok meghatározása a kombinatorika egyik legnehezebb problémája. Ismert, hogy R(3,3)=6 és R(4,4)=18. De R(5,5) pontos értéke már ismeretlen, csak azt tudjuk róla, hogy 43 (Geoffrey Exoo) és 49 (Brendan McKay és Stanisław Radziszowski) között található; hacsak nem találunk az összes eset szisztematikus végigvizsgálásánál lényegesen hatékonyabb eljárást, valószínű, hogy az R(6,6) pontos értéke örökre ismeretlen marad számunkra.

„Képzeljük el, hogy az embernél sokkal hatalmasabb idegen faj landol a Földön, és az R(5, 5) értékét követelik, vagy elpusztítják a bolygót. Ebben az esetben hadra kéne fognunk minden számítógépet és matematikust, hogy megtaláljuk az értéket. De tegyük fel, hogy ehelyett az R(6, 6) értékére kíváncsiak; ebben az esetben minden erőnkkel meg kéne próbálnunk legyőzni őket.”Erdős Pál

Nagy n értékekre a bizonyításból

adódik. Erdős a valószínűségszámítási módszer egyik legelső alkalmazásával igazolta, hogy

Egy hosszú ideig érintetlen Erdős-kérdés volt, hogy lehet-e -re a triviális -nél lényegesen jobb konstruktív alsó becslést adni. Erre először Nagy Zsigmond egy -ös, majd Frankl Péter és Wilson egy -es konstrukciót adott.

Erdős egyik nevezetes sejtése, hogy van olyan c szám, hogy minden -ra elég nagy n esetén

teljesül.

-re a következő ismert:

alkalmas pozitív konstansokra, a felső korlát Ajtai Miklóstól, Komlós Jánostól és Szemerédi Endrétől, az alsó Jeon Han Kimtől ered (1995, ezért az eredményéért 1997-ben Fulkerson-díjat kapott).

R2(3,3,…,3) esete[szerkesztés]

Szavakban ez tehát azt mondja ki, hogy ha egy (s darab 3) szögpontú teljes gráf éleit s színnel színezzük, akkor van egyszínű háromszög. Bebizonyítjuk az és általában az becslést (az első három esetben egyenlőség van). Ehhez definiáljuk az f függvényt az , rekurzióval. r-re való indukcióval bebizonyítjuk, hogy ha éleit r színnel színezzük, van egyszínű háromszög. Ez r=1-re nyilván igaz. Tegyük fel, hogy tudjuk az állítást r-re és adott éleinek egy r+1 színnel való színezése. Legyen p a gráf egy csúcsa, sorra azon további pontok halmaza, amelyek p-be az első, második, …, r+1-edik színben vannak bekötve. Nyilván , ezért van olyan , hogy . Ha pontjai között szerepelne az i-edik szín, akkor van az i színben háromszög. Ha nem, párjait r színnel színezzük, az indukció miatt van tehát egyszínű háromszög.

Végül jegyezzük meg, hogy indukcióval adódik

A tétel érdekes alkalmazása Issai Schur tétele.

r=2, tetszőleges s esete[szerkesztés]

Teljes indukcióval igazolható az

egyenlőtlenség. Ebből viszont az

korlátot kaphatjuk indukcióval.

A tétel végtelen formája[szerkesztés]

Ha s, r pozitív egész számok és f a természetes számok összes r elemű részhalmazainak halmazát s részre bontja (s színnel színezi), akkor van olyan végtelen részhalmaz, aminek minden részhalmaza ugyanabba a részbe esik (ugyanazt a színt kapja).


Ramsey-típusú tételek[szerkesztés]

Tétel[szerkesztés]

Minden 6 pontú gráfban van egy teljes 3-as vagy egy teljes üres 3-as, azaz van 3 olyan pont, hogy bármely 2 között fut él, vagy van 3 olyan pont, hogy közöttük nem fut él.

Bizonyítás[szerkesztés]

Válasszunk ki egy tetszőleges pontot, -et. Ezen kívül még 5 pontunk van, ezekből vagy van 3 olyan pont, amibe vezet él -ből, vagy van 3 olyan pont, amibe nem vezet él -ből. Az első esetben legyenek szomszédai , , . Ha ezek között fut él, például , akkor , , egy teljes 3-ast ad, azonban ha nem fut köztük él, akkor , , egy teljes üres hármas. A második esetben is ugyanígy következik az állítás.

Tétel (Ramsey)[szerkesztés]

Adott k, l pozitív egészekhez létezik egy olyan legkisebb szám, hogy esetén az pontú teljes gráf, éleit két színnel kiszínezve van a gráfban egy első színű vagy egy második színű .

Bizonyítás[szerkesztés]

A következő tétel bizonyításával együtt látjuk be ennek a tételnek a bizonyítását is.

Tétel (Erdős-Szekeres)[szerkesztés]

Bizonyítás[szerkesztés]

Bizonyítsunk indukcióval. Nyilvánvaló, hogy létezik és , és világos, hogy és . Tegyük fel, hogy létezik minden , ahol vagy és vagy és . Emellett indirekt tegyünk fel, hogy , és éleit ki lehet színezni két színnel úgy, hogy a gráfban nincs sem első színű (kék) , sem második színű (piros) . Válasszuk ki egy tetszőleges pontját a gráfnak, -et. Legyenek -ből kiinduló kék élek végpontjai , a pirosaké pedig . Ha nagyobb lenne -nél, akkor a pontok között a feltevés miatt volna vagy egy piros , vagy egy kék , és az utóbbi esetben ehhez hozzávéve -et kék -t kapnánk. Tehát a feltevéseinkből következik, hogy . Ugyanígy kapjuk, hogy . Ekkor viszont , ami viszont ellentmondás. Tehát azt láttuk be, hogy olyan szám, hogy minden nála nem kisebb -re -et színezve lesz a gráfban kék , vagy piros . Ekkor viszont a legkisebb ilyen szám kisebb vagy egyenlő -vel.

Becslések r(k,l)-re[szerkesztés]

Felső becslés[szerkesztés]

Alsó becslés[szerkesztés]

Ha , akkor

Alkalmazások[szerkesztés]

Schur tétele[szerkesztés]

Ha elég nagy, és az első n pozitív egész számot r színnel kiszínezzük, akkor lesz az egyenletnek egyszínű megoldása, azaz olyan számok, amikre áll, és mindegyik egyszínű.

Forrás[szerkesztés]