Happy ending problem

In mathematics, the "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein[1]) is the following statement: Theorem — any set of five points in the plane in general position[2] has a subset of four points that form the vertices of a convex quadrilateral.

See Peterson (2000) for an illustrated explanation of this proof, and Morris & Soltan (2000) for a more detailed survey of the problem.

The Erdős–Szekeres conjecture states precisely a more general relationship between the number of points in a general-position point set and its largest subset forming a convex polygon, namely that the smallest number of points for which any general position arrangement contains a convex subset of

Erdős & Szekeres (1935) proved the following generalisation: Theorem — for any positive integer N, any sufficiently large finite set of points in the plane in general position has a subset of N points that form the vertices of a convex polygon.

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 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

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] For a long time the question of the existence of empty hexagons remained open, but Nicolás (2007) and Gerken (2008) proved that every sufficiently large point set in general position contains a convex empty hexagon.

Valtr (2008) supplies a simplification of Gerken's proof that however requires more points, f(15) instead of f(9).

[11] The question was finally answered by Heule & Scheucher (2024), who showed, using a SAT solving approach, that indeed every set of 30 points in general position contains an empty hexagon.

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.

[12] 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.