Extremální kombinatorika

Jak velká (nebo naopak jak malá) může být struktura vyhovující určité vlastnosti, pokud jiná nežádoucí vlastnost nesmí nastat?

v případě grafů a hypergrafů se jedná hlavně o

Kolik nejvíce hran může mít graf, který splňuje danou vlastnost a ideálně i jak vypadá.

Ještě konkrétněji se jedná třeba o

Kolik nejvíc hran může mít graf, který neobsahuje jiný graf jako podgraf.

Značení: Pro graf $H$, $ex(n,H)$ je největší $m$ takové, že existuje graf s $n$ vrcholy a $m$ hranami neobsahující $H$ jako podgraf.

Definice (Turánův graf): Pro $k,n\in \mathbb{N}$ označme $T_k(n)$ úplný $k$-partitní graf na $n$ vrcholech, jehož všechny partity mají velikost $\lfloor \frac{n}{k}\rfloor$ nebo $\lceil \frac{n}{k}\rceil$.

Pozorování: $\forall n\in \mathbb{N},r\ge 2:ex(n,K_r)\ge T_{k-1}(n)$

Turánova věta

$\forall r\ge 2:ex(n,K_r)=T_{k-1}(n)$

Erdös-Ko-Radoova věta

Definice: $k$-uniformní hypergraf je dvojice $(V,E)$, kde $E\subseteq \left(\genfrac{}{}{0ex}{}{V}{k}\right)$)

• $f(k,n):=\max m$ t.ž. $\exists$ $k$-uniformní hypergraf $H=(V,E)$ t.ž. $\mid V\mid =n,\mid E\mid =m$ a $E$ je „pronikající systém množin“ (t.j. $\forall e,e\prime \in E:e\cap e^{\prime }\ne \varnothing$)
  • braní všech hran nemusí fungovat (musí se protínat všechny dvojice)

Věta: $\forall k,n\in \mathbb{N}:n\ge 2k⟹f(k,n)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$