A matematikában az Erdős–Szekeres-tétel egy véges eredmény, ami Ramsey tételének egyik folyományát teszi precízzé. Míg a Ramsey-tétel segítségével könnyen belátható, hogy bármely különböző valós számokból álló végtelen sorozat tartalmaz vagy egy monoton növekvő, vagy egy monoton csökkenő végtelen részsorozatot, az Erdős Pál és Szekeres György által igazolt tétel ennél tovább megy.

Tétel: Bármely nk + 1 darab különböző számból álló sorozatban van vagy egy n-nél hosszabb csökkenő részsorozat, vagy egy k-nál hosszabb növekvő részsorozat.

A tétel bizonyítása ugyanabban az 1935-ös dolgozatban szerepelt, amelyik a Happy End-problémát is tárgyalja.^[1]

Az n = 2 és k = 1 esetre a képlet szerint három szám bármilyen permutációjában találni 3 hosszúságú növekvő, vagy 2 hosszúságú csökkenő részsorozatot. Az 1,2,3 számok lehetséges hat permutációja:

• 1,2,3: mindhárom számból álló növekvÅ‘ részsorozat
• 1,3,2: csökkenÅ‘ részsorozat: 3,2
• 2,1,3: csökkenÅ‘ részsorozat: 2,1
• 2,3,1: két csökkenÅ‘ részsorozat: 2,1 és 3,1
• 3,1,2: két csökkenÅ‘ részsorozat: 3,1 és 3,2
• 3,2,1: három két szám hosszúságú csökkenÅ‘ részsorozat: 3,2, 3,1 és 2,1.

A sorozat indexei felfoghatók az euklideszi sík pontjainak x-, számai pedig y-koordinátáiként; vagy fordítva, a sík egy ponthalmazát véve a pontok y koordinátái, az x koordináták szerint sorba rendezve (ha semelyik két x koordináta nem egyezik meg) számsorozatot alkotnak. A számsorozatok és ponthalmazok közötti megfeleltetéssel az Erdős–Szekeres-tétel úgy is értelmezhető, hogy bármely, legalább nk + 1 pont közé rajzolható n hosszúságú pozitív vagy k hosszúságú negatív meredekségű töröttvonal. Például az n = k = 4 esetet véve, bármely legalább 17 pontból álló halmaz pontjai között húzható töröttvonal, melynek minden szakaszának meredeksége azonos előjelű. Szemléletes példa hozható arra, hogy a tétel éles, és nk pontra már nem szükségképpen igaz az állítás: mindössze egy n × k-s négyzetrácsot enyhén el kell forgatni, ahogy az ábrán is látható.

Az Erdős–Szekeres-tétel többféle módon igazolható; (Steele 1995) hat különböző bizonyítását tárgyalja, köztük a két lejjebb olvashatót.^[2] A tétel Steele által citált egyéb bizonyításai között szerepel az eredeti, Erdős és Székely által megadott, valamint a következők: (Blackwell 1971)^[3] (Hammersley 1972),^[4] és (Lovász 1979).^[5]

Vegyünk egy nk + 1 hosszúságú sorozatot. A sorozat minden a_i elemét lássuk el f_i,g_i címkepárral, ahol f_i a leghosszabb, a_i-vel végződő monoton növekvő részsorozat hossza, míg g_i a leghosszabb, a_i-vel végződő monoton csökkenő részsorozat hossza. A sorozat bármely két számához különböző címkepár tartozik: ha i < j és a_i < a_j, akkor f_i < f_j, ugyanakkor ha a_i > a_j, akkor g_i > g_j. De ha nincs megfelelő részsorozat, akkor összesen csak nk lehetséges címke van: f_i legfeljebb n, és g_i legfeljebb k. A skatulyaelv alapján léteznie kell tehát olyan i értéknek, amire f_i vagy g_i kívül esik ezen a tartományon. Ha f_i esik kívül, akkor a_i tagja egy legalább n + 1 hosszúságú növekvő részsorozatnak, ha pedig g_i esik kívül, akkor a_i tagja egy legalább k + 1 hosszúságú csökkenő részsorozatnak.

(Steele 1995) ezt a bizonyítást (Seidenberg 1959) egyoldalas munkájának tulajdonítja, és az általa vizsgáltak közül ezt tartja a legügyesebb, legszisztematikusabb bizonyításnak.^[2][6]

Egy másik bizonyítás a részbenrendezett halmazok láncfelbontásaival foglalkozó Dilworth-tételt, vagy annak egyszerűbb duálisát, a Mirsky-tételt használja fel.

A bizonyításhoz definiáljunk a sorozat elemei között egy parciális rendezést, amelyben x ≤ y a parciális rendezés szerint, ha fennáll, hogy x ≤ y mint számok, és x nem szerepel y-nál később a sorozatban. Ebben a parciális rendezésben egy lánc megfeleltethető egy monoton növekvő részsorozatnak, egy antilánc pedig egy monoton csökkenő részsorozatnak. A Mirsky-tétel alapján vagy létezik n + 1 hosszú lánc, vagy a részsorozat felbontható legfeljebb n + 1 antiláncra; ám ebben az esetben a leghosszabb antiláncnak olyan monoton csökkenő részsorozatnak kell lennie, melynek hossza minimálisan

${\displaystyle \left\lceil {\frac {(n+1)(k+1)-(k+1)+2}{n}}\right\rceil =k+1.}$

A Dilworth-tételből közvetlenül is adódik, hogy vagy létezik k + 1 hosszúságú antilánc, vagy a részsorozat felbontható legfeljebb k láncra, melyek közül a leghosszabb legalább n + 1 elemből áll.

• Ez a szócikk részben vagy egészben az ErdÅ‘s–Szekeres theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztÅ‘it annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzÅ‘i jogokat jelzi, nem szolgál a cikkben szereplÅ‘ információk forrásmegjelöléseként.

• Weisstein, Eric W.: Erdos-Szekeres Theorem (angol nyelven). Wolfram MathWorld