Teorema Erdős-Szekeres în combinatorică este o afirmație care rafinează una dintre consecințele teoremei Ramsey pentru cazul finit. În timp ce teorema lui Ramsey face mai ușor să se demonstreze că fiecare șir de numere reale distincte conține o subsecvență infinită monoton crescătoare sau o subsecvență infinită monoton descrescătoare, rezultatul demonstrat de Pal Erdős și György Székeres merge mai departe. Având în vedere r , s , au arătat că orice succesiune de numere distincte de lungime cel puțin ( r -1)( s -1)+1 conține o subsecvență monoton crescătoare a lungimii r sau o subsecvență monoton descrescătoare a lungimii s . Dovada a apărut în aceeași lucrare din 1935 ca problema cu finalul fericit . [unu]
Pentru r =3 și s =2, formula spune că orice permutare a trei numere are o subsecvență crescătoare a lungimii trei sau o subsecvență descrescătoare a lungimii doi. Din cele șase permutări ale numerelor 1,2,3:
Pozițiile numerelor din șir pot fi interpretate ca coordonate x ale punctelor din planul euclidian , iar numerele în sine ca coordonate y ; pe de altă parte, pentru orice set de puncte din plan, coordonatele lor y , ordonate după coordonatele lor x , formează o succesiune de numere (cu excepția cazului în care două numere au două coordonate x identice). Cu o astfel de conexiune între secvențe și mulțimi de puncte, teorema Erdős-Székeres poate fi interpretată ca afirmația că pentru orice mulțime de rs + 1 sau mai multe puncte, există o linie poligonală din r segmente înclinate pozitiv sau din s segmente cu o panta negativa. De exemplu, pentru r = s = 4, orice set de 17 sau mai multe puncte are un lanț de patru muchii în care toate pantele au același semn.
Teorema Erdős-Szekeres poate fi demonstrată în mai multe moduri diferite; Michael Steel oferă o imagine de ansamblu a șase dovezi diferite ale teoremei, inclusiv cele care folosesc principiul lui Dirichlet și teorema lui Dilworth . [2] Alte dovezi citate de Steele includ proba originală de Erdős și Székeres și proba de Blackwell, Lovas și Steele însuși. [3] [4] [5] Dovada se află și în carte [6] .
Într-o succesiune de lungime ( r − 1)( s − 1) + 1, marcați fiecare număr n i cu o pereche ( a i , b i ), unde a i este lungimea celei mai mari subsecvențe monoton care se termină în n i , b i este lungimea celei mai mari subsecvențe monoton descrescătoare care se termină în n i . Toate numerele din succesiune sunt marcate cu perechi diferite: dacă i < j și n i ≤ n j , atunci a i < a j ; dacă n i ≥ n j , atunci b i < b j . Dar există doar ( r − 1)( s − 1) perechi posibile dacă a i nu este mai mare decât r − 1 și b i nu este mai mare decât s − 1, deci după principiul Dirichlet există un i pentru care fie a i sau b i depășește această limitare. Dacă a i este în afara limitelor, atunci n i face parte dintr-o subsecvență crescătoare de lungime cel puțin r , dacă b i este în afara limitelor, atunci n i este o parte a unei subsecvențe descrescătoare de lungime cel puțin s .