Happy ending problem

Erdős & Szekeres (1935) proved the following generalisation:

The proof appeared in the same paper that proves the Erdős–Szekeres theorem on monotonic subsequences in sequences of numbers.

Let f(N) denote the minimum M for which any set of M points in general position must contain a convex N-gon. It is known that

• f(3) = 3, trivially.
• f(4) = 5.^[3]
• f(5) = 9.^[4] A set of eight points with no convex pentagon is shown in the illustration, demonstrating that f(5) > 8; the more difficult part of the proof is to show that every set of nine points in general position contains the vertices of a convex pentagon.
• f(6) = 17.^[5]
• The value of f(N) is unknown for all N > 6. By the result of Erdős & Szekeres (1935), f(N) is known to be finite for all finite N.

On the basis of the known values of f(N) for N = 3, 4 and 5, Erdős and Szekeres conjectured in their original paper that

$${\displaystyle f(N)=1+2^{N-2}\quad {\text{for all }}N\geq 3.}$$ They proved later, by constructing explicit examples, that^[6] $${\displaystyle f(N)\geq 1+2^{N-2}.}$$ In 2016 Andrew Suk^[7] showed that for N ≥ 7 $${\displaystyle f(N)\leq 2^{N+o(N)}.}$$

Suk actually proves, for N sufficiently large, $${\displaystyle f(N)\leq 2^{N+6N^{2/3}\log N}.}$$

This was subsequently improved to:^[8]

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

There is also the question of whether any sufficiently large set of points in general position has an "empty" convex quadrilateral, pentagon, etc., that is, one that contains no other input point. The original solution to the happy ending problem can be adapted to show that any five points in general position have an empty convex quadrilateral, as shown in the illustration, and any ten points in general position have an empty convex pentagon.^[9] However, there exist arbitrarily large sets of points in general position that contain no empty convex heptagon.^[10]

Let ${\displaystyle N}$ be the minimum number of points, such that any ${\displaystyle N}$ points in general position contains an empty hexagon. For a long time it is open whether ${\displaystyle N}$ exists. The question is now solved:

• Overmars (2003) showed that if it exists, then ${\displaystyle N\geq 30}$, by constructing an example with 29 points.
• Nicolás (2007) showed that ${\displaystyle N\leq f(25)}$.
• Gerken (2008) showed that ${\displaystyle N\leq f(9)}$.
• Valtr (2008) made a simpler but looser version of Gerken (2008), to show that ${\displaystyle N\leq f(15)}$.
• Heule & Scheucher (2024) showed, by using a SAT solving approach, that ${\displaystyle N=30}$.

The problem of finding sets of n points minimizing the number of convex quadrilaterals is equivalent to minimizing the crossing number in a straight-line drawing of a complete graph. The number of quadrilaterals must be proportional to the fourth power of n, but the precise constant is not known.^[11]

It is straightforward to show that, in higher-dimensional Euclidean spaces, sufficiently large sets of points will have a subset of k points that forms the vertices of a convex polytope, for any k greater than the dimension: this follows immediately from existence of convex k-gons in sufficiently large planar point sets, by projecting the higher-dimensional point set into an arbitrary two-dimensional subspace. However, the number of points necessary to find k points in convex position may be smaller in higher dimensions than it is in the plane, and it is possible to find subsets that are more highly constrained. In particular, in d dimensions, every d + 3 points in general position have a subset of d + 2 points that form the vertices of a cyclic polytope.^[12] More generally, for every d and k > d there exists a number m(d, k) such that every set of m(d, k) points in general position has a subset of k points that form the vertices of a neighborly polytope.^[13]