Ramseyova čísla

Definice:

1. Velikost maximální kliky ($K$) $\omega (G)$
2. Velikost maximální nezávislé množiny ($E$) $\alpha (G)$

Ramseyovo Číslo

$$r(k,l)=\min n\text{ takoveˊ zˇe }\forall G\text{ na n vrcholech obsahuje budˇ }{K}_k\text{ nebo }{E}_l$$

Ekvivalentně mohu vzít $n$ vrcholů a kreslit hrany 2 barvami a ptát se zda obsahuje kliku velikosti $k$ v jedné barvě, nebo kliku velikosti $l$ v barvě druhé.

Odhady

Pro $k,l\ge 2$, $r(k,l)\le r(k-1,l)+r(k,l-1)$

Důkaz: Mějme $G$ ma $r(k-1,l)+r(k,l-1)$ vrcholech. Zvolme libovolné $u$ a označme:

1. $A:=$ ne-sousedé $u$
2. $B:=$ sousedé $u$ Platí tedy nutně $|A|\ge r(k-1,l)$ nebo $|B|\ge r(k,l-1)$, protože jinak bychom se přidáním $u$ nedostali k potřebnému počtu vrcholů. Pro $|A|\ge r(k-1,l)$ máme jen dvě možnosti:
   1. $G{|}_A$ platí $\omega (G{|}_A)\ge l⟹\omega (G)\ge l$.
   2. $G{|}_A$ platí $\alpha (G{|}_A)\ge k-1$, kde přidáním $u$ máme nezávislou množinu velikosti $k$. Pro $|B|\ge r(k,l-1)$ platí obdobný argument, kde rozšiřujeme kliku o $u$.

Důsledkem je tedy

$$r(k,l)\le \left(\genfrac{}{}{0ex}{}{k+l-2}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{k+l-2}{l-1}\right)$$

r(k,l) \leq r(k,l) \leq r(k-1,l) +r(k,l-1) \leq \binom{k+l-3}{k-2} + \binom{k+l-3}{k-2} = \binom{k+l-2}{k-1}

undefined

Pr[K\text{ je zelená}] = 2^{-\binom k 2}

undefined

Pr[U] \leq \binom n k \cdot 2 \cdot 2^{-\binom k 2} = \binom n k \cdot 2^{1-\binom k 2}.

$$Je-li$$

\binom n k \cdot 2^{1-\binom k 2} <1

Pak i $Pr(U) < 1$. Existuje tedy alespoň jeden graf bez monochromatické $K_{k}$. Tedy

r(k)>n.

undefined

r(k) > 2^{k/2}.