Erdős-Szekeres tétel

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]

Példa

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:

Geometriai értelmezés

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

Bizonyítás

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

Dirichlet-elv

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 .

Dilworth tétele

Lásd még

Jegyzetek

  1. Erdős, Paul ; Szekeres, George (1935), A kombinatorikai probléma a geometriában , Compositio Mathematica vol. 2: 463–470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > Archivált : 2019. február 19. a Wayback Machine -nél 
  2. Steele, J. Michael (1995), Variations on the monotone subsequence theme of Erdős and Szekeres , in Aldous, David ; Diaconis, Persi & Spencer, Joel és mtsai, Discrete Probability and Algorithms , vol. 72, IMA Volumes in Mathematics and its Applications, Springer-Verlag, p. 111–131 ., < http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf > Archivált : 2019. június 11. a Wayback Machine -nél . 
  3. Blackwell, Paul (1971), Erdős és Szekeres tételének alternatív bizonyítéka , American Mathematical Monthly 78. kötet (3): 273–273 , DOI 10.2307/2317525  .
  4. Hammersley, JM (1972), A kutatás néhány csemetéje, Proc. 6. Berkeley Symp. Math. statisztika. Prob. , University of California Press, p. 345–394  .
  5. Lovász László (1979), Megoldás a 14.25. feladathoz, Kombinatorikus problémák és gyakorlatok , North-Holland  .
  6. Kombinatorikus elmélet, 1982 , p. 514.

Források

Irodalom