Ramsey-tétel

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

Ha ${\displaystyle r,k_{1},\dots ,k_{s}}$ pozitív egész számok, akkor van olyan (legkisebb) ${\displaystyle 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 ${\displaystyle |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 ${\displaystyle 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 ${\displaystyle R_{1}(k_{1},\dots ,k_{s})=(k_{1}-1)+\cdots +(k_{s}-1)+1}$-elemű halmazt kiszínezzük az ${\displaystyle 1,2,\dots ,s}$ színekkel, akkor valamelyik i-re van legalább ${\displaystyle k_{i}}$ számú pont ami az i színt kapja.

Minden r-re nyilvánvaló az s=1 eset: ${\displaystyle R_{r}(k)=k}$.

Az r=2, s=2 eset

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:

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

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

${\displaystyle R(a,b)\leq R(a-1,b)+R(a,b-1)}$

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

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

Thomason (1987): ${\displaystyle R(a,a)\leq {\frac {1}{\sqrt {a}}}{{2a-2} \choose {a-1}}}$

Conlon (2009): ${\displaystyle 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

${\displaystyle 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

${\displaystyle 2^{\frac {n}{2}}<R_{2}(n,n).}$

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

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

${\displaystyle (c-\varepsilon )^{n}<R(n,n)<(c+\varepsilon )^{n}}$

teljesül.

${\displaystyle R_{2}(3,n)}$-re a következő ismert:

${\displaystyle c_{1}{\frac {n^{2}}{\log n}}<R_{2}(3,n)<c_{2}{\frac {n^{2}}{\log n}}}$

alkalmas pozitív ${\displaystyle 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 ${\displaystyle R_{2}(3,3,\dots ,3)}$ (r darab 3) szögpontú teljes gráf éleit r színnel színezzük, akkor van egyszínű háromszög. Bebizonyítjuk az ${\displaystyle R(3)\leq 3,R(3,3)\leq 6,R(3,3,3)\leq 17}$ és általában az ${\displaystyle 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 ${\displaystyle f(1)=2}$, ${\displaystyle f(r+1)=(r+1)f(r)+1}$ rekurzióval. r-re való indukcióval bebizonyítjuk, hogy ha ${\displaystyle 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ük fel, hogy tudjuk az állítást r-re és adott ${\displaystyle K_{f(r+1)+1}}$ éleinek egy r+1 színnel való színezése. Legyen p a gráf egy csúcsa, ${\displaystyle 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 ${\displaystyle |A_{1}|+\cdots +|A_{r+1}|=f(r+1)=(r+1)f(r)+1}$, ezért van olyan ${\displaystyle i}$, hogy ${\displaystyle |A_{i}|\geq f(r)+1}$. Ha ${\displaystyle A_{i}}$ pontjai között szerepelne az i-edik szín, akkor van az i színben háromszög. Ha nem, ${\displaystyle 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

${\displaystyle 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

${\displaystyle 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

${\displaystyle 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).

Ramsey-típusú tételek

Tétel

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. A tétel koktélparti-tétel néven is ismeretes, mivel egy közérthető megfogalmazása szerint ha hat vendéget hívunk meg egy partira, akkor vagy vannak hárman, akik kölcsönösen ismerik egymást, vagy hárman, akik kölcsönösen nem.

Bizonyítás

Válasszunk ki egy tetszőleges pontot, ${\displaystyle {v_{1}}}$-et. Ezen kívül még 5 pontunk van, ezekből vagy van 3 olyan pont, amibe vezet él ${\displaystyle v_{1}}$-ből, vagy van 3 olyan pont, amibe nem vezet él ${\displaystyle v_{1}}$-ből. Az első esetben legyenek ${\displaystyle v_{1}}$ szomszédai ${\displaystyle v_{2}}$, ${\displaystyle v_{3}}$, ${\displaystyle v_{4}}$. Ha ezek között fut él, például ${\displaystyle \{v_{2},v_{3}\}\in E(G)}$, akkor ${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$, ${\displaystyle v_{3}}$ egy teljes 3-ast ad, azonban ha nem fut köztük él, akkor ${\displaystyle v_{2}}$, ${\displaystyle v_{3}}$, ${\displaystyle 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 ${\displaystyle r(k,l)}$ szám, hogy ${\displaystyle n\geq r(k,l)}$ esetén az ${\displaystyle n}$ pontú teljes gráf, ${\displaystyle K_{n}}$ éleit két színnel kiszínezve van a gráfban egy első színű ${\displaystyle K_{k}}$ vagy egy második színű ${\displaystyle 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)

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

Bizonyítás

Bizonyítsunk indukcióval. Nyilvánvaló, hogy létezik ${\displaystyle r(k,2)}$ és ${\displaystyle r(2,l)}$, és világos, hogy ${\displaystyle r(k,2)=k}$ és ${\displaystyle r(2,l)=l}$. Tegyük fel, hogy létezik minden ${\displaystyle r(t,s)}$, ahol vagy ${\displaystyle t\leq k}$ és ${\displaystyle s<l}$ vagy ${\displaystyle t<k}$ és ${\displaystyle s\leq l}$. Emellett indirekt tegyünk fel, hogy ${\displaystyle n\geq r(k-1,l)+r(k,l-1)}$, és ${\displaystyle K_{n}}$ éleit ki lehet színezni két színnel úgy, hogy a gráfban nincs sem első színű (kék) ${\displaystyle K_{k}}$, sem második színű (piros) ${\displaystyle K_{l}}$. Válasszuk ki ${\displaystyle K_{n}}$ egy tetszőleges pontját a gráfnak, ${\displaystyle v_{1}}$-et. Legyenek ${\displaystyle v_{1}}$-ből kiinduló kék élek végpontjai ${\displaystyle k_{1},k_{2},\dots ,k_{u}}$, a pirosaké pedig ${\displaystyle p_{1},p_{2},\dots ,p_{v}}$. Ha ${\displaystyle u}$ nagyobb lenne ${\displaystyle r(k-1,l)-1}$-nél, akkor a ${\displaystyle k_{i}}$ pontok között a feltevés miatt volna vagy egy piros ${\displaystyle K_{l}}$, vagy egy kék ${\displaystyle K_{(k-1)}}$, és az utóbbi esetben ehhez hozzávéve ${\displaystyle v_{1}}$-et kék ${\displaystyle K_{k}}$-t kapnánk. Tehát a feltevéseinkből következik, hogy ${\displaystyle u\leq r(k-1,l)-1}$. Ugyanígy kapjuk, hogy ${\displaystyle v\leq r(k,l-1)-1}$. Ekkor viszont ${\displaystyle 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 ${\displaystyle r(k-1,l)+r(k,l-1)}$ olyan szám, hogy minden nála nem kisebb ${\displaystyle n}$-re ${\displaystyle K_{n}}$-et színezve lesz a gráfban kék ${\displaystyle K_{k}}$, vagy piros ${\displaystyle K_{l}}$. Ekkor viszont a legkisebb ilyen szám kisebb vagy egyenlő ${\displaystyle r(k-1,l)+r(k,l-1)-1}$-vel.

Becslések r(k,l)-re

Felső becslés

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

Alsó becslés

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

Alkalmazások

Schur tétele

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

Források

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