Nejednakost Erdös-Szekeresa je teorem u kombinatorici, odnosno Ramseyjevoj teoriji. Nejednakost predstavlja gornju ogradu za Ramseyjev broj
.[1]
Nejednakost glasi:
, za
.
Nejednakost je nazvana u čast mađarskim matematičarima Paulu Erdösu, jednom od najznačajnijih matematičara 20. stoljeća, i Georgeu Szekeresu.
Indukcijom po zbroju
. Za
tvrdnja vrijedi jer je tada
, te je pritom
.
Pretpostavimo da nejednakost vrijedi za sve parove
za koje je
za neki
. Dokazat ćemo da vrijedi i za sve parove
za koje je
.
Koristimo poznatu nejednakost
. Zbog pretpostavke indukcije dobivamo redom:
![{\displaystyle N(p,q)\leq N(p-1,q)+N(p,q-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9723804cb38930ea298662af69f40b2d3b78c308)
![{\displaystyle \leq {\binom {p-1+q-2}{p-2}}+{\binom {p+q-1-2}{p-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd9591df3f8c07e9837bdff236878e55496f6bc7)
![{\displaystyle ={\frac {p+q-3)!}{(p-2)!(q-1)!}}+{\frac {p+q-3)!}{(p-1)!(q-2)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f59061fe5373bb13470dcaa64cdd0d06f2b4f294)
![{\displaystyle ={\frac {(p+q-3)!}{(p-2)!(q-2)!}}[{\frac {1}{q-1}}+{\frac {1}{p-1}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e99a998256b28ec567cd33db71f2c6fc58f6aaaf)
![{\displaystyle ={\frac {(p+q-3)!}{(p-2)!(q-2)!}}\cdot {\frac {p-q-2}{(p-1)(q-1)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7b5b80b44513ebdcb285091e615fc8100ec657f)
![{\displaystyle ={\frac {(p+q-2)!}{(p-1)!(q-1)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16d0b7beb365f242d6477d757742a8954beace61)
, što je i trebalo pokazati.
- ↑ Darko Veljan, Kombinatorika s teorijom grafova, Školska knjiga, Zagreb, 1989., str. 66, 67.