Problema del final feliz

El " problema de final feliz " (llamado así por el matemático Paul Erdős porque condujo al matrimonio de George Szekeres y Esther Klein​) tiene el planteamiento siguiente:

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

Teorema : cualquier conjunto de cinco puntos en el plano en posición general​ tiene un subconjunto de cuatro puntos que forman los vértices de un cuadrilátero convexo.

Este fue uno de los resultados originales que condujeron al desarrollo de la teoría de Ramsey.

El teorema del final feliz puede probarse mediante un simple análisis de casos: si cuatro o más puntos son vértices de la envolvente convexa, se pueden elegir cuatro puntos. Si, por otro lado, el conjunto de puntos 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éanse Peterson (2000) para una explicación ilustrada de esta prueba, y Morris y Soltan (2000) para un análisis más detallado del problema.

La conjetura de Erdős-Szekeres establece precisamente una relación más general entre el número de puntos de un conjunto de puntos en posición general y su polígono convexo más grande, es decir, el número más pequeño de puntos para los cuales cualquier disposición de posición general contiene un subconjunto convexo de $n$ puntos es $2^{n-2}+1$. Sigue sin probarse, pero se conocen límites menos precisos.

Polígonos más grandes

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

Erdős y Szekeres (1935) probaron la siguiente generalización:

Teorema : para cualquier número 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 monotónicas en secuencias de números.

Supóngase que f ( N ) denota 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, caso trivial.
• f (4) = 5.​
• f (5) = 9.​ 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 prueba es demostrar que cada conjunto de nueve puntos en posición general contiene los vértices de un pentágono convexo.
• f (6) = 17.​
• El valor de f ( N ) es desconocido para todos N > 6; pero por el resultado de Erdős y 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 documento original que

$f(N)=1+2^{N-2}\quad {\mbox{para todo }}N\geq 3.$

Más tarde demostraron, al construir ejemplos explícitos, que

$f(N)\geq 1+2^{N-2},$ ​

pero el límite superior mejor conocido cuando N ≥ 7 es

$f(N)\leq 2^{N+o(N)}.$ ​

Polígonos convexos vacíos

También está la cuestión de si un conjunto de puntos suficientemente grande en posición general tiene un cuadrilátero convexo "vacío", pentágono, etc., es decir, uno que no contenga ningún otro punto interior. La solución original al problema del final feliz se puede adaptar para demostrar que cinco puntos en posición general contienen un cuadrilátero convexo vacío, como se muestra en la ilustración, y diez puntos en posición general poseen un pentágono convexo vacío.​ Sin embargo, existen conjuntos de puntos arbitrariamente grandes en posición general que no contienen un heptágono convexo vacío.​

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 punt suficientemente grande establecido en posición general contiene un hexágono convexo vacío. 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 mostró 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 hexágono convexo 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 cruce en un dibujo con líneas rectas 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.​

Es sencillo mostrar que, en espacios euclídeos de dimensiones superiores, los 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 deduce inmediatamente de la existencia de k-gonos convexos 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 altamente restringidos. En particular, en d dimensiones, cada d + 3 puntos en posición general tienen un subconjunto de d + 2 puntos que forman los vértices de un politopo cíclico.​ Más generalmente, por cada d y k > d existe un número m (d, k) tal que cada conjunto de puntos m (d, k) en posición general tiene un subconjunto de k puntos que forman los vértices de un politopo vecinal.​

Bibliografía

• Chung, F.R.K.; Graham, R.L. (1998), «Forced convex n-gons in the plane», Discrete and Computational Geometry 19 (3): 367-371, doi:10.1007/PL00009353 ..
• Erdős, P.; Szekeres, G. (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463-470 ..
• Erdős, P.; Szekeres, G. (1961), «On some extremum problems in elementary geometry», Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3–4: 53-62 .. Reprinted in: Erdős, P. (1973), Spencer, J., ed., The Art of Counting: Selected Writings, Cambridge, MA: MIT Press, pp. 680-689 ..
• Gerken, Tobias (2008), «Empty convex hexagons in planar point sets», Discrete and Computational Geometry 39 (1–3): 239-272, doi:10.1007/s00454-007-9018-x ..
• Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, eds., Convex Polytopes, Graduate Texts in Mathematics 221 (2nd edición), Springer-Verlag, ISBN 0-387-00424-6 ..
• Harborth, Heiko (1978), «Konvexe Fünfecke in ebenen Punktmengen», Elemente der Mathematik 33 (5): 116-118 ..
• Horton, J. D. (1983), «Sets with no empty convex 7-gons», Canadian Mathematical Bulletin 26 (4): 482-484, doi:10.4153/CMB-1983-077-8 ..
• Kalbfleisch, J.D.; Kalbfleisch, J.G.; Stanton, R.G. (1970), «A combinatorial problem on convex regions», Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Congressus Numerantium 1, Baton Rouge, La.: Louisiana State Univ., pp. 180-188 ..
• Kleitman, D.J.; Pachter, L. (1998), «Finding convex sets among points in the plane», Discrete and Computational Geometry 19 (3): 405-410, doi:10.1007/PL00009358, archivado desde el original el 4 de febrero de 2022, consultado el 15 de febrero de 2020 ..
• Morris, W.; Soltan, V. (2000), «The Erdős-Szekeres problem on points in convex position—A survey», Bulletin of the American Mathematical Society 37 (04): 437-458, doi:10.1090/S0273-0979-00-00877-6 ..
• Nicolás, Carlos M. (2007), «The empty hexagon theorem», Discrete and Computational Geometry 38 (2): 389-397, doi:10.1007/s00454-007-1343-6 ..
• Overmars, M. (2003), «Finding sets of points without empty convex 6-gons», Discrete and Computational Geometry 29 (1): 153-158, doi:10.1007/s00454-002-2829-x ..
• Peterson, Ivars (2000), «Planes of Budapest», MAA Online, archivado desde el original el 30 de diciembre de 2012, consultado el 15 de febrero de 2020 ..
• Scheinerman, Edward R.; Wilf, Herbert S. (1994), «The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability», American Mathematical Monthly (Mathematical Association of America) 101 (10): 939-943, doi:10.2307/2975158 ..
• Suk, Andrew (2016), «On the Erdős–Szekeres convex polygon problem», J. Amer. Math. Soc., 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, archivado desde el original el 13 de diciembre de 2019, consultado el 15 de febrero de 2020 ..
• Tóth, G.; Valtr, P. (1998), «Note on the Erdős-Szekeres theorem», Discrete and Computational Geometry 19 (3): 457-459, doi:10.1007/PL00009363 ..
• Tóth, G.; Valtr, P. (2005), «The Erdős-Szekeres theorem: upper bounds and related results», en Goodman, Jacob E.; Pach, János; Welzl, eds., Combinatorial and Computational Geometry, Mathematical Sciences Research Institute Publications 52, Cambridge University Press, pp. 557-568, archivado desde el original el 28 de julio de 2019, consultado el 15 de febrero de 2020 ..
• Valtr, P. (2008), «On empty hexagons», en Goodman, Jacob E.; Pach, János; Pollack, eds., Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, June 18-22, 2006, Snowbird, Utah, Contemporary Mathematics 453, American Mathematical Society, pp. 433-442, ISBN 9780821842393 ..

Enlaces externos

• Happy ending problem and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath
• Weisstein, Eric W. «Happy End Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q1033772