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:
-
-
-
-
-
-
- , što je i trebalo pokazati.
- ↑ Darko Veljan, Kombinatorika s teorijom grafova, Školska knjiga, Zagreb, 1989., str. 66, 67.