Főmenü megnyitása

A tétel véges formájaSzerkeszté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 esetSzerkeszté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ámokSzerkeszté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) eseteSzerkesztés

Szavakban ez tehát azt mondja ki, hogy ha egy   (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   é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 eseteSzerkesztés

Teljes indukcióval igazolható az

 

egyenlőtlenség. Ebből viszont az

 

korlátot kaphatjuk indukcióval.

A tétel végtelen formájaSzerkeszté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ételekSzerkesztés

TételSzerkeszté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ásSzerkeszté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ásSzerkeszté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ásSzerkeszté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)-reSzerkesztés

Felső becslésSzerkesztés

 

Alsó becslésSzerkesztés

Ha  , akkor  

AlkalmazásokSzerkesztés

Schur tételeSzerkeszté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ásSzerkesztés

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