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.