Nejednakost Erdös-Szekeresa je teorem u kombinatorici, odnosno Ramseyjevoj teoriji. Nejednakost predstavlja gornju ogradu za Ramseyjev broj .Darko Veljan, Kombinatorika s teorijom grafova, Školska knjiga, Zagreb, 1989., str. 66, 67.
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.
Dokaz 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.
Izvori
Kategorija:Matematika