TOPICS
Search

Happy End Problem


HappyEndProblem

The happy end problem, also called the "happy ending problem," is the problem of determining for n>=3 the smallest number of points g(n) in general position in the plane (i.e., no three of which are collinear), such that every possible arrangement of g(n) points will always contain at least one set of n points that are the vertices of a convex polygon of n sides. The problem was so-named by Erdős when two investigators who first worked on the problem, Ester Klein and George Szekeres, became engaged and subsequently married (Hoffman 1998, p. 76).

Since three noncollinear points always determine a triangle, g(3)=3.

HappyEndProblem4

Random arrangements of n=4 points are illustrated above. Note that no convex quadrilaterals are possible for the arrangements shown in the fifth and eighth figures above, so g(4) must be greater than 4. E. Klein proved that g(4)=5 by showing that any arrangement of five points must fall into one of the three cases (left top figure; Hoffman 1998, pp. 75-76).

HappyEndProblem8

Random arrangements of n=8 points are illustrated above. Note that no convex pentagons are possible for the arrangement shown in the fifth figure above, so g(5) must be greater than 8. E. Makai proved g(5)=9 after demonstrating that a counterexample could be found for eight points (right top figure; Hoffman 1998, pp. 75-76).

As the number of points n increases, the number of k-subsets of n that must be examined to see if they form convex k-gons increases as (n; k), so combinatorial explosion prevents cases much bigger than n=5 from being easily studied. Furthermore, the parameter space become so large that searching for a counterexample at random even for the case n=6 with k=12 points takes an extremely long time. For these reasons, the general problem remains open.

g(6)=17 was demonstrated by Szekeres and Peters (2006) using a 1500 CPU-hour computer search which eliminated all possible configurations of 17 points which lacked convex hexagons while examining only a tiny fraction of all configurations. Marić (2019) and Scheucher (2020) independently verified g(6)=17 using satisfiability (SAT) solving in a few CPU hours, a time later reduced to 10 CPU-minutes by Scheucher (2023) and to 8.53 CPU-seconds by Heule and Scheucher (2024).

The first few values of g(n) for n=3, 4, 5, and 6 are therefore 3, 5, 9, 17, which happen to be exactly 2^(n-2)+1. However, the values of g(n) for n>=7 are unknown.

Erdős and Szekeres (1935) showed that g(n) always exists and derived the bound

 2^(n-2)+1<=g(n)<=(2n-4; n-2)+1,
(1)

where (n; k) is a binomial coefficient. For n>=4, this has since been reduced to g(n)<=g_1(n) for

 g_1(n)=(2n-4; n-2)
(2)

by Chung and Graham (1998), g(n)<=g_2(n) for

 g_2(n)=(2n-4; n-2)+7-2n
(3)

by Kleitman and Pachter (1998), and g(n)<=g_3(n) for

 g_3(n)=(2n-5; n-2)+2
(4)

by Tóth and Valtr (1998).


See also

Convex Hull, Convex Polygon

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, p. 78, 2003.Chung, F. R. K. and Graham, R. L. "Forced Convex n-gons in the Plane." Discr. Comput. Geom. 19, 367-371, 1998.Erdős, P. and Szekeres, G. "A Combinatorial Problem in Geometry." Compositio Math. 2, 463-470, 1935.Heule, M. J. H. and Scheucher, M. "Happy Ending: An Empty Hexagon in Every Set of 30 Points." 1 Mar 2024. https://arxiv.org/abs/2403.00737.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 75-78, 1998.Kleitman, D. and Pachter, L. "Finding Convex Sets among Points in the Plane." Discr. Comput. Geom. 19, 405-410, 1998.Lovász, L.; Pelikán, J.; and Vesztergombi, K. Discrete Mathematics, Elementary and Beyond. New York: Springer-Verlag, 2003.Marić, F. "Fast Formal Proof of the Erdős-Szekeres Conjecture for Convex Polygons With at Most 6 Points." J. Automated Reasoning 62, 301-329, 2019.Scheucher, M. "Two Disjoint 5-Holes in Point Sets." Comput. Geom. 91, 101670, 2020.Scheucher, M. "A SAT Attack on Erd-Szekeres Numbers in Rd and the Empty Hexagon Theorem." Computing in Geometry and Topology 2, 2:1-2:13, 2023.Szekeres, G. and Peters, L. "Computer Solution to the 17-Point Erdős-Szekeres Problem." ANZIAM J. 48, 151-164, 2006.Tóth, G. and Valtr, P. "Note on the Erdős-Szekeres Theorem." Discr. Comput. Geom. 19, 457-459, 1998.Soifer, A. "The Happy End Problem." Ch. 31 in The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, pp. 321-337, 2024.

Referenced on Wolfram|Alpha

Happy End Problem

Cite this as:

Weisstein, Eric W. "Happy End Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HappyEndProblem.html

Subject classifications