Teorema de Erdős-Szekeres

En matemáticas, el teorema de Erdős-Szekeres es un resultado de finitud que precisa uno de los corolarios del teorema de Ramsey. Mientras que el teorema de Ramsey facilita probar que toda sucesión infinita de números reales distintos contiene una subsucesión infinita monótonamente creciente o una subsucesión infinita monótonamente decreciente, el resultado que probaron Paul Erdős y George Szekeres va más allá. Para $r$ , $s$ dados, probaron que cualquier sucesión de longitud al menos $(r-1)(s-1)+1$ contiene una subsucesión monótonamente creciente de longitud $r$ o una subsucesión monótonamente decreciente de longitud $s$ . La demostración está en el mismo artículo de 1935 que menciona el problema del final feliz.^[1]

Ejemplo

Para $r=3$ y $s=2$ , la fórmula afirma que cualquier permutación de tres números tiene una subsucesión creciente de longitud tres o una subsucesión decreciente de longitud dos. Tomando las seis posibles permutaciones de los números 1, 2, 3:

1,2,3 tiene una subsucesión creciente consistente en los tres números
1,3,2 tiene una subsucesión decreciente 3,2
2,1,3 tiene una subsucesión decreciente 2,1
2,3,1 tiene dos subsucesiones decrecientes, 2,1 y 3,1
3,1,2 tiene dos subsucesiones decrecientes, 3,1 y 3,2
3,2,1 tiene tres subsucesiones decrecientes de longitud dos, 3,2, 3,1, y 2,1.

Interpretaciones alternativas

Interpretación geométrica

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 $rs-r-s+2$ puntos se puede encontrar un camino poligonal de o bien $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 se puede encontrar un camino poligonal de al menos $\left\lfloor {\sqrt {(}}n-1)\right\rfloor$ 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 un camino de este tipo, probando que este límite es fijo, aplicando una pequeña rotación a una red $(r-1)$ por $(s-1)$ .

Interpretación en patrones de permutación

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.

Demostraciones

El teorema de Erdős-Szekeres se puede probar de varias maneras diferentes;Steele (1995) revisó seis demostraciones diferentes del teorema de Erdős-Szekeres, incluyendo las dos que siguen.^[2] Otras demostraciones revisadas por Steele incluyen la demostración original de Erdős y Szekeres, así como las de Blackwell (1971),^[3]Hammersley (1972),^[4] y Lovász (1979).^[5]

Principio del palomar

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]

Teorema de Dilworth

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

\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.

Véase también

Problema de la subsecuencia más larga

Referencias

↑ Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463-470, Zbl 0012.27010, doi:10.1007/978-0-8176-4842-8_3. .
↑ Steele, J. Michael (1995), «Variations on the monotone subsequence theme of Erdős and Szekeres», en Aldous, David; Diaconis, Persi; Spencer, Joel et al., eds., Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications 72, Springer-Verlag, pp. 111-131, ISBN 0-387-94532-6 ..
↑ Blackwell, Paul (1971), «An alternative proof of a theorem of Erdős and Szekeres», American Mathematical Monthly 78 (3): 273-273, JSTOR 2317525, doi:10.2307/2317525 ..
↑ Hammersley, J. M. (1972), «A few seedlings of research», Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, pp. 345-394 .. As cited by Steele (1995).
↑ Lovász, László (1979), «Solution to Exercise 14.25», Combinatorial Problems and Exercises, North-Holland .. As cited by Steele (1995).
↑ Seidenberg, A. (1959), «A simple proof of a theorem of Erdős and Szekeres», Journal of the London Mathematical Society 34: 352, doi:10.1112/jlms/s1-34.3.352 ..

Enlaces externos

Weisstein, Eric W. «Erdős-Szekeres Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.

Datos: Q976607

[1] Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463-470, Zbl 0012.27010, doi:10.1007/978-0-8176-4842-8_3. .

[steele-2] Steele, J. Michael (1995), «Variations on the monotone subsequence theme of Erdős and Szekeres», en Aldous, David; Diaconis, Persi; Spencer, Joel et al., eds., Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications 72, Springer-Verlag, pp. 111-131, ISBN 0-387-94532-6 ..

[3] Blackwell, Paul (1971), «An alternative proof of a theorem of Erdős and Szekeres», American Mathematical Monthly 78 (3): 273-273, JSTOR 2317525, doi:10.2307/2317525 ..

[4] Hammersley, J. M. (1972), «A few seedlings of research», Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, pp. 345-394 .. As cited by Steele (1995).

[5] Lovász, László (1979), «Solution to Exercise 14.25», Combinatorial Problems and Exercises, North-Holland .. As cited by Steele (1995).

[6] Seidenberg, A. (1959), «A simple proof of a theorem of Erdős and Szekeres», Journal of the London Mathematical Society 34: 352, doi:10.1112/jlms/s1-34.3.352 ..

[1]

[2]

[3]

[4]

[5]

[6]