Happy Ending Problem - Larger Polygons

Larger Polygons

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

• f(3) = 3, trivially.
• f(4) = 5.
• f(5) = 9. 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.
• The value of f(N) is unknown for all N > 6; by the result of Erdős & Szekeres (1935) it is known to be finite.

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

They proved later, by constructing explicit examples, that

but the best known upper bound when N ≥ 7 is