En matemáticas , el " problema del final feliz " (llamado así por Paul Erdős porque condujo al matrimonio de George Szekeres y Esther Klein [1] ) es la siguiente afirmación:
- Teorema : cualquier conjunto de cinco puntos en el plano en posición general [2] tiene un subconjunto de cuatro puntos que forman los vértices de un cuadrilátero convexo .
Este fue uno de los resultados originales que llevaron al desarrollo de la teoría de Ramsey .
El teorema del final feliz se puede demostrar mediante un análisis de caso simple: si cuatro o más puntos son vértices del casco convexo , se pueden elegir cuatro puntos cualesquiera. Si por el contrario, el casco convexo tiene la forma de un triángulo con dos puntos en su interior, se pueden elegir los dos puntos interiores y uno de los lados del triángulo. Ver Peterson (2000) para una explicación ilustrada de esta prueba, y Morris y Soltan (2000) para una revisión más detallada del problema.
La conjetura de Erdős-Szekeres establece precisamente una relación más general entre el número de puntos en un conjunto de puntos de posición general y su polígono convexo más grande , a saber, que el número más pequeño de puntos para los cuales cualquier disposición de posición general contiene un subconjunto convexo de puntos es . Aún no se ha probado, pero se conocen límites menos precisos.
Polígonos más grandes
Erdős & Szekeres (1935) demostraron la siguiente generalización:
- Teorema : para cualquier entero positivo N , cualquier conjunto finito suficientemente grande de puntos en el plano en posición general tiene un subconjunto de N puntos que forman los vértices de un polígono convexo.
La prueba apareció en el mismo artículo que prueba el teorema de Erdős-Szekeres sobre subsecuencias monótonas en secuencias de números.
Sea f ( N ) el mínimo M para el cual cualquier conjunto de M puntos en posición general debe contener un N -gon convexo . Se sabe que
- f (3) = 3, trivialmente.
- f (4) = 5. [3]
- f (5) = 9. [4] En la ilustración se muestra un conjunto de ocho puntos sin pentágono convexo , lo que demuestra que f (5)> 8; la parte más difícil de la demostración es mostrar que cada conjunto de nueve puntos en posición general contiene los vértices de un pentágono convexo.
- f (6) = 17. [5]
- El valor de f ( N ) es desconocido para todo N > 6. Por el resultado de Erdős & Szekeres (1935) se sabe que es finito.
Sobre la base de los valores conocidos de f ( N ) para N = 3, 4 y 5, Erdős y Szekeres conjeturaron en su artículo original que
Posteriormente demostraron, mediante la construcción de ejemplos explícitos, que
pero el límite superior más conocido cuando N ≥ 7 es
Polígonos convexos vacíos
También está la cuestión de si cualquier conjunto suficientemente grande de puntos en posición general tiene un cuadrilátero convexo, un pentágono, etc. "vacío", es decir, uno que no contiene ningún otro punto de entrada. La solución original al problema del final feliz se puede adaptar para mostrar que cualesquiera cinco puntos en posición general tienen un cuadrilátero convexo vacío, como se muestra en la ilustración, y diez puntos cualesquiera en posición general tienen un pentágono convexo vacío. [8] Sin embargo, existen conjuntos de puntos arbitrariamente grandes en posición general que no contienen heptágono convexo vacío . [9]
Durante mucho tiempo permaneció abierta la cuestión de la existencia de hexágonos vacíos , pero Nicolás (2007) y Gerken (2008) demostraron que todo conjunto de puntos suficientemente grande en posición general contiene un hexágono vacío convexo. Más específicamente, Gerken mostró que el número de puntos necesarios no es más de f (9) para la misma función f definida anteriormente, mientras que Nicolás mostró que el número de puntos necesarios no es más de f (25). Valtr (2008) proporciona una simplificación de la prueba de Gerken que, sin embargo, requiere más puntos, f (15) en lugar de f (9). Se necesitan al menos 30 puntos; existe un conjunto de 29 puntos en posición general sin hexágono convexo vacío. [10]
Problemas relacionados
El problema de encontrar conjuntos de n puntos minimizando el número de cuadriláteros convexos es equivalente a minimizar el número de cruces en un dibujo de línea recta de un gráfico completo . El número de cuadriláteros debe ser proporcional a la cuarta potencia de n , pero se desconoce la constante precisa. [11]
Es sencillo demostrar que, en espacios euclidianos de dimensiones superiores , conjuntos de puntos suficientemente grandes tendrán un subconjunto de k puntos que forman los vértices de un politopo convexo , para cualquier k mayor que la dimensión: esto se sigue inmediatamente de la existencia de convexos k -gones en conjuntos de puntos planos suficientemente grandes, proyectando el conjunto de puntos de dimensiones superiores en un subespacio bidimensional arbitrario. Sin embargo, el número de puntos necesarios para encontrar k puntos en posición convexa puede ser menor en dimensiones más altas que en el plano, y es posible encontrar subconjuntos que están más restringidos. En particular, en d dimensiones, cada d + 3 puntos en posición general tiene un subconjunto de d + 2 puntos que forman los vértices de un politopo cíclico . [12] De manera más general, para cada d y k > d existe un número m ( d , k ) tal que todo conjunto de m ( d , k ) puntos en posición general tiene un subconjunto de k puntos que forman los vértices de un Politopo vecino . [13]
Notas
- ↑ Un mundo de enseñanza y números, multiplicado por dos , Michael Cowling , The Sydney Morning Herald , 7 de noviembre de 2005, citado 4 de septiembre de 2014
- ^ En este contexto, posición general significa que no hay dos puntos que coincidan ni que tres puntos sean colineales.
- ↑ Este fue el problema original, probado por Esther Klein.
- ↑ Según Erdős & Szekeres (1935) , esto fue probado por primera vez por E. Makai; la primera prueba publicada apareció en Kalbfleisch, Kalbfleisch & Stanton (1970) .
- ^ Esto ha sido probado por Szekeres & Peters (2006) . Llevaron a cabo una búsqueda por computadora que eliminó todas las configuraciones posibles de 17 puntos sin hexágonos convexos mientras examinaban solo una pequeña fracción de todas las configuraciones.
- ^ Erdős y Szekeres (1961)
- ^ Suk (2016) . Consulte el coeficiente binomial y la notación O grande para la notación utilizada aquí y los números catalanes o la aproximación de Stirling para la expansión asintótica.
- ^ Harborth (1978) .
- ^ Horton (1983)
- ^ Overmars (2003) .
- ^ Scheinerman y Wilf (1994)
- ^ Grünbaum (2003) , ej. 6.5.6, pág. 120. Grünbaum atribuye este resultado a una comunicación privada de Micha A. Perles.
- ^ Grünbaum (2003) , ej. 7.3.6, pág. 126. Este resultado se sigue aplicando un argumento teórico de Ramsey similar a la demostración original de Szekeres junto con el resultado de Perles en el caso k = d + 2.
Referencias
- Chung, FRK ; Graham, RL (1998), "N-gones convexos forzados en el plano", Geometría discreta y computacional , 19 (3): 367–371, doi : 10.1007 / PL00009353.
- Erdős, P .; Szekeres, G. (1935), "Un problema combinatorio en geometría" , Compositio Mathematica , 2 : 463–470.
- Erdős, P .; Szekeres, G. (1961), "Sobre algunos problemas extremos en geometría elemental", Ann. Univ. Sci. Budapest. Secta Eötvös. Matemáticas. , 3–4 : 53–62. Reimpreso en: Erdős, P. (1973), Spencer, J. (ed.), The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, págs. 680–689.
- Gerken, Tobias (2008), "Hexágonos convexos vacíos en conjuntos de puntos planos", Geometría discreta y computacional , 39 (1-3): 239-272, doi : 10.1007 / s00454-007-9018-x.
- Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor ; Ziegler, Günter M. (eds.), Politopos convexos , Textos de posgrado en matemáticas, 221 (2a ed.), Springer-Verlag , ISBN 0-387-00424-6.
- Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elemente der Mathematik , 33 (5): 116-118.
- Horton, JD (1983), "Conjuntos sin 7 gones convexos vacíos", Canadian Mathematical Bulletin , 26 (4): 482–484, doi : 10.4153 / CMB-1983-077-8.
- Kalbfleisch, JD; Kalbfleisch, JG ; Stanton, RG (1970), "Un problema combinatorio en regiones convexas", Proc. Conf. De Luisiana Combinatoria, teoría de grafos y computación , Congressus Numerantium, 1 , Baton Rouge, La .: Louisiana State Univ., Págs. 180–188.
- Kleitman, DJ ; Pachter, L. (1998), "Encontrar conjuntos convexos entre puntos en el plano" (PDF) , Geometría discreta y computacional , 19 (3): 405–410, doi : 10.1007 / PL00009358.
- Morris, W .; Soltan, V. (2000), "El problema de Erdős-Szekeres sobre puntos en posición convexa: una encuesta", Boletín de la Sociedad Americana de Matemáticas , 37 (04): 437–458, doi : 10.1090 / S0273-0979-00- 00877-6.
- Nicolás, Carlos M. (2007), "El teorema del hexágono vacío", Geometría discreta y computacional , 38 (2): 389–397, doi : 10.1007 / s00454-007-1343-6.
- Overmars, M. (2003), "Encontrar conjuntos de puntos sin 6 gones convexos vacíos", Geometría discreta y computacional , 29 (1): 153-158, doi : 10.1007 / s00454-002-2829-x.
- Peterson, Ivars (2000), "Planes of Budapest" , MAA Online , archivado desde el original el 2 de julio de 2013.
- Scheinerman, Edward R .; Wilf, Herbert S. (1994), "El número de cruce rectilíneo de una gráfica completa y el" problema de cuatro puntos "de probabilidad geométrica de Sylvester", American Mathematical Monthly , Asociación Matemática de América, 101 (10): 939-943, doi : 10.2307 / 2975158 , JSTOR 2975158.
- Suk, Andrew (2016), "Sobre el problema del polígono convexo de Erdős-Szekeres", J. Amer. Matemáticas. Soc. , arXiv : 1604.08657 , doi : 10.1090 / jams / 869.
- Szekeres, G .; Peters, L. (2006), "Computer solution to the 17-point Erdős-Szekeres problem" , ANZIAM Journal , 48 (02): 151–164, doi : 10.1017 / S144618110000300X.
- Tóth, G .; Valtr, P. (1998), "Nota sobre el teorema de Erdős-Szekeres", Geometría discreta y computacional , 19 (3): 457–459, doi : 10.1007 / PL00009363.
- Tóth, G .; Valtr, P. (2005), "El teorema de Erdős-Szekeres: límites superiores y resultados relacionados", en Goodman, Jacob E .; Pach, János ; Welzl, Emo (eds.), Geometría combinatoria y computacional (PDF) , Publicaciones del Instituto de Investigación de Ciencias Matemáticas, 52 , Cambridge University Press, págs. 557–568.
- Valtr, P. (2008), "Sobre hexágonos vacíos", en Goodman, Jacob E .; Pach, János ; Pollack, Richard (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, 18-22 de junio de 2006, Snowbird, Utah , Contemporary Mathematics, 453 , American Mathematical Society, págs. . 433–442, ISBN 9780821842393.
enlaces externos
- Problema de final feliz y prueba teórica de Ramsey del teorema de Erdős-Szekeres en PlanetMath
- Weisstein, Eric W. "Problema del final feliz" . MathWorld .