El teorema de Erdős-Szekeres en combinatoria es un enunciado que refina una de las consecuencias del teorema de Ramsey para el caso finito. Si bien el teorema de Ramsey facilita la demostración de que cada secuencia de números reales distintos contiene una subsecuencia infinita monótonamente creciente o una subsecuencia infinita monótonamente decreciente, el resultado demostrado por Pal Erdős y György Székeres va más allá. Dado r , s , demostraron que cualquier secuencia de números distintos de longitud al menos ( r -1)( s -1)+1 contiene una subsecuencia monótonamente creciente de longitud r o una subsecuencia monótonamente decreciente de longitud s . La demostración apareció en el mismo artículo de 1935 que el problema del final feliz . [una]
Para r =3 ys =2, la fórmula dice que cualquier permutación de tres números tiene una subsecuencia creciente de longitud tres o una subsecuencia decreciente de longitud dos. De las seis permutaciones de los números 1,2,3:
Las posiciones de los números en la secuencia se pueden interpretar como coordenadas x de puntos en el plano euclidiano , y los números mismos como coordenadas y ; por otro lado, para cualquier conjunto de puntos en el plano, sus coordenadas y , ordenadas por sus coordenadas x , forman una secuencia de números (a menos que dos números tengan dos coordenadas x idénticas). Con tal conexión entre secuencias y conjuntos de puntos, el teorema de Erdős-Székeres puede interpretarse como el enunciado de que para cualquier conjunto de rs + 1 o más puntos, existe una línea poligonal de r segmentos inclinados positivamente o de s segmentos con un pendiente negativa. Por ejemplo, para r = s = 4, cualquier conjunto de 17 o más puntos tiene una cadena de cuatro aristas en la que todas las pendientes tienen el mismo signo.
El teorema de Erdős-Szekeres se puede probar de varias maneras diferentes; Michael Steel ofrece una descripción general de seis pruebas diferentes del teorema, incluidas las que utilizan el principio de Dirichlet y el teorema de Dilworth . [2] Otras pruebas citadas por Steele incluyen la prueba original de Erdős y Székeres y la prueba de Blackwell, Lovas y el mismo Steele. [3] [4] [5] La prueba también está en el libro [6] .
En una secuencia de longitud ( r − 1)( s − 1) + 1, marque cada número n i con un par ( a i , b i ), donde a i es la longitud de la subsecuencia monótonamente creciente más grande que termina en n i , b i es la longitud de la subsecuencia monótonamente decreciente más grande que termina en n i . Todos los números en la secuencia están marcados con diferentes pares: si i < j y n i ≤ n j , entonces a i < a j ; si norte yo ≥ norte j , entonces segundo yo < segundo j . Pero solo hay ( r − 1)( s − 1) pares posibles si a i no es mayor que r − 1 y b i no es mayor que s − 1, por lo que según el principio de Dirichlet hay un i para el cual a i o b i está más allá de esta limitación. Si a i está fuera de los límites, entonces n i es parte de una subsecuencia creciente de longitud de al menos r , si b i está fuera de los límites, entonces n i es parte de una subsecuencia decreciente de longitud de al menos s .