Teorema de Erdős-Szekeres

Se pueden interpretar las posiciones de los números en una sucesión como las coordenadas x de puntos en el plano euclídeo, y los propios números como coordenadas y; recíprocamente, para cualquier conjunto de puntos en el plano, las coordenadas y de los puntos, ordenadas por sus coordenadas x, forman una sucesión de números (a menos que dos de los puntos tengan iguales coordenadas x). Con esta relación entre sucesiones y conjuntos de puntos, el teorema de Erdős-Szekeres se puede interpretar como que en cualquier conjunto de al menos ${\displaystyle rs-r-s+2}$ puntos se puede encontrar un camino poligonal de o bien ${\displaystyle r-1}$ aristas de pendiente positiva o ${\displaystyle s-1}$ aristas de pendiente negativa. En particular (tomando ${\displaystyle r=s}$), en cualquier conjunto de al menos n puntos se puede encontrar un camino poligonal de al menos ${\displaystyle \left\lfloor {\sqrt {(}}n-1)\right\rfloor }$ aristas con pendientes del mismo signo. Por ejemplo, tomando ${\displaystyle 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 ${\displaystyle rs-r-s+1}$ puntos sin un camino de este tipo, probando que este límite es fijo, aplicando una pequeña rotación a una red ${\displaystyle (r-1)}$ por ${\displaystyle (s-1)}$.

El teorema de Erdős-Szekeres también se puede interpretar en el lenguaje de los patrones de permutación como que toda permutación de longitud al menos rs + 1 debe contener o bien el patrón 1, 2, 3, …, r + 1 o el patrón s + 1, s, …, 2, 1.

Dada una sucesión de longitud (r − 1)(s − 1) + 1, se etiqueta cada número n_i en la sucesión con el par (a_i,b_i), donde a_i es la longitud de la mayor subsucesión monótonamente creciente que termina en n_i y b_i es la longitud de la mayor subsucesión monótonamente decreciente que termina en n_i. Cada par de números en la sucesión se etiqueta con un par diferente: si i < j y n_i ≤ n_j entonces a_i < a_j, y por otra parte si n_i ≥ n_j entonces b_i < b_j. Pero existen solo (r − 1)(s − 1) etiquetas posibles si a_i es a lo sumo r − 1 y b_i es a lo sumo s − 1, por lo que por el principio del palomar debe existir un valor de i para el que a_i o b_i esté fuera de este rango. Si a_i está fuera del rango, entonces n_i es parte de una subsucesión creciente de longitud al menos r, y si b_i está fuera del rango entonces n_i es parte de una sucesión decreciente de longitud al menos s.Steele (1995) referencia esta demostración en el artículo de una página de Seidenberg (1959) y la llama «la más astuta y sistemática» de las demostraciones que revisa.[6]

Otras de las demostraciones utiliza el teorema de Dilworth de descomposición de cadenas en órdenes parcial, o su dual más sencillo (teorema de Mirsky).

Para probar el teorema, se define un orden parcial en los miembros de la sucesión, en el que x es menor o igual que y en el orden parcial si x ≤ y como números y x no va después de y en la sucesión. Una cadena en este orden parcial es una subsucesión monótonamente creciente, y su anticadena es una subsucesión monótonamente decreciente. Por el teorema de Mirsky, o bien existe una cadena de longitud r, o la sucesión se puede partir en como mucho r − 1 anticadenas; pero en ese caso la mayor de las anticadenas debe formar una subsucesión decreciente con longitud al menos

${\displaystyle \left\lceil {\frac {rs-r-s+2}{r-1}}\right\rceil =s}$.

Alternativamente, usando el propio teorema de Dilworth, o bien existe una anticadena de longitud s o la sucesión se puede partir en como mucho s − 1 cadenas, la mayor de las cuales debe tener longitud al menos r.