Erdős-Szekeres sætning

Erdős-Szekeres-sætningen i kombinatorik  er et udsagn, der forfiner en af ​​konsekvenserne af Ramsey-sætningen for det endelige tilfælde. Mens Ramseys sætning gør det lettere at bevise, at hver sekvens af distinkte reelle tal indeholder en monotont stigende uendelig delsekvens eller en monotont aftagende uendelig delsekvens, går resultatet bevist af Pal Erdős og György Székeres længere. Givet r , s , viste de, at enhver sekvens af distinkte antal længder på mindst ( r -1)( s -1)+1 indeholder en monotont stigende delsekvens af længden r eller en monotont aftagende delsekvens af længden s . Beviset dukkede op i det samme papir fra 1935 som problemet med den lykkelige slutning . [en]

Eksempel

For r =3 og s =2 siger formlen, at enhver permutation af tre tal har en stigende undersekvens af længde tre eller en faldende undersekvens af længde to. Af de seks permutationer af tallene 1,2,3:

Geometrisk fortolkning

Positionerne af tallene i sekvensen kan fortolkes som x - koordinater af punkter i det euklidiske plan , og tallene i sig selv som y - koordinater; på den anden side, for ethvert sæt af punkter i planet, danner deres y -koordinater, ordnet efter deres x -koordinater, en talfølge (medmindre to tal har to identiske x - koordinater). Med en sådan forbindelse mellem sekvenser og sæt af punkter kan Erdős-Székeres sætning tolkes som udsagnet om, at for ethvert sæt af rs + 1 eller flere punkter er der en polygonal linje fra r  positivt skrå segmenter eller fra s segmenter med en negativ hældning. For eksempel, for r = s = 4, har ethvert sæt af 17 eller flere punkter en kæde af fire kanter, hvor alle skråninger har samme fortegn.

Bevis

Erdős-Szekeres-sætningen kan bevises på flere forskellige måder; Michael Steel giver et overblik over seks forskellige beviser for sætningen, herunder dem, der bruger Dirichlets princip og Dilworths sætning . [2] Andre beviser citeret af Steele inkluderer det originale bevis af Erdős og Székeres og beviset af Blackwell, Lovas og Steele selv. [3] [4] [5] Beviset findes også i bogen [6] .

Dirichlets princip

I en sekvens af længde ( r  − 1)( s  − 1) + 1 skal du markere hvert tal n i med et par ( a i , b i ), hvor a i er længden af ​​den største monotont stigende undersekvens, der ender på n i , b i er længden af ​​den største monotont aftagende undersekvens, der ender på n i . Alle tal i rækkefølgen er markeret med forskellige par: hvis i < j og n i ≤ n j , så a i < a j ; hvis n i ≥ n j , så er b i < b j . Men der er kun ( r  − 1)( s  − 1) mulige par, hvis a i ikke er større end r  − 1 og b i ikke er større end s  − 1, så efter Dirichlet-princippet er der et i , for hvilket enten a i eller b i er uden for denne begrænsning. Hvis a i er uden for grænserne, så er n i en del af en stigende delsekvens af længde mindst r , hvis bi er uden for grænserne, så er n i en del af en aftagende delsekvens af længde mindst s .

Dilworths teorem

Se også

Noter

  1. Erdős, Paul ; Szekeres, George (1935), A combinatorial problem in geometry , Compositio Mathematica bind 2: 463–470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > Arkiveret 19. februar 2019 på Wayback Machine 
  2. 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, s. 111–131 , < http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf > Arkiveret 11. juni 2019 på Wayback Machine . 
  3. Blackwell, Paul (1971), Et alternativt bevis på en teorem af Erdős og Szekeres , American Mathematical Monthly bind 78 (3): 273–273 , DOI 10.2307/2317525  .
  4. Hammersley, JM (1972), Et par frøplanter af forskning, Proc. 6. Berkeley Symp. Matematik. stat. Prob. , University of California Press, s. 345-394  .
  5. Lovász, László (1979), Solution to Exercise 14.25, Combinatorial Problems and Exercises , North-Holland  .
  6. Combinatorial theory, 1982 , s. 514.

Kilder

Litteratur