The Happy Ending problem (forcing convex polygons)

Problem's Description

The happy ending problem, is concerned with determining, for $ n \geq 3 $, the smallest number of points in the plane, each in general position (i.e., not collinear), such that any arrangement of these points will always include at least one set of $ n $ points forming the vertices of a convex polygon with $ n $ sides.

The problem earned its name when Ester Klein and George Szekeres, the initial researchers on this problem, became engaged and later married, as noted by Erdős (see [1]). This discovery was one of the foundational results that spurred the advancement of Ramsey theory.

The proof of the happy ending theorem can be illustrated through a straightforward case analysis: if there are four or more points forming vertices of the convex hull, any set of four such points can be selected. Conversely, if the convex hull is in the shape of a triangle with two points enclosed within it, the two inner points and one side of the triangle can be chosen. Refer to Morris & Soltan [2] who provide a comprehensive survey of the problem.

The Erdős–Szekeres conjecture precisely describes a broader connection between the number of points in a point set in general position and the largest subset forming a convex polygon. Specifically, it conjectures that the minimum number of points required for any arrangement in general position to contain a convex subset of n points is given by $2^{n-2}+1$. Although still unproven, there exist less precise bounds on this conjecture.

1. BookIs an originThe man who loved only numbers

   • Paul Hoffman

   pp. viii+302, year of publication: 1998

2. Article The Erdős-Szekeres problem on points in convex position--a survey

   • W. Morris,
   • V. Soltan

   American Mathematical Society. Bulletin. New Series 37, 437-458, 2000fulltext