The Erdős–Szekeres happy ending conjecture

Unsolved Research level Archive

archive posted 7 weeks ago

Let $f (N)$ be the smallest number such that any $f (N)$ points in the plane, no three on a line, include $N$ points that are the vertices of a convex polygon. Prove or disprove that $f (N) = 2^{N - 2} + 1$ for every $N \geq 3$ .

Posed by Paul Erdős and George Szekeres (after a question of Esther Klein), 1935

Like0

History and references

Still open as of 2026.

Esther Klein observed that any 5 points in general position include the vertices of a convex quadrilateral. In 1935 Erdős and Szekeres proved that $f (N)$ is finite for every $N$ , one of the founding results of Ramsey theory, and conjectured the exact formula from the values $f (3) = 3$ , $f (4) = 5$ and $f (5) = 9$ . Erdős called it the happy ending problem because Klein and Szekeres later married. They also constructed point sets showing $f (N) \geq 2^{N - 2} + 1$ . The only other known value is $f (6) = 17$ . In 2016 Andrew Suk proved $f (N) \leq 2^{N + o (N)}$ , which matches the conjecture up to lower order terms in the exponent.

References

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

References

Solutions 0

Discussion 0