Nejednakost Erdös-Szekeresa

Predložak:Drugoznačenje2 Nejednakost Erdös-Szekeresa je teorem u kombinatorici, odnosno Ramseyjevoj teoriji. Nejednakost predstavlja gornju ogradu za Ramseyjev broj $N(p,q)$.

Nejednakost glasi:

$N(p,q)\le (\genfrac{}{}{0ex}{}{p+q-2}{p-1})$, za $p,q\ge 2$.

Nejednakost je nazvana u čast mađarskim matematičarima Paulu Erdösu, jednom od najznačajnijih matematičara 20. stoljeća, i Georgeu Szekeresu.

Dokaz

Indukcijom po zbroju $p+q$. Za $p+q=4$ tvrdnja vrijedi jer je tada $p=q=2$, te je pritom $N(2,2)=2\le (\genfrac{}{}{0ex}{}{2}{1})=2$.

Pretpostavimo da nejednakost vrijedi za sve parove $(p,q)$ za koje je $p+q<n$ za neki $n\in \mathbb{N}$. Dokazat ćemo da vrijedi i za sve parove $(p,q)$ za koje je $p+q=n$.

Koristimo poznatu nejednakost $N(p,q)\le N(p-1,q)+N(p,q-1)$. Zbog pretpostavke indukcije dobivamo redom:

$N(p,q)\le N(p-1,q)+N(p,q-1)$

$\le (\genfrac{}{}{0ex}{}{p-1+q-2}{p-2})+(\genfrac{}{}{0ex}{}{p+q-1-2}{p-1})$

$=\frac{p+q-3)!}{(p-2)!(q-1)!}+\frac{p+q-3)!}{(p-1)!(q-2)!}$

$=\frac{(p+q-3)!}{(p-2)!(q-2)!}[\frac{1}{q-1}+\frac{1}{p-1}]$

$=\frac{(p+q-3)!}{(p-2)!(q-2)!}\cdot \frac{p-q-2}{(p-1)(q-1)}$

$=\frac{(p+q-2)!}{(p-1)!(q-1)!}$

$=(\genfrac{}{}{0ex}{}{p+q-2}{p-1})$, što je i trebalo pokazati.