Happy ending problem

submited by

Style Pass

2024-10-25 20:00:07

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.

The happy ending theorem can be proven by a simple case analysis: if four or more points are vertices of the convex hull, any four such points can be chosen. If on the other hand, the convex hull has the form of a triangle with two points inside it, the two inner points and one of the triangle sides can be chosen. 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 n {\displaystyle n} points is 2 n − 2 + 1 {\displaystyle 2^{n-2}+1} . It remains unproven, but less precise bounds are known.