Nejednakost Erdös-Szekeresa

Za druga značenja pogledajte Erdős–Szekeresova konjektura, Erdős–Szekeresov poučak odnosno Problem sa sretnim završetkom.

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)\leq {\binom {p+q-2}{p-1}}$, za $p,q\geq 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\leq {\binom {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)\leq N(p-1,q)+N(p,q-1)$. Zbog pretpostavke indukcije dobivamo redom:

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

$\leq {\binom {p-1+q-2}{p-2}}+{\binom {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)!}}$

$={\binom {p+q-2}{p-1}}$, što je i trebalo pokazati.