Ramseyho teorie
Ramseyho teorie je soubor výsledků a vět z extremální kombinatoriky. Objektem zkoumání jsou velké množiny a jaké vlastnosti těchto množin můžeme zaručit pouze na základě jejich velikosti. Teorie je pojmenována po britském matematikovi F. P. Ramseyovi.

Motivační příklad 
Obvyklý příklad, který se uvádí jako úvod do problematiky Ramseyho teorie, je tento: Uvažujme hospodu, kde daný den popíjí právě 6 lidí. Někteří lidé se znají a někteří lidé se neznají (ovšem znají se navzájem, není možné, že by Petr znal Adama, ale Adam Petra ne). Potom můžeme zaručit, že na takovém večírku existuje trojice lidí, kteří se navzájem znají (každý z trojice zná každého z trojice), nebo trojice lidí, kteří se navzájem vůbec neznají (nikdo z trojice nezná nikoho z trojice). Pravdivost tohoto tvrzení není zřejmá, lze dokázat takto:

Vyberme libovolného štamgasta, nazvěme ho Honza. Ostatní zúčastněné rozdělme na skupiny K,N, kde skupinu K tvoří kamarádi Honzy a skupinu N tvoří lidé, které Honza nezná. Celkem tyto skupiny obsahují pět lidí, tedy alespoň jedna z těchto skupin obsahuje alespoň tři návštěvníky. Rozdělme si možné případy (jeden z nich musí nastat):
  Tedy máme trojici lidí, kteří se všichni přátelí s Honzou. Pokud se alespoň dva z nich znají navzájem, potom spolu s Honzou tvoří hledanou trojici. Pokud se žádní dva z nich neznají navzájem, všichni tři tvoří hledanou trojici.
  Máme trojici cizinců, které Honza nezná. Pokud se někteří dva z nich neznají navzájem, potom spolu s Honzou tvoří hledanou trojici. Pokud to není pravda, potom se nutně musí všichni tři znát navzájem a tedy opět tvoří hledanou trojici.

Tedy v obou možných případech najdeme trojici a tím je tvrzení dokázáno.

Přeformulování 
Nyní zavrhněme hospody a přesuňme se do o něco formálnějších podmínek. Tedy do teorie grafů (ideální kombinací je pak teorie grafů nad pivem v hospodě). Situace v pivnici se dá modelovat jako jednoduchý graf na 6 vrcholech reprezentujících hospodské povaleče, kde hrana mezi dvěma vrcholy je právě tehdy, když se pivaři znají. Takže věta se dá přeformulovat takto:

 V každém grafu na 6 vrcholech existuje trojúhelník nebo nezávislá trojice vrcholů.

Prvním zobecněním, které na výše uvedeném tvrzení provedeme, bude, že nebudeme hledat pouze trojice, ale obecně -tice. Tedy -prvkovou podmnožinu vrcholů, které tvoří kliku nebo nezávislou množinu jako indukovaný podgraf.

Ramseyho věta pro grafy 
 Pro každé  existuje  takové, že každý graf na  vrcholech (nebo více) obsahuje -prvkovou množinu indukující kliku nebo -prvkovou množinu indukující nezávislou množinu.

 Symbolicky zapsáno:

Důkaz 
Důkaz bude pouze zobecnění původní verze. Provedeme ho indukcí podle :

 : Vybereme libovolný vrchol a ten bude tvořit, co chceme, jako indukovaný podgraf na tom vrcholu. Věta tedy platí pro .
 Nechť . Definujeme . Z indukčního předpokladu tyto hodnoty existují, tedy  je dobře definovaná. Tvrdíme, že tato hodnota splňuje větu - tedy že v ní existuje alespoň jeden z indukovaných podgrafů:
 Nechť  je nějaký graf na  vrcholech. Vybereme libovolný vrchol . Rozdělíme ostatní vrcholy do skupin  podle pravidla . Potom nastane alespoň jedna z těchto možností:
  Potom někde v podgrafu indukovaném množinou  existuje buď -prvková nezávislá množina (a jsme hotovi), nebo -prvková klika – k té přidáme  a jsme také hotovi.
  Potom někde v podgrafu indukovaném množinou  existuje buď -prvková klika (a jsme hotovi), nebo -prvková nezávislá množina – k té přidáme  a jsme také hotovi.
 Tedy jsme v každé možnosti našli hledaný podgraf a věta platí.

Definice Ramseyho čísla 
Co vlastně R(k,l) znamená, lze vyčíst z výše uvedené věty, ale stejně si toto číslo formálně definujme pro jasnost. Také se nám bude hodit znát explicitní definici až budeme dokazovat dolní odhad.

Vícebarevná Ramseyho věta pro grafy 
 Pro každé  existuje  takové, že pro každý úplný graf na  vrcholech (nebo více) s libovolným hranovým obarvením  barvami existuje takové , že graf obsahuje -prvkovou množinu vrcholů, které indukují kliku barvy  (všechny hrany mezi nimi mají barvu ).
 Symbolicky zapsáno: 

Tato verze je zjevně silnější než původní verze, ačkoli zkoumáme pouze úplné grafy – jednobarevný graf lze modelovat na úplném grafu tak, že hrany obarvíme jednou barvou a nehrany jinou barvou.

Důkaz 
Důkaz provedeme za použití jednobarevné verze. Budeme postupovat indukcí podle :
 Pro  je věta triviální, pro  je ekvivalentní předchozí větě.
 Mějme  počet barev. Vybereme libovolné dvě barvy a ty slijeme dohromady, například vybereme  a definujeme nové obarvení , barvy hran původně obarvených barvami  jsou nyní obarveny barvou . Potom úplný graf  pro  (podle indukčního předpokladu toto číslo existuje) obsahuje buď nějakou jednobarevnou patřičně velkou kliku pro barvy  (a jsme hotovi), nebo -barevnou kliku velikosti . Potom, když opět rozdělíme barvy jako v původním obarvení, vznikne dvoubarevný podgraf, ve kterém podle indukčního předpokladu (nebo podle předchozí věty) existuje alespoň jedna z jednobarevných klik patřičné velikosti. A jsme hotovi.

Dolní odhad R(k,k) 
Dokázali jsme, že pro každé k,l existují velmi velké grafy s požadovanou vlastností, ale neznáme, jak velké tyto grafy vlastně musí být. Budeme nyní hledat dolní odhad R(k,k). Použijeme slavný Erdosův důkaz pravděpodobnostní metodou.

Nechť n=R(k,k), dokážeme, že nutně . G=(V,E) je graf na n vrcholech, kde každá hrana je v E s pravděpodobností 1/2. Tedy konstrukci tohoto grafu si můžeme představit tak, že pro každou dvojici vrcholů hodíme mincí, pokud padne hlava, tuto hranu zahrneme, pokud orel, nezahrneme ji do E.

Pro libovolnou k-prvkovou podmnožinu vrcholů platí, že je klikou s pravděpodobností . Pravděpodobnost, že graf obsahuje k-kliku je tedy . Zřejmě graf obsahuje nezávislou množinu se stejnou pravděpodobností. Tedy pro G platí, že pravděpodobnost, že obsahuje kliku nebo nezávislou množinu na k vrcholech, je menší, než . Pokud ukážeme, že tato pravděpodobnost je menší, než 1, určitě bude existovat nějaký graf, ve kterém k-klika ani k-prvková nezávislá množina nejsou (protože kdyby neexistoval, pravděpodobnost by musela být rovna 1). Tedy nyní již jen vyjádříme n z nerovnice
, použijeme odhad :

, z toho plyne . Tedy pokud zvolíme , nerovnost bude platit a tedy bude existovat graf bez požadovaných podgrafů a tedy Ramseyovo číslo musí být větší než tato hodnota n.

 
Matematické věty a důkazy