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]
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:
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.
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] .
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 .