Extremální grafy (bez C3, C4)

[petrmanek]

-- Dukaz T(n) = \lfloor n^2 / 4 \rfloor

1. Horní odhad - $T(n) \geq \left\lfloor \frac{n^2}{4} \right\rfloor$
   a) pro n sudé - použijeme $K_{\frac{n}{2}, \frac{n}{2}}$
   b) pro n liché $n = 2k+1$, použijeme $K_{k+1, k}$ - nahlédneme, že $|E| = k(k+1)$. Chceme $\left\lfloor \frac{n^2}{4} \right\rfloor = \left\lfloor \frac{4k^2 + 4k + 1}{4} \right\rfloor = k^2 + k = k(k+1)$
2. Dolní odhad - indukcí dle $n$, krok bude $n \rightarrow n+2$
   Mějme $G$ na $n+2$ vrcholech, chceme ukázat, že $|E| \leq \frac{(n+2)^2}{4}$ Vezměme libovolnou ${u,v} \in E$. Použijeme IP na graf $G'(V',E') = G(V \backslash {u,v}, E[V'])$. Víme, že $|V'| = n$, $|E'| \leq \frac{n^2}{4}$. Počet hran mezi vrcholem $u$ a zbytkem grafu si označím jako $N_u$, odbodně s $v$. Víme dále, že $|E| = |E'| + N_u + N_v + 1$. Stačí nahlédnout, že $N_u + N_v \leq n$. Sporem, kdyby nebylo, existuje vrchol $p$ takový, že ${p,u} \in E \land {p,v} \in E$. To by ale znamenalo, že máme trojúhelník, což je spor s předpokladem.

ještě nám ukazoval, že graf s maximálním počtem hran bez trojúhelníku je právě K_n/2,n/2 - důkaz = zamyslet se nad důkazem té rovnosti
poznamka k predchozi - T(n) oznacoval jako max pocet hran v grafu s n vrcholy bez K3
-- a tedy Důkaz $|E(G)| \leq \frac{1}{2} \left( n^\frac{3}{2} + n \right)
vezměme si množinu $M$, což je množina cest $P_2 \subset G$ mezi 3 vrcholy, označíme si je $(u, v, w)$.
Nahlédneme, že pro libovolnou dvojici ${u, w}$ existuje nejvýše jedno $v$, jinak bychom dostali $C_4$, tedy $|M| \leq \binom{n}{2}$.
Dále nahlédneme, že pro $v$ lze zvolit ${u, w}$ jako libovolné sousedy $v$, $|M| = \sum_{v \in V} \binom{\mathrm{deg}(v)}{2}$.
Pokud budou tedy $d_1, \dots, d_n$ stupně vrcholů, bude platit, že $\frac{\sum_{i=1}^n (d_i-1)^2}{2} \leq \sum_{i=1}^{n} \binom{d_i}{2} \leq \binom{n}{2}. Nás zajímá max. $|E| = \frac{1}{2} \sum_{i=1}^n d_i$. Využitím Cauchy-Schwarzovi nerovnosti víme, že
$$ \sum_{i=1}^n (d_i - 1) \leq \sqrt{\sum_{i=1}^n (d_i - 1)^2} \sqrt{\sum_{i=1}^n} \leq \sqrt{n^2} \sqrt{n} \leq n^{\frac{3}{2}}$$
$$|E| \leq \frac{1}{2} \left( n^{\frac{3}{2}} + n \right)$$
$n$ se vyskytuje protože počítáme s $d_i - 1$.

-- tenhle důkaz je ošklivý, tak si ho radši ještě projdi, Medvěd nám ho dával takhle. Ten už se mi narozdíl od předchozího nelíbí.