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 a 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):

• ${\displaystyle |K|\geq 3:}$ 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.
• ${\displaystyle |N|\geq 3:}$ 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í opusťme hospodu 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ě ${\displaystyle k}$-tice. Tedy ${\displaystyle k}$-prvkovou podmnožinu vrcholů, které tvoří kliku nebo nezávislou množinu jako indukovaný podgraf.

Ramseyho věta pro grafy

• Pro každé ${\displaystyle k,l\in \mathbb {N} }$ existuje ${\displaystyle R(k,l)\in \mathbb {N} }$ takové, že každý graf na ${\displaystyle R(k,l)}$ vrcholech (nebo více) obsahuje ${\displaystyle k}$-prvkovou množinu indukující kliku nebo ${\displaystyle l}$-prvkovou množinu indukující nezávislou množinu.

• Symbolicky zapsáno: ${\displaystyle \forall k,l\in \mathbb {N} \,\exists R(k,l)\in \mathbb {N} \,\forall n\geq R(k,l)\,\forall G=(V,E),|V|\geq n:\left(\left(\exists K\subseteq V,|K|=k:G[K]\,{\text{klika}}\right)\vee (\exists L\subseteq V,|L|=l:G[L]\,{\text{nezávislá}})\right)}$

Důkaz

Důkaz bude pouze zobecnění původní verze. Provedeme ho indukcí podle ${\displaystyle k+l}$:

• ${\displaystyle k=1\vee l=1}$: Vybereme libovolný vrchol a ten bude tvořit, co chceme, jako indukovaný podgraf na tom vrcholu. Věta tedy platí pro ${\displaystyle R(k,1)=R(1,l)=1}$.
• Nechť ${\displaystyle k,l\in \mathbb {N} }$. Definujeme ${\displaystyle R(k,l)=R(k-1,l)+R(k,l-1)}$. Z indukčního předpokladu tyto hodnoty existují, tedy ${\displaystyle R(k,l)}$ 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ť ${\displaystyle G=(V,E)}$ je nějaký graf na ${\displaystyle R(k,l)}$ vrcholech. Vybereme libovolný vrchol ${\displaystyle v_{0}\in V}$. Rozdělíme ostatní vrcholy do skupin ${\displaystyle A,B\subset V:V=A\cup B\cup \{v_{0}\}}$ podle pravidla ${\displaystyle A=\{v\in V\,|\,\{v_{0},v\}\in E\},B=\{v\in V\,|\,\{v_{0},v\}\notin E\}}$. Potom nastane alespoň jedna z těchto možností:
    • ${\displaystyle |A|\geq R(k-1,l):}$ Potom někde v podgrafu indukovaném množinou ${\displaystyle A}$ existuje buď ${\displaystyle l}$-prvková nezávislá množina (a jsme hotovi), nebo ${\displaystyle (k-1)}$-prvková klika – k té přidáme ${\displaystyle v_{0}}$ a jsme také hotovi.
    • ${\displaystyle |B|\geq R(k,l-1):}$ Potom někde v podgrafu indukovaném množinou ${\displaystyle B}$ existuje buď ${\displaystyle k}$-prvková klika (a jsme hotovi), nebo ${\displaystyle (l-1)}$-prvková nezávislá množina – k té přidáme ${\displaystyle v_{0}}$ 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.

${\displaystyle R(k,l)=\mathrm {min} \left\{N\in \mathbb {N} \,|\,{\text{každý graf na alespoň }}N{\text{ vrcholech obsahuje kliku velikosti }}k{\text{ nebo nezávislou množinu velikosti }}l\right\}}$

Vícebarevná Ramseyho věta pro grafy

• Pro každé ${\displaystyle r,k_{1},\dots ,k_{r}\in \mathbb {N} }$ existuje ${\displaystyle R_{r}(k_{1},\dots ,k_{r})\in \mathbb {N} }$ takové, že pro každý úplný graf na ${\displaystyle R_{r}(k_{1},\dots ,k_{r})}$ vrcholech (nebo více) s libovolným hranovým obarvením ${\displaystyle r}$ barvami existuje takové ${\displaystyle i\in \{1,\dots ,r\}}$, že graf obsahuje ${\displaystyle k_{i}}$-prvkovou množinu vrcholů, které indukují kliku barvy ${\displaystyle i}$ (všechny hrany mezi nimi mají barvu ${\displaystyle i}$).
• Symbolicky zapsáno: ${\displaystyle \forall r,k_{1},k_{2},\dots ,k_{r}\in \mathbb {N} \,\exists R_{r}(k_{1},\dots ,k_{r})\in \mathbb {N} \,\forall n\geq R_{r}(k_{1},\dots ,k_{r})\,\forall c:E(K_{n})\rightarrow \{1,\dots ,r\}\,\exists b\in \{1,\dots ,r\}\,\exists K\subseteq V(K_{n}),|K|=k_{b}:c|_{K}\equiv b}$

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

• Pro ${\displaystyle r=1}$ je věta triviální, pro ${\displaystyle r=2}$ je ekvivalentní předchozí větě.
• Mějme ${\displaystyle r\in \mathbb {N} }$ počet barev. Vybereme libovolné dvě barvy a ty slijeme dohromady, například vybereme ${\displaystyle r-1,r}$ a definujeme nové obarvení ${\displaystyle c':V\rightarrow \{1,\dots ,r-2,q\}}$, barvy hran původně obarvených barvami ${\displaystyle r-1,r}$ jsou nyní obarveny barvou ${\displaystyle q}$. Potom úplný graf ${\displaystyle K_{n}}$ pro ${\displaystyle n\geq R_{r}(k_{1},\dots ,k_{r})=R_{r-1}(k_{1},\dots ,k_{r-2},R_{2}(k_{r-1},k_{r}))}$ (podle indukčního předpokladu toto číslo existuje) obsahuje buď nějakou jednobarevnou patřičně velkou kliku pro barvy ${\displaystyle 1,\dots ,r-2}$ (a jsme hotovi), nebo ${\displaystyle q}$-barevnou kliku velikosti ${\displaystyle R_{2}(k_{r-1},k_{r})}$. 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ě ${\displaystyle n>2^{k/2-1}}$. 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í ${\displaystyle \left({\frac {1}{2}}\right)^{\binom {k}{2}}}$. Pravděpodobnost, že graf obsahuje k-kliku je tedy ${\displaystyle {\binom {n}{k}}2^{-{\binom {k}{2}}}}$. 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ž ${\displaystyle 2{\binom {n}{k}}2^{-k(k-1)/2}}$. 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 ${\displaystyle 2{\binom {n}{k}}2^{-k(k-1)/2}<1}$, použijeme odhad ${\displaystyle {\binom {n}{k}}\leq n^{k}}$:

${\displaystyle 2{\binom {n}{k}}2^{-k(k-1)/2}\leq 2n^{k}2^{-k(k-1)/2}<1}$, z toho plyne ${\displaystyle 2n^{k}<2^{k(k-1)/2}}$. Tedy pokud zvolíme ${\displaystyle n<2^{k/2-1}}$, 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.