Ramsey-tétel

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

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

E speciális eset a tétel legismertebb formája: ha a 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 vagy 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

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 K_L‒1 olyan kék-piros színezéséből áll, ami nem tartalmaz kék K_a részgráfot, sem piros K_b részgráfot. Egy K_n 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).

R₂(3,3,…,3) esete

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

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

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).

Tétel

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

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)

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

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)

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

Bizonyítás

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

Felsőbecslés

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

Alsóbecslés

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

Alkalmazások

Schur tétele

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

• Katona Gyula Y, Recski András, Szabó Csaba. A számítástudomány alapjai. Typotex Kiadó. ISBN 963-9326-68-2 (2001) 
• Ramsey-type theorem