En matemáticas , el teorema de Erdős-Szekeres es un resultado final que precisa uno de los corolarios del teorema de Ramsey . Si bien el teorema de Ramsey facilita la demostración de que cada secuencia infinita de números reales distintos contiene una subsecuencia infinita que aumenta monótonamente o una subsecuencia infinita que disminuye monótonamente, el resultado demostrado por Paul Erds y George Szekeres va más allá. Para r , s dados , mostraron que cualquier secuencia de números reales distintos con una longitud de al menos ( r - 1) ( s - 1) + 1 contiene una subsecuencia de longitud que aumenta monótonamente r o una subsecuencia decreciente monótonamente de longitud s . La prueba apareció en el mismo artículo de 1935 que menciona el problema del final feliz . [1]
Ejemplo
Para r = 3 ys = 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:
- 1,2,3 tiene una subsecuencia creciente que consta de los tres números
- 1,3,2 tiene una subsecuencia decreciente 3,2
- 2,1,3 tiene una subsecuencia decreciente 2,1
- 2,3,1 tiene dos subsecuencias decrecientes, 2,1 y 3,1
- 3,1,2 tiene dos subsecuencias decrecientes, 3,1 y 3,2
- 3,2,1 tiene tres subsecuencias de longitud 2 decrecientes, 3,2, 3,1 y 2,1.
Interpretaciones alternativas
Interpretación geométrica
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, el teorema de Erdős-Szekeres se puede interpretar en el sentido de 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 una trayectoria 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 una trayectoria de cuatro bordes en la que todas las pendientes tienen el mismo signo.
Un ejemplo de puntos rs - r - s + 1 sin una ruta de este tipo, que muestra que este límite es estrecho, se puede formar aplicando una pequeña rotación a una cuadrícula ( r - 1) por ( s - 1).
Interpretación del patrón de permutación
El teorema de Erdős-Szekeres también se puede interpretar en el lenguaje de los patrones de permutación en el sentido de que toda permutación de longitud al menos rs + 1 debe contener el patrón 1, 2, 3, ..., r + 1 o el patrón s + 1, s , ..., 2, 1.
Pruebas
El teorema de Erdős-Szekeres se puede demostrar de varias formas diferentes; Steele (1995) examina seis pruebas 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]
Principio del casillero
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 de la terminación de subsecuencia que aumenta monótonamente más larga con n i y b i es la longitud de la subsecuencia decreciente monótonamente más larga que termina con 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 solo 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 de 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 n i es parte de una secuencia creciente de longitud al menos r , y si b i está fuera de rango, entonces n i 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]
Teorema de Dilworth
Otra de las demostraciones usa el teorema de Dilworth sobre descomposiciones en cadena en órdenes parciales, o su dual más simple ( teorema de Mirsky ).
Para demostrar el teorema, defina un orden parcial de los miembros de la secuencia, en el que x es menor o igual ay en el orden parcial si x ≤ y como números yx no es posterior a y en la secuencia. Una cadena en este orden parcial es una subsecuencia que aumenta monótonamente, y una antichain es una subsecuencia que disminuye monótonamente. Según el teorema de Mirsky, o hay una cadena de longitud r , o la secuencia se puede dividir en como máximo r - 1 antichains; pero en ese caso, el mayor de los antichains debe formar una subsecuencia decreciente con una longitud al menos
Alternativamente, según el propio teorema de Dilworth, existe una antichain de longitud s , o la secuencia se puede dividir en como máximo s - 1 cadenas, la más larga de las cuales debe tener una longitud de al menos r .
Aplicación de la correspondencia Robinson-Schensted
El resultado también puede obtenerse como corolario de la correspondencia Robinson-Schensted .
Recuerde que la correspondencia de 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:
- La longitud de la más larga subsecuencia creciente es igual a la longitud de la primera fila de P .
- La longitud de la subsecuencia decreciente más largo es igual a la longitud de la primera columna de P .
Ahora, no es posible ajustar ( r - 1) ( s - 1) + 1 entradas en una caja cuadrada de tamaño ( r - 1) ( s - 1), por lo que la primera fila tiene una longitud de al menos r o la última fila tiene una longitud de al menos s .
Ver también
Referencias
- ^ Erdős, Paul ; Szekeres, George (1935), "Un problema combinatorio en geometría" , Compositio Mathematica , 2 : 463–470, doi : 10.1007 / 978-0-8176-4842-8_3 , Zbl 0012.27010 .
- ^ a b Steele, J. Michael (1995), "Variaciones sobre el tema de la subsecuencia monótona de Erdős y Szekeres", en Aldous, David ; Diaconis, Persi ; Spencer, Joel ; Steele, J. Michael (eds.), Probabilidad discreta y algoritmos (PDF) , Volúmenes IMA en matemáticas y sus aplicaciones, 72 , Springer-Verlag, págs. 111-131, ISBN 0-387-94532-6.
- ^ Blackwell, Paul (1971), "Una prueba alternativa de un teorema de Erdős y Szekeres", American Mathematical Monthly , 78 (3): 273-273, doi : 10.2307 / 2317525 , JSTOR 2317525.
- ^ Hammersley, JM (1972), "Algunas plántulas de investigación", Proc. 6th Berkeley Symp. Matemáticas. Stat. Prob. , University of California Press, págs. 345–394. Como lo cita Steele (1995) .
- ^ Lovász, László (1979), "Solución del ejercicio 14.25", Problemas y ejercicios combinatorios , Holanda Septentrional. Como lo cita Steele (1995) .
- ^ Seidenberg, A. (1959), "Una demostración simple de un teorema de Erdős y Szekeres" (PDF) , Journal of the London Mathematical Society , 34 : 352, doi : 10.1112 / jlms / s1-34.3.352[ enlace muerto ] .
enlaces externos
- Weisstein, Eric W. "Teorema de Erdős-Szekeres" . MathWorld .