Erdős-Szekeres-satsen i kombinatorik är ett påstående som förfinar en av konsekvenserna av Ramsey-satsen för det finita fallet. Medan Ramseys teorem gör det lättare att bevisa att varje sekvens av distinkta reella tal innehåller en monotont ökande oändlig delsekvens eller en monotont minskande oändlig delsekvens, går resultatet som bevisats av Pal Erdős och György Székeres längre. Givet r , s visade de att varje sekvens av distinkta antal längder åtminstone ( r -1)( s -1)+1 innehåller en monotont ökande delsekvens av längden r eller en monotont minskande delsekvens av längden s . Beviset dök upp i samma papper från 1935 som problemet med lyckligt slut . [ett]
För r =3 och s =2 säger formeln att varje permutation av tre tal har en ökande undersekvens av längd tre eller en minskande undersekvens av längd två. Av de sex permutationerna av nummer 1,2,3:
Positionerna för siffrorna i sekvensen kan tolkas som x -koordinater för punkter i det euklidiska planet , och talen i sig som y - koordinater; å andra sidan, för vilken uppsättning punkter som helst i planet, bildar deras y -koordinater, ordnade efter deras x -koordinater, en talföljd (såvida inte två tal har två identiska x - koordinater). Med en sådan koppling mellan sekvenser och uppsättningar av punkter kan Erdős-Székeres-satsen tolkas som påståendet att för varje uppsättning av rs + 1 eller fler punkter finns det en polygonal linje från r positivt lutande segment eller från s segment med en negativ lutning. Till exempel, för r = s = 4, har varje uppsättning med 17 eller fler punkter en kedja av fyra kanter där alla sluttningar har samma tecken.
Erdős-Szekeres sats kan bevisas på flera olika sätt; Michael Steel ger en översikt över sex olika bevis för satsen, inklusive de som använder Dirichlets princip och Dilworths sats . [2] Andra bevis som citeras av Steele inkluderar originalbeviset av Erdős och Székeres och beviset av Blackwell, Lovas och Steele själv. [3] [4] [5] Beviset finns också i boken [6] .
I en sekvens av längd ( r − 1)( s − 1) + 1, markera varje nummer n i med ett par ( a i , b i ), där a i är längden på den största monotont ökande undersekvensen som slutar på n i , b i är längden av den största monotont minskande undersekvensen som slutar på n i . Alla nummer i sekvensen är markerade med olika par: om i < j och n i ≤ n j , då a i < a j ; om n i ≥ n j , då b i < b j . Men det finns bara ( r − 1)( s − 1) möjliga par om a i inte är större än r − 1 och b i inte är större än s − 1, så enligt Dirichlet-principen finns det ett i för vilket antingen a i eller b i är bortom denna begränsning. Om a i är utanför gränserna, så är n i en del av en ökande undersekvens av längden åtminstone r , om bi är utanför gränserna, då är n i en del av en minskande undersekvens av längden åtminstone s .