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.
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[szerkesztés]
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[szerkeszté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[szerkesztés]
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[szerkesztés]
Vegyünk egy nk + 1 hosszúságú sorozatot. A sorozat minden ai elemét lássuk el fi,gi címkepárral, ahol fi a leghosszabb, ai-vel végződő monoton növekvő részsorozat hossza, míg gi a leghosszabb, ai-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 ai < aj, akkor fi < fj, ugyanakkor ha ai > aj, akkor gi > gj. De ha nincs megfelelő részsorozat, akkor összesen csak nk lehetséges címke van: fi legfeljebb n, és gi legfeljebb k. A skatulyaelv alapján léteznie kell tehát olyan i értéknek, amire fi vagy gi kívül esik ezen a tartományon. Ha fi esik kívül, akkor ai tagja egy legalább n + 1 hosszúságú növekvő részsorozatnak, ha pedig gi esik kívül, akkor ai 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[szerkesztés]
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
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.
Jegyzetek[szerkesztés]
- ↑ Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry", Compositio Mathematica 2: 463–470, <http://www.numdam.org/item?id=CM_1935__2__463_0>
- ↑ a b Steele, J. Michael (1995), "Variations on the monotone subsequence theme of Erdős and Szekeres", in Aldous, David; Diaconis, Persi & Spencer, Joel et al., Discrete Probability and Algorithms, vol. 72, IMA Volumes in Mathematics and its Applications, Springer-Verlag, pp. 111–131, <http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf>.
- ↑ Blackwell, Paul (1971), "An alternative proof of a theorem of Erdős and Szekeres", American Mathematical Monthly 78 (3): 273–273, doi:10.2307/2317525, <http://www.jstor.org/stable/2317525>.
- ↑ Hammersley, J. M. (1972), "A few seedlings of research", Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, pp. 345–394. (Steele 1995) szerint.
- ↑ Lovász, László (1979), "Solution to Exercise 14.25", Combinatorial Problems and Exercises, North-Holland is. (Steele 1995) szerint.
- ↑ Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres", Journal of the London Mathematical Society 34: 352, <http://jlms.oxfordjournals.org/cgi/reprint/s1-34/3/352.pdf>.
Fordítás[szerkesztés]
- 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.
További információk[szerkesztés]
- Weisstein, Eric W.: Erdos-Szekeres Theorem (angol nyelven). Wolfram MathWorld
