Problema del final feliz

Cinco puntos coplanares tienen un subconjunto que forma un cuadrilátero convexo

El problema del final feliz: cada conjunto de cinco puntos en posición general contiene los vértices de un cuadrilátero convexo

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 el siguiente enunciado:

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 .

Éste fue uno de los resultados originales que condujeron 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 de la envoltura convexa , se pueden elegir cuatro de esos puntos. Si, por otro lado, la envoltura convexa tiene la forma de un triángulo con dos puntos en su interior, se pueden elegir los dos puntos internos y uno de los lados del triángulo. Véase Peterson (2000) para una explicación ilustrada de esta prueba, y Morris & Soltan (2000) para un estudio más detallado del problema.

La conjetura de Erdős–Szekeres enuncia con precisión una relación más general entre el número de puntos de un conjunto de puntos de posición general y su subconjunto más grande que forma un polígono convexo , es decir, 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 demostrado, pero se conocen límites menos precisos. ${\displaystyle n}$ ${\displaystyle 2^{n-2}+1}$

Polígonos más grandes

Un conjunto de ocho puntos en posición general sin pentágono convexo

Erdős y 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 -gono convexo. Se sabe que

• f (3) = 3 , trivialmente.
• f (4) = 5 . ^[3]
• f (5) = 9 . ^[4] En la ilustración se muestraun conjunto de ocho puntos sin pentágono convexo, lo que demuestra que f (5) > 8 ; la parte más difícil de la prueba 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 y Szekeres (1935), se sabe que f ( N ) es finito para todo N 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

Un conjunto de dieciséis puntos en posición general sin hexágono convexo

$${\displaystyle f(N)=1+2^{N-2}\quad {\text{for all }}N\geq 3.}$$Demostraron más tarde, mediante la construcción de ejemplos explícitos, que ^[6] En 2016, Andrew Suk ^[7] demostró que para N ≥ 7 $${\displaystyle f(N)\geq 1+2^{N-2}.}$$ $${\displaystyle f(N)\leq 2^{N+o(N)}.}$$

Suk demuestra en realidad, para N suficientemente grande, $${\displaystyle f(N)\leq 2^{N+6N^{2/3}logN}.}$$

Esto se mejoró posteriormente a: ^[8]

$${\displaystyle f(N)\leq 2^{N+O({\sqrt {NlogN}})}.}$$

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, pentágono, etc. convexo "vacío", es decir, uno que no contenga 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 cualesquiera diez puntos en posición general tienen un pentágono convexo vacío. ^[9] Sin embargo, existen conjuntos arbitrariamente grandes de puntos en posición general que no contienen ningún heptágono convexo vacío . ^[10]

Durante mucho tiempo la cuestión de la existencia de hexágonos vacíos permaneció abierta, pero Nicolás (2007) y Gerken (2008) demostraron que cada conjunto de puntos suficientemente grande en posición general contiene un hexágono vacío convexo. Más específicamente, Gerken demostró que el número de puntos necesarios no es mayor que f (9) para la misma función f definida anteriormente, mientras que Nicolás demostró que el número de puntos necesarios no es mayor que 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 ningún hexágono convexo vacío. ^[11] La pregunta fue finalmente respondida por Heule y Scheucher (2024), quienes demostraron, utilizando un enfoque de resolución SAT, que efectivamente cada conjunto de 30 puntos en posición general contiene un hexágono vacío.

Problemas relacionados

El problema de encontrar conjuntos de n puntos que minimicen 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 no se conoce la constante precisa. ^[12]

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 k -gonos convexos en conjuntos de puntos planos suficientemente grandes, al proyectar 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 superiores que en el plano, y es posible encontrar subconjuntos que estén más restringidos. En particular, en dimensiones d , 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 . ^[13] De manera más general, para cada d y k  >  d existe un número m ( d , k ) tal que cada 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 . ^[14]

Notas

1. Un mundo de enseñanza y números, multiplicado por dos, Michael Cowling , The Sydney Morning Herald , 7 de noviembre de 2005, citado el 4 de septiembre de 2014
2. En este contexto, posición general significa que no hay dos puntos que coincidan ni tres puntos que sean colineales.
3. Éste fue el problema original, demostrado por Esther Klein.
4. Según Erdős y Szekeres (1935), esto fue demostrado por primera vez por E. Makai; la primera prueba publicada apareció en Kalbfleisch, Kalbfleisch y Stanton (1970).
5. Esto fue demostrado por Szekeres y Peters (2006). Realizaron 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.
6. Erdøs y Szekeres (1961)
7. Suk (2016). Véase el coeficiente binomial y la notación O grande para la notación utilizada aquí y los números de Catalan o la aproximación de Stirling para la expansión asintótica.
8. Holmsen y otros (2020).
9. Harborth (1978).
10. Horton (1983)
11. Overmars (2003).
12. Scheinerman y Wilf (1994)
13. Grünbaum (2003), Ex. 6.5.6, p.120. Grünbaum atribuye este resultado a una comunicación privada de Micha A. Perles.
14. Grünbaum (2003), Ex. 7.3.6, p. 126. Este resultado se obtiene aplicando un argumento teórico de Ramsey similar a la prueba original de Szekeres junto con el resultado de Perles en el caso k  =  d  + 2.

Referencias

• Chung, FRK ; Graham, RL (1998), "N-gonos 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. Ciencia. Budapest. Secta Eötvös. Matemáticas. , 3–4 : 53–62; reimpreso en Erdős, P. (1973), Spencer, J. (ed.), El arte de contar: escritos seleccionados , 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, Víctor ; Ziegler, Günter M. (eds.), Politopos convexos , Textos de posgrado en matemáticas, vol. 221 (2.ª ed.), Springer-Verlag , ISBN 0-387-00424-6
• Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elemente der Mathematik , 33 (5): 116-118
• Heule, Marijn JH; Scheucher, Manfred (2024), "Final feliz: un hexágono vacío en cada conjunto de 30 puntos", en Finkbeiner, Bernd; Kovács, Laura (eds.), Herramientas y algoritmos para la construcción y análisis de sistemas , Lecture Notes in Computer Science, vol. 14570, Springer-Verlag, págs. 61–80, arXiv : 2403.00737 , doi : 10.1007/978-3-031-57246-3_5
• Holmsen, Andreas F.; Mojarrad, Hossein Nassajian; Pach, János ; Tardos, Gábor (2020), "Dos extensiones del problema de Erdős-Szekeres", Revista de la Sociedad Matemática Europea (JEMS) , 22 (12): 3981–3995, arXiv : 1710.11415 , doi :10.4171/jems/1000, SEÑOR  4176784
• Horton, JD (1983), "Conjuntos sin 7-gonos convexos vacíos", Canadian Mathematical Bulletin , 26 (4): 482–484, doi : 10.4153/CMB-1983-077-8 , S2CID  120267029
• Kalbfleisch, JD; Kalbfleisch, JG ; Stanton, RG (1970), "Un problema combinatorio en regiones convexas", Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing , Congressus Numerantium, vol. 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 , archivado desde el original (PDF) el 2022-02-04 , consultado el 2019-09-23
• Morris, W.; Soltan, V. (2000), "El problema de Erdős-Szekeres en puntos en posición convexa: un estudio", Boletín de la Sociedad Matemática Americana , 37 (4): 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-gonos 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 cruces rectilíneos de un gráfico completo y el "problema de los cuatro puntos" de Sylvester de probabilidad geométrica", American Mathematical Monthly , 101 (10), Mathematical Association of America: 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. , 30 (4): 1047–1053, arXiv : 1604.08657 , doi : 10.1090/jams/869, S2CID  15732134
• Szekeres, G .; Peters, L. (2006), "Solución informática al problema de Erdős-Szekeres de 17 puntos", ANZIAM Journal , 48 (2): 151–164, doi : 10.1017/S144618110000300X , archivado desde el original el 13 de diciembre de 2019 , consultado el 5 de enero de 2007
• 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.), Combinatorial and Computational Geometry (PDF) , Mathematical Sciences Research Institute Publications, vol. 52, Cambridge University Press, pp. 557–568, archivado desde el original (PDF) el 28 de julio de 2019 , consultado el 28 de febrero de 2015
• Valtr, P. (2008), "Sobre hexágonos vacíos", en Goodman, Jacob E. ; Pach, János ; Pollack, Richard (eds.), Encuestas sobre geometría discreta y computacional: veinte años después: Conferencia de investigación de verano conjunta AMS-IMS-SIAM, 18-22 de junio de 2006, Snowbird, Utah, Contemporary Mathematics, vol. 453, American Mathematical Society, págs. 433–442, ISBN 9780821842393

Enlaces externos

• Problema de final feliz y demostración teórica de Ramsey del teorema de Erdős-Szekeres en PlanetMath
• Weisstein, Eric W. , "Problema del final feliz", MathWorld