Problema del final feliz

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:

Este 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 sencillo análisis de casos: si cuatro o más puntos son vértices de la envoltura convexa , se pueden elegir cualesquiera cuatro de dichos puntos. Si, por otro lado, la envoltura convexa tiene la forma de un triángulo con dos vértices en su interior, se pueden elegir los dos vértices interiores y uno de los lados del triángulo. Véase Peterson (2000) para una explicación ilustrada de esta demostración, 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 en un conjunto de puntos de posición general y su subconjunto más grande que forma un polígono convexo , 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${\displaystyle n}$puntos es${\displaystyle 2^{n-2}+1}$Aún no se ha demostrado, pero se conocen límites menos precisos.

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

La demostración apareció en el mismo artículo que demuestra 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 demostración es mostrar que todo 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 . Según 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

$${\displaystyle f(N)=1+2^{N-2}\quad {\text{para todo }}N\geq 3.}$$ Posteriormente demostraron, mediante la construcción de ejemplos explícitos, que ^{[ 6 ]}$${\displaystyle f(N)\geq 1+2^{N-2}.}$$ En 2016 Andrew Suk ^{[ 7 ]} demostró que para N ≥ 7$${\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}\log N}.}$$

Posteriormente se mejoró a: ^{[ 8 ]}

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

También surge la cuestión de si cualquier conjunto suficientemente grande de puntos en posición general contiene 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 puede adaptarse para demostrar que cualesquiera cinco puntos en posición general contienen un cuadrilátero convexo vacío, como se muestra en la ilustración, y cualesquiera diez puntos en posición general contienen 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 ]}

Dejar${\displaystyle N}$sea ​​el número mínimo de puntos, de tal manera que cualquier${\displaystyle N}$Los puntos en posición general contienen un hexágono vacío. Durante mucho tiempo ha estado abierto si${\displaystyle N}$Existe. La pregunta ya está resuelta:

• Overmars (2003) demostró que si existe, entonces${\displaystyle N\geq 30}$, mediante la construcción de un ejemplo con 29 puntos.
• Nicolás (2007) demostró que${\displaystyle N\leq f(25)}$.
• Gerken (2008) demostró que${\displaystyle N\leq f(9)}$.
• Valtr (2008) hizo una versión más simple pero menos rigurosa de Gerken (2008) , para demostrar que${\displaystyle N\leq f(15)}$.
• Heule y Scheucher (2024) demostraron, mediante el uso de un enfoque de resolución SAT , que${\displaystyle N=30}$.

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 intersecciones en un trazado de línea recta de un grafo completo . El número de cuadriláteros debe ser proporcional a la cuarta potencia de n , pero se desconoce la constante exacta. ^{[ 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 deduce inmediatamente de la existencia de k -gonos convexos en conjuntos de puntos planares 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 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 . ^{[ 12 ]} 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 . ^{[ 13 ]} 

• Problema del 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