En matemáticas , el teorema de Erdős-Szekeres afirma que, dados r , s, cualquier secuencia de números reales distintos con longitud al menos ( r − 1)( s − 1) + 1 contiene una subsecuencia monótonamente creciente de longitud r o una subsecuencia monótonamente decreciente. subsecuencia de longitud s . La prueba apareció en el mismo artículo de 1935 que menciona el problema del final feliz . [1]
Es un resultado finito que precisa uno de los corolarios del teorema de Ramsey . Si bien el teorema de Ramsey facilita demostrar que toda secuencia infinita de números reales distintos contiene una subsecuencia infinita monótonamente creciente o una subsecuencia infinita monótonamente decreciente, el resultado demostrado por Paul Erdős y George Szekeres va más allá.
Para r = 3 y s = 2, la fórmula nos dice que cualquier permutación de tres números tiene una subsecuencia creciente de longitud tres o una subsecuencia decreciente de longitud dos. Entre las seis permutaciones de los números 1,2,3:
Se pueden interpretar las posiciones de los números en una secuencia como coordenadas x de puntos en el plano euclidiano , y los números mismos como coordenadas y ; a la inversa, para cualquier punto establecido en el plano, las coordenadas y de los puntos, ordenadas por sus coordenadas x , forman una secuencia de números (a menos que dos de los puntos tengan coordenadas x iguales ). Con esta traducción entre secuencias y conjuntos de puntos, se puede interpretar que el teorema de Erdős-Szekeres establece que en cualquier conjunto de al menos rs − r − s + 2 puntos podemos encontrar una trayectoria poligonal de r − 1 aristas de pendiente positiva o s − 1 aristas de pendiente negativa. En particular (tomando r = s ), en cualquier conjunto de al menos n puntos podemos encontrar un camino poligonal de al menos ⌊ √ n -1 ⌋ aristas con pendientes del mismo signo. Por ejemplo, tomando r = s = 5, cualquier conjunto de al menos 17 puntos tiene un camino de cuatro aristas en el que todas las pendientes tienen el mismo signo.
Se puede formar un ejemplo de rs − r − s + 1 puntos sin tal camino, que muestra que este límite es estrecho, aplicando una pequeña rotación a una cuadrícula ( r − 1) por ( s − 1).
El teorema de Erdős-Szekeres también puede interpretarse en el lenguaje de los patrones de permutación como si estableciera que cada permutación de longitud al menos ( r - 1)( s - 1) + 1 debe contener el patrón 12⋯ r o el patrón s ⋯21 .
El teorema de Erdős-Szekeres se puede demostrar de varias formas diferentes; Steele (1995) analiza seis demostraciones diferentes del teorema de Erdős-Szekeres, incluidas las dos siguientes. [2] Otras pruebas examinadas por Steele incluyen la prueba original de Erdős y Szekeres, así como las de Blackwell (1971), [3] Hammersley (1972), [4] y Lovász (1979). [5]
Dada una secuencia de longitud ( r − 1)( s − 1) + 1, etiquete cada número n i en la secuencia con el par ( a i , b i ), donde a i es la longitud del final de subsecuencia que aumenta monótonamente más largo con n i y b i es la longitud de la subsecuencia monótonamente decreciente más larga que termina en n i . Cada dos números en la secuencia están etiquetados con un par diferente: si i < j y n i < n j entonces a i < a j , y por otro lado si n i > n j entonces b i < b j . Pero sólo hay ( r − 1)( s − 1) etiquetas posibles si a i es como máximo r − 1 y b i es como máximo s − 1, por lo que, según el principio del casillero , debe existir un valor de i para el cual a i o b i está fuera de este rango. Si a i está fuera de rango, entonces ni es parte de una secuencia creciente de longitud al menos r , y si b i está fuera de rango, entonces ni es parte de una secuencia decreciente de longitud al menos s .
Steele (1995) atribuye esta prueba al artículo de una página de Seidenberg (1959) y la llama "la más hábil y sistemática" de las pruebas que examina. [2] [6]
Otra de las demostraciones utiliza el teorema de Dilworth sobre descomposiciones en cadena en órdenes parciales, o su dual más simple ( teorema de Mirsky ).
Para probar el teorema, defina un orden parcial de los miembros de la secuencia, en el que x es menor o igual que y en el orden parcial si x ≤ y como números y x no es posterior a y en la secuencia. Una cadena en este orden parcial es una subsecuencia monótonamente creciente y una anticadena es una subsecuencia monótonamente decreciente. Según el teorema de Mirsky, o hay una cadena de longitud r , o la secuencia puede dividirse en como máximo r − 1 anticadenas; pero en ese caso la mayor de las anticadenas debe formar una subsecuencia decreciente con una longitud al menos
Alternativamente, según el propio teorema de Dilworth, hay una anticadena de longitud s o la secuencia puede dividirse en como máximo s − 1 cadenas, la más larga de las cuales debe tener una longitud de al menos r .
El resultado también puede obtenerse como corolario de la correspondencia Robinson-Schensted .
Recuerde que la correspondencia Robinson-Schensted asocia a cada secuencia un cuadro de Young P cuyas entradas son los valores de la secuencia. El cuadro P tiene las siguientes propiedades:
Ahora bien, no es posible ajustar ( r − 1)( s − 1) + 1 entradas en un cuadro cuadrado de tamaño ( r − 1)( s − 1), de modo que la primera fila tenga una longitud de al menos r o la última fila tiene una longitud de al menos s .
