Erdős–Szekeres-tétel

A Wikipédiából, a szabad enciklopédiából
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.

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 | forrásszöveg szerkesztése]

Az n = 2 és k = 1 esetre a képlet szerint három szám bármilyen permutációjában találni 3 szám hosszúságú növekvő, vagy 2 szám 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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

Vegyünk egy nk + 1 hosszúságú sorozatot. A sorozat minden ai elemét lássuk el fi,gj címkepárral, ahol fi a leghosszabb, ai-vel végződő monoton növekvő részsorozat hossza, míg gj a leghosszabb, aj-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 összesen csak nk lehetséges címke van, melyek közül fi legfeljebb n, és gi legfeljebb k, ezért a skatulyaelv alapján léteznie kell 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 ji 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, legszisztematikusabbnak bizonyításnak.[2][6]

Dilworth tétele alapján[szerkesztés | forrásszöveg szerkesztése]

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 xy a parciális rendezés szerint, ha fennáll, hogy xy 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

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

Források[szerkesztés | forrásszöveg szerkesztése]

  1. 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>
  2. ^ 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>.
  3. 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>.
  4. 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.
  5. Lovász, László (1979), "Solution to Exercise 14.25", Combinatorial Problems and Exercises, North-Holland is. (Steele 1995) szerint.
  6. 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>.

További információk[szerkesztés | forrásszöveg szerkesztése]