Ramseyovy věty

Konečná Ramseyova věta

Pro každé $t$ a $p$ existuje $N$ takové, že pro každou funkci $c:\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)\mapsto [t],n\ge N$ existuje množina $A\in \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ pro níž je $c$ ma $\left(\genfrac{}{}{0ex}{}{A}{2}\right)$ konstantní.

Co to znamená?

• $t$ udává, kolik barev používáme
• $k$ předepisuje, jak velkou kliku si přejeme najít
• $N$ říká, jak velký graf je už „dost velkýˇ
• $n$ je počet vrcholů grafu, který se chystáme obarvit
• $[n]=1,...,n$ očíslujeme vrcholy tohoto grafu
• $c$ je obarvení hran grafu $t$ barvami
• $A$ je $k$-tice vrcholů, která indukuje jednobarevnou kliku

Věta je velmi podobná principu holubníku. V něm ovšem nebarvíme hrany, nýbrž vrcholy samotné: Věta: (princip holubníku) Pro každé $t$ a $k$ existuje $N$ takové, že pro každou funkci $c:[n]\to [t],n\ge N$ existuje množina $A\in \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$, na níž je funkce c konstantní. Důkaz: Stačí zvolit $N=t(k-1)+1$.

Nekonečná Ramseyova věta

$\forall p,t\in \mathbb{N}$ a $\forall c:\left(\genfrac{}{}{0ex}{}{\mathbb{N}}{p}\right)\mapsto [t]$, tak $\exists A\subseteq \mathbb{N}$ nekonečná že $c$ je na $\left(\genfrac{}{}{0ex}{}{A}{p}\right)$ konstantní. Důkaz: Sestrojme posloupnost nekonečných množin $A_1,A_2,A_3,\dots$ . Položme $A_1=\mathbb{N}$ a opakujme následný krok pro $i=1,2,3,4,\dots$: Zvolíme $v_i\in A_i$ libovolně. Rozdělíme do ekvivalenčních tříd ostatní vrcholy, tedy $A_i^{\prime }=A_i\setminus \{v_i\}$, dle toho jakou barvu mají hrany z $v_i$ do daného vrcholu a třídy označíme $B_i^1,B_i^2,B_i^3,\dots ,,B_i^t$. $A_i^{\prime }$ je nekonečná a tedy alespoň jedna z tříd musí být taky, nechť je to $B_i^j$. Položme nyní $b_i=j$ a $A_{i+1}=B_j^i$ a znovu iterujme. Pozorování: Posloupnost vybraných $v_1,v_2,\dots$ má vlastnost, že kdykoliv $i<j$, tak hrana $\{v_i,v_j\}$ má barvu $b_i$. V nekonečné posloupnosti vybraných barev $b_1,b_2,\dots$ je ale jen konečně mnoho hodnot. Takže některá se musí nekonečněkrát opakovat. Označme ji $b_i$ a její výskyty $b_{i_1},b_{i_2},\dots$ Z pozorování tedy plyne, že vrcholy $v_{i_1},v_{i_2},v_{i_3},\dots$ indukují námi hledanou nekonečnou jednobarevnou kliku $A$.

Důkaz konečné verze: Potřebujeme zajistit, aby vybraná podposloupnost obsahovala $k$ vrcholů. Z principu holubníku víme, že k tomu stačí zaručit, aby posloupnost, ze které vybíráme, obsahovala alespoň $tk$ prvků (neboť v ní je nejvýše $t$ různých hodnot).

Musíme tedy upravit výběr $A_{i+1}$ z $A_i$ a sice za $A_{i+1}$ zvolíme největší ze tříd $A_i$. Tedy $|A_{i+1}|\ge |A_i|-1/t$. Tedy je nutné zařídit, aby konstrukce jela $tk$ kroků, tedy $|A_{tk}|\ge 1$. To nastane, když  $|A_{tk-1}|\ge t+1,|A_{tk-2}|\ge t^2+t+1,\dots ,|A_1|\ge {\sum }_{i=0}^{tk}{t}^i=(t^{tk+1}-1)/(t-1)$. Stačí mít tedy $N=t^{tk+1}$ a konstrukce vytvoří dostatečně dlouhou posloupnost, abychom v ní našli jednobarevnou kliku na $k$ vrcholech.

Nekonečná Ramseyova věta pro $p$-tice

Pro každé $t,p$ a $k$ existuje $N$ takové, že pro každou funkci $c:\left(\genfrac{}{}{0ex}{}{[n]}{p}\right)\mapsto [t],n\ge N$ existuje nekonečná množina $A\subseteq \mathbb{N}$, pro níž je $c$ ma $\left(\genfrac{}{}{0ex}{}{A}{p}\right)$ konstantní. Ke státnicím je potřeba jen verze s $p=2$, která je extra výše, avšak Důkaz je linknut.

Konečná Ramseyova věta pro $p$-tice

Pro každé $t,p$ a $k$ existuje $N$ takové, že pro každou funkci $c:\left(\genfrac{}{}{0ex}{}{[n]}{p}\right)\mapsto [t],n\ge N$ existuje množina $A\in \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ pro níž je $c$ ma $\left(\genfrac{}{}{0ex}{}{A}{p}\right)$ konstantní.