A Ramsey-elmélet Frank Plumplton Ramsey matematikus-közgazdász harmincas években publikált eredménye által elindított igen fontos ága a kombinatorikának.
Az elméletet összefűző ``filozófiát'' nagyon egyszerűen meg lehet fogalmazni: Ha egy struktúra hatalmas, akkor az nem kerülheti el az igen szabályos nagy részstruktúrákat. Az alábbiakban a fentieket alátámasztó matematikai tételeket ismertetünk.
Az első struktúra a teljes gráf éleinek két (piros-kék) színezései. A csúcsok egy H halmazát homogénnek nevezzük, ha a H-ban haladó élek mind ugyanolyan színűek. Ha a közös színt ki akarjuk emelni, akkor piros-homogén, illetve kék-homogén halmazról beszélünk. Igaz-e, hogy ha a kiinduló teljes gráf pontszáma elég nagy, akkor tetszőleges színezésünk garantáltan tartalmaz k elemű homogén részhalmazt? Ramsey-tétele azt állítja, hogy igen. Az alábbiakban egy Erdős Páltól származó bizonyítást ismertetünk.
Tétel (Ramsey-tétel): Legyen G a (k+l-2k-1) csúcsú teljes gráf és legyen f:E(G)->{piros, kék} egy tetszőLeges piros-kék élszínezése. Ekkor G garantáltan tartalmaz k elemű piros-homogén ponthalmazt vagy l elemű kék-homogén halmazt.
Bizonyítás: k+l-re vonatkozó indukció. A k=1 vagy k=2 eset könnyen meggondolható. Az indukciós lépeshez válasszuk ki G egy tetszőleges x csúcsát. Az x-en kívüli csúcso két csoportba oszthatók aszerint, hogy x-ből milyen színű él vezet hozzá. Legyen P az x csúcs azon szomszédai, amihez x-ből piros él vezet. Legyen K az x csúcs azon szomszédai, amihez x-ből kék él vezet. Könnyű belátni, hogy vagy |P| legalább ((k-1)+l-2(k-1)-1) vagy |K| legalább (k+(l-1)-2k-1). Az első esetben az indukciós feltevés garantál k-1 elemű piros-homogén ponthalmazt, amely x-szel kibővítve ad egy k elemű piros-homogén halmazt, vagy egy l elemű kék-homgén halmazt. Így ekkor készen vagyunk. A második eset hasonlóan működik.
A tétel és a bizonyítás természetes módon vezet a következő definícióhoz.
Definíció: Legyen R(k,l) az a minimális természetes szám, amellyel helyettesíthető a tételben szereplő (k+l-2k-1). Legyen R(k)=R(k,k). Az R(k,l) és R(k) számokat Ramsey-számoknak nevezzük.
A Ramsey-számok vizsgálata központi kérdés a gráfelméletben. Az alábbiakben az R(k) számokra vonakozó alaperedményeket ismertetjük.
Tétel (Erdős Pál tétele): 2k/2 < R(k) < 4k.
Bizonyítás: A felső becslés könnyen adódik a Ramsey-tétel fenti bizonyításából, hiszen ott R(k)<=(2k-2k-1)-et kaptunk. Az alsó becsléshez legyen r egy véletlen él színezése a 2k/2 pontú teljes gráf élhalmazának (minden él színe egyvalószínűségi változó, amely 1/2-ed valószínűséggel kék, 1/2-ed valószínűséggel piros értéket vesz fel, továbba az egyes valószínűségi változó különböző élek esetén függetlenek. Könnyű belátni, hogy a k elemű homogén halmazok létezésének valószínúsége 1-nél kisebb. (Igazából nagyon kicsi lesz.) Így lesz olyan színezése a telhjes gráfnak, amely azt mutatja, hogy a Ramsey-tételben 2k/2 elemszámú ponthalmazzal nem boldogulhatunk.
A fenti tétel nagyon egyszerű, de mind a mai napig nem ismert lényeges javítása. A Ramsey-számok jelenleg is központi kutatási témája a gráfelméletnek.
Az alsó becslés módszere egy nagyon fontos módszert indított el a kombinatorikában. A valószínűségszámítási módszert rendkívül hatékonyan használják.
Természetesen a tétel megértése után az alső becslés bizonyítására más mód kívánkozik: Adjunk meg egy 2k/2 pontú teljes gráfot és írjuk le éleinek egy kétszínezését, amjd mutassuk meg. hogy a leírt, konkrét színezés esetén nincs k elemű homogén halmazunk. A fenti bizonyítást a várt, jól leírt konstrukciót helyettesítette egy véletlennel. Konstruktív bizonyítás mind a mai napig nem ismert Ramsey tételére.