Teorema de Erdős-Szekeres

(Redirigido desde «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 , dados, probaron que cualquier sucesión de longitud al menos contiene una subsucesión monótonamente creciente de longitud o una subsucesión monótonamente decreciente de longitud . La demostración está en el mismo artículo de 1935 que menciona el problema del final feliz.[1]

Un camino de cuatro aristas ascendentes en un conjunto de 17 puntos. Por el teorema de Erdős-Szekeres, todo conjunto de 17 puntos tiene un camino de esta longitud bien ascendente o bien descendente. El subconjunto de 16 puntos que no incluye el punto central no tiene ningún camino de este tipo.

Ejemplo

editar

Para   y  , 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

editar

Interpretación geométrica

editar

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   puntos se puede encontrar un camino poligonal de o bien   aristas de pendiente positiva o   aristas de pendiente negativa. En particular (tomando  ), en cualquier conjunto de al menos n puntos se puede encontrar un camino poligonal de al menos   aristas con pendientes del mismo signo. Por ejemplo, tomando  , 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   puntos sin un camino de este tipo, probando que este límite es fijo, aplicando una pequeña rotación a una red   por  .

Interpretación en patrones de permutación

editar

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

editar

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

editar

Dada una sucesión de longitud (r − 1)(s − 1) + 1, se etiqueta cada número ni en la sucesión con el par (ai,bi), donde ai es la longitud de la mayor subsucesión monótonamente creciente que termina en ni y bi es la longitud de la mayor subsucesión monótonamente decreciente que termina en ni. Cada par de números en la sucesión se etiqueta con un par diferente: si i < j y ninj entonces ai < aj, y por otra parte si ninj entonces bi < bj. Pero existen solo (r − 1)(s − 1) etiquetas posibles si ai es a lo sumo r − 1 y bi es a lo sumo s − 1, por lo que por el principio del palomar debe existir un valor de i para el que ai o bi esté fuera de este rango. Si ai está fuera del rango, entonces ni es parte de una subsucesión creciente de longitud al menos r, y si bi está fuera del rango entonces ni 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

editar

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

 .

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

editar

Referencias

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

Enlaces externos

editar