The Erdős–Szekeres happy ending problem

Among any five points in the plane with no three on a line, four form a convex quadrilateral. Erdős and Szekeres asked how many points in general position force a convex $n$-gon, and conjectured the answer $2^{n-2}+1$. Erdős named it the happy ending problem because it led to the marriage of George Szekeres and Esther Klein, who first raised it.

Problem

Let $f(n)$ be the smallest integer such that any $f(n)$ points in the plane, no three on a line, contain $n$ points that are the vertices of a convex $n$-gon. Prove that

$$f(n)=2^{n-2}+1\quad\text{for all } n\ge3.$$

Erdős offered $500 for a proof (and $100 for a disproof); Graham later offered $1000 for a proof.

Background

Esther Klein observed in 1931 that $f(4)=5$, and Turán and Makai showed $f(5)=9$. Erdős and Szekeres proved in 1935 that $f(n)$ exists, with $f(n)\le\binom{2n-4}{n-2}+1$, and in 1960 they constructed sets of $2^{n-2}$ points with no convex $n$-gon, giving $f(n)\ge 2^{n-2}+1$. Szekeres and Peters (2006) settled $f(6)=17$ by a computer search. For a long time all improvements of the upper bound were of the form $4^{(1+o(1))n}$.

What is known

• Small values. $f(4)=5$, $f(5)=9$, and $f(6)=17$ (Szekeres and Peters, 2006), all agreeing with the conjecture.
• Upper bound. Suk (2017) proved $f(n)\le 2^{n+o(n)}$, so the conjecture is correct in the exponent; Holmsen, Mojarrad, Pach and Tardos (2020) refined this to $f(n)\le 2^{n+O(\sqrt{n\log n})}$.
• Lower bound. The Erdős–Szekeres construction gives $f(n)\ge 2^{n-2}+1$, which is conjectured to be exact.

What would count as progress

• The value $f(7)$: either a proof that $33$ points in general position always contain a convex heptagon (presumably computer-assisted, with a checkable certificate such as a SAT proof), or $33$ points with no convex heptagon, which would disprove the conjecture and can be verified directly.
• An upper bound of the form $f(n)\le 2^{n+O(\log n)}$, or $f(n)\le C\cdot 2^{n}$.
• A proof of the conjecture in full.
• A formal proof against the Lean statement in formal-conjectures.

References

1. P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463–470. numdam.org
2. G. Szekeres and L. Peters, Computer solution to the 17-point Erdős–Szekeres problem, ANZIAM J. 48 (2006), 151–164. doi:10.1017/S144618110000300X
3. A. Suk, On the Erdős–Szekeres convex polygon problem, J. Amer. Math. Soc. 30 (2017), 1047–1053. doi:10.1090/jams/869
4. A. F. Holmsen, H. N. Mojarrad, J. Pach and G. Tardos, Two extensions of the Erdős–Szekeres problem, J. Eur. Math. Soc. 22 (2020), 3981–3995. doi:10.4171/JEMS/1000

Source

Imported from Erdős Problems 107, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.