A kombinatorika Erdős-Szekeres tétele egy olyan állítás, amely a Ramsey-tétel egyik következményét finomítja a véges esetre. Míg Ramsey tétele megkönnyíti annak bizonyítását, hogy minden különálló valós számsorozat tartalmaz monoton növekvő végtelen részsorozatot vagy monotonan csökkenő végtelen részsorozatot, addig az Erdős Pal és Székeres György által bizonyított eredmény tovább megy. Adott r , s , megmutatták, hogy bármely, legalább ( r -1)( s -1)+1 hosszúságú különböző számú sorozat tartalmaz egy monoton növekvő r hosszúságú részsorozatot vagy egy monotonan csökkenő s hosszúságú részsorozatot . A bizonyíték ugyanabban az 1935-ös újságban jelent meg, mint a happy end probléma . [egy]
r =3 és s =2 esetén a képlet azt mondja, hogy három szám bármely permutációja növekvő három hosszúságú részsorozattal vagy csökkenő kettes hosszúságú részsorozattal rendelkezik. Az 1, 2, 3 számok hat permutációja közül:
A számok helyzete a sorozatban értelmezhető az euklideszi sík pontjainak x -koordinátájaként , maguk a számok pedig y - koordinátákként; másrészt a sík bármely ponthalmazához az x koordinátáik szerint rendezett y -koordinátáik számsort alkotnak (kivéve, ha két számnak két azonos x - koordinátája van). A sorozatok és ponthalmazok ilyen kapcsolata esetén az Erdős-Székeres tétel úgy értelmezhető, mint az az állítás, hogy bármely rs + 1 vagy több pont halmazára van egy sokszögű egyenes r pozitív hajlású szakaszból vagy s szakaszból egy negatív meredekség. Például r = s = 4 esetén bármely 17 vagy több pontból álló halmaz négy élből álló lánccal rendelkezik, amelyben minden lejtő azonos előjelű.
Az Erdős-Szekeres tétel többféleképpen bizonyítható; Michael Steel áttekintést ad a tétel hat különböző bizonyításáról, köztük a Dirichlet-elvet és a Dilworth-tételt használókról . [2] A Steele által idézett további bizonyítékok közé tartozik Erdős és Székeres eredeti bizonyítása, valamint Blackwell, Lovas és maga Steele. [3] [4] [5] A bizonyítás a [6] könyvben is megtalálható .
Az ( r − 1)( s − 1) + 1 hosszúságú sorozatban jelölje meg minden n i számot egy ( a i , b i ) párral, ahol a i a legnagyobb monoton növekvő részsorozat hossza, amely n i -re végződik. , b i a legnagyobb monoton csökkenő n i -re végződő részsorozat hossza . A sorozatban szereplő összes szám különböző párokkal van jelölve: ha i < j és n i ≤ n j , akkor a i < a j ; ha n i ≥ n j , akkor b i < b j . De csak ( r − 1)( s − 1) lehetséges pár van, ha a i nem nagyobb r − 1-nél és b i nem nagyobb s − 1-nél, tehát a Dirichlet-elv szerint van olyan i , amelyre vagy a i vagy b i túl van ezen a korláton. Ha a i határon kívül van, akkor n i egy legalább r hosszúságú növekvő részsorozat része , ha b i határon kívül van, akkor n i egy legalább s hosszúságú csökkenő részsorozat része .