Ramsey-tétel

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

Ramsey tétele, melynek névadója F. 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 | forrásszöveg szerkesztése]

Ha r,k_1,\dots,k_s pozitív egész számok, akkor van olyan (legkisebb) R_r(k_1,\dots,k_s) pozitív egész szám, hogy igaz a következő állítás: ha tetszőleges S halmazra |S|=R_r(k_1,\dots,k_s) é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 k_i-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 R_1(k_1,\dots,k_s)=(k_1-1)+\cdots+(k_s-1)+1-elemű halmazt kiszínezzük az 1,2,\dots,s színekkel, akkor valamelyik i-re van k_i pont ami az i színt kapja.

Minden r-re nyilvánvaló az s=1 eset: R_r(k)=k.

Az r=2, s=2 eset[szerkesztés | forrásszöveg szerkesztése]

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:

R(a,b)\leq {{a+b-2}\choose{a-1}}

.

Ez a+b-re való indukcióval igazolható. Nyilvánvalóan teljesül R(a,2)=a és R(2,b)=b. Ha belátjuk, hogy teljesül

R(a,b)\leq R(a-1,b)+R(a,b-1)

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

{{a+b-2}\choose{a-1}}={{a+b-3}\choose{a-2}}+{{a+b-3}\choose{a-1}}

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 |A|+|B|=R(a-1,b)+R(a,b-1)-1, vagy |A|\geq R(a-1,b) vagy |B|\geq R(a,b-1) 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): R(a,b)\leq \frac{c}{(\log(a+b))^d}{{a+b-2}\choose{a-1}} alkalmas c, d>0 konstansokkal
Thomason (1987): R(a,a)\leq\frac{1}{\sqrt{a}}{{2a-2}\choose{a-1}}
Conlon (2009): R(a,a)\leq\frac{1}{a^{c \log{a}/\log\log{a}}}{{2a-2}\choose{a-1}}

Ramsey-számok[szerkesztés | forrásszöveg szerkesztése]

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

R_2(n,n)\leq {{2n-2}\choose{n-1}}<4^n

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

2^{\frac{n}{2}}<R_2(n,n).

Egy hosszú ideig érintetlen Erdős-kérdés volt, hogy lehet-e R_2(n,n)-re a triviális (n-1)^2+1-nél lényegesen jobb konstruktív alsó becslést adni. Erre először Nagy Zsigmond egy n^3-ös, majd Frankl Péter és Wilson egy n^{c\log n}-es konstrukcót adott.

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

(c-\varepsilon)^n<R(n,n)<(c+\varepsilon)^n

teljesül.

R_2(3,n)-re a következő ismert:

c_1\frac{n^2}{\log n}<R_2(3,n)<c_2\frac{n^2}{\log n}

alkalmas pozitív c_1,c_2 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 | forrásszöveg szerkesztése]

Szavakban ez tehát azt mondja ki, hogy ha egy R_2(3,3,\dots,3) (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 R(3)\leq 3, R(3,3)\leq 6, R(3,3,3)\leq 17 és általában az R(3,3,\dots,3)\leq [er!]+1 becslést (az első három esetben egyenlőség van). Ehhez definiáljuk az f függvényt az f(1)=2, f(r+1)=(r+1)f(r)+1 rekurzióval. r-re való indukcióval bebizonyítjuk, hogy ha K_{f(r)+1} éleit r színnel színezzük, van egyszínű háromszög. Ez r=1-re nyilván igaz. Tegyükfel, hogy tudjuk az állítást r-re és adott K_{f(r+1)+1} éleinek egy r+1 színnel való színezése. Legyen p a gráf egy csúcsa, A_1,\dots,A_{r+1} sorra azon további pontok halmaza, amelyek p-be az első, második, …, r+1-edik színben vannak bekötve. Nyilván |A_1|+\cdots+|A_{r+1}|=f(r+1)=(r+1)f(r)+1, ezért van olyan i, hogy |A_i|\geq f(r)+1. Ha A_i pontjai között szerepelne az i-edik szín, akkor van az i színben háromszög. Ha nem, A_i 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

f(r)=r!\left(1+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{r!}\right)=[er!].

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

r=2, tetszőleges s esete[szerkesztés | forrásszöveg szerkesztése]

Teljes indukcióval igazolható az

R_2(k_1,\dots,k_s)\leq R_2(k_1-1,k_2,\dots)+R_2(k_1,k_2-1,\dots)+\cdots+R_2(k_1,\dots,k_s-1)-s+2

egyenlőtlenség. Ebből viszont az

R_2(k_1,\dots,k_s)\leq s^{k_1+\cdots+k_s}

korlátot kaphatjuk indukcióval.

A tétel végtelen formája[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

Tétel[szerkesztés | forrásszöveg szerkesztése]

Minden 6 pontú gráfban van egy teljes 3-as vagy egy teljes üres 3-as, azaz vagy 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 | forrásszöveg szerkesztése]

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

Tétel (Ramsey)[szerkesztés | forrásszöveg szerkesztése]

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

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

r(k,l)\leq r(k-1,l)+ r(k,l-1)

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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

Becslések r(k,l)-re[szerkesztés | forrásszöveg szerkesztése]

Felsőbecslés[szerkesztés | forrásszöveg szerkesztése]

r(k,l) \leq \binom {k+l-2}{k-1}

Alsóbecslés[szerkesztés | forrásszöveg szerkesztése]

Ha k \geq 3, akkor r(k,k) \geq 2^{\frac{k}{2}}

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

Schur tétele[szerkesztés | forrásszöveg szerkesztése]

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

Forrás[szerkesztés | forrásszöveg szerkesztése]