Erdős–Szekeres-tétel

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.

4 pozitív meredekségű él alkotta útvonal egy 17 pontból álló halmazban. Ha az x-koordináták szerint sorba rendezett pontok y-koordinátáiból sorozatot alkotunk, az Erdős–Szekeres-tétel biztosítja, hogy vagy ilyen élsorozatot találunk, vagy olyat, ahol mind a négy él meredeksége ≤ 0. Ha azonban a középső pontot elhagyjuk, nem találunk ilyen útvonalat.

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]

Példa

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.

Mértani értelmezés

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ó.

Bizonyítások

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]

Skatulyaelv alapján

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]

Dilworth tétele alapján

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.