Convex and discrete geometry Discrete and combinatorial geometry Problem

Happy ending problem

Problem

A finite set of points in the plane is in general position if no three of its points lie on a line. For an integer $n \ge 3$ , let $N(n)$ be the least integer $N$ with the following property. Every set of $N$ points in the plane in general position contains $n$ points that are the vertices of a convex polygon. The problem asks for the value of $N(n)$ . Erdős and Szekeres conjectured that $N(n) = 2^{n-2} + 1$ for every $n \ge 3$ .

Remarks

Erdős and Szekeres proved that $N(n)$ exists, using Ramsey's theorem in one of their proofs. They also proved the lower bound $N(n) \ge 2^{n-2} + 1$ by a construction. The known values are $N(3) = 3$ , $N(4) = 5$ , $N(5) = 9$ and $N(6) = 17$ , all equal to $2^{n-2} + 1$ . The value $N(6) = 17$ was established with a computer search by Szekeres and Peters. Suk proved in 2017 that $N(n) \le 2^{n + o(n)}$ . The conjecture $N(n) = 2^{n-2} + 1$ is open for $n \ge 7$ .

History

The case $n = 4$ was posed by Esther Klein. The name comes from the marriage of Klein and George Szekeres, who met through this problem.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Clique definition
Complete graph example
Convex set concept
Ramsey's theorem statement
Happy ending problem problem

Tag	`PX7SS1X16K`
URI	`m2://PX7SS1X16K`
Kind	problem
Writing	W0 stub
MSC	52C10, 05D10
Status	This copy of the site has no build data. Run `m2 status PX7SS1X16K`.
About	Convex set
Uses	Convex set, Ramsey's theorem
Same as	Wikidata Q1033772 Wikipedia Happy ending problem
Changed	2 November 2026

Happy ending problem

Problem

Remarks

History

Reading path

Further reading

What this page needs for W1

What links here