Ramseyova čísla

Definice:

Velikost maximální kliky ( $K$ ) $ω (G)$
Velikost maximální nezávislé množiny ( $E$ ) $α (G)$

Ramseyovo Číslo

r (k, l) = min n takov \overset{e}{ˊ} \overset{z}{ˇ} e \forall G na n vrcholech obsahuje bu \overset{ˇ}{d} K_{k} 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 \geq 2$ , $r (k, l) \leq 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:

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

Důsledkem je tedy

r (k, l) \leq (k - 1 k + l - 2) = (l - 1 k + l - 2)

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

$\forall k, n \in N$ t.ž. $(k n) 2^{1 - k /2} < 1 ⟹ r (k) > n$ .

Zapisujeme $r (k)$ jako zkratku $r (k, k)$ . Chceme ukázat, že existuje graf na $n$ vrcholech, který neobsahuje ani zelenou $K_{k}$ , ani modrou $K_{k}$ . Označme $G (n, \frac{1}{2})$ náhodný graf, ve kterém každou hranu obarvíme zeleně (resp. existuje) s pravděpodobností $\frac{1}{2}$ , nezávisle.

Pro každou pevnou množinu $K$ o $k$ vrcholech je pravděpodobnost, že tvoří zelenou klikou

P r [K je zelen \overset{a}{ˊ}] = 2^{- (2 k)}

Označme $U$ událost, že existuje nějaká $k$ -prvková množina, která je buď zelenou klikou, nebo modrou nezávislou množinou. Poté odhadem sjednocení (union bound - $P r (U_{1} \cup U_{2}) \leq P r (U_{1}) + P r (U_{2})$ ) máme

P r [U] \leq (k n) \cdot 2 \cdot 2^{- (2 k)} = (k n) \cdot 2^{1 - (2 k)} .

Je-li

(k n) \cdot 2^{1 - (2 k)} < 1

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

r (k) > n .

Volbou $n = ⌊ 2^{k /2} ⌋$ a hrubou odhadovou nerovností $(k n) \leq \frac{n ^{k}}{k !}$ , dostaneme pro velká $k$

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

Osobní stránka

Explorer

Ramseyova čísla

Ramseyovo Číslo

Odhady

Pro $k, l \geq 2$ , $r (k, l) \leq r (k - 1, l) + r (k, l - 1)$

$\forall k, n \in N$ t.ž. $(k n) 2^{1 - k /2} < 1 ⟹ r (k) > n$ .

Graph View

Table of Contents

Backlinks

Osobní stránka

Explorer

Ramseyova čísla

Ramseyovo Číslo

Odhady

Pro k,l≥2, r(k,l)≤r(k−1,l)+r(k,l−1)

∀k,n∈N t.ž. (kn​)21−k/2<1⟹r(k)>n.

Graph View

Table of Contents

Backlinks

Pro $k, l \geq 2$ , $r (k, l) \leq r (k - 1, l) + r (k, l - 1)$

$\forall k, n \in N$ t.ž. $(k n) 2^{1 - k /2} < 1 ⟹ r (k) > n$ .