The happy end problem, also called the "happy ending problem," is the problem of determining for 
the smallest number of points 
in general position
in the plane (i.e., no three of which are collinear),
such that every possible arrangement of 
points will always contain at least one set of 
points that are the vertices of a convex
polygon of 
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, 
.
Random arrangements of 
points are illustrated above. Note that no convex quadrilaterals are possible for
the arrangements shown in the fifth and eighth figures above, so 
must be greater than 4. E. Klein proved that 
by showing that any arrangement
of five points must fall into one of the three cases (left top figure; Hoffman 1998,
pp. 75-76).
Random arrangements of 
points are illustrated above. Note that no convex pentagons
are possible for the arrangement shown in the fifth figure above, so 
must be greater than 8. E. Makai proved 
after demonstrating that a counterexample could be found
for eight points (right top figure; Hoffman 1998, pp. 75-76).
As the number of points 
increases, the number of 
-subsets of 
that must be examined to see if they form convex 
-gons increases as 
, so combinatorial explosion prevents cases much bigger
than 
from being easily studied. Furthermore, the parameter space become so large that
searching for a counterexample at random even for the case 
with 
points takes an extremely long time. For these reasons,
the general problem remains open.
was demonstrated by Szekeres and
Peters (2006) using a computer search which eliminated all possible configurations
of 17 points which lacked convex hexagons while examining only a tiny fraction of
all configurations.
Erdős and Szekeres (1935) showed that 
always exists and derived the bound
 |
(1)
|
where 
is a binomial coefficient. For 
, this has since been reduced to 
for
 |
(2)
|
by Chung and Graham (1998), 
for
 |
(3)
|
by Kleitman and Pachter (1998), and 
for
 |
(4)
|
by Tóth and Valtr (1998). For 
, these bounds give 71, 70, 65, and 37, respectively (Hoffman
1998, p. 78).
The values of 
for 
,
7, ... are 37, 128, 464, 1718, ... (OEIS A052473).
-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.Hoffman, P.