# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/107.lean).

## References

1. P. Erdős and G. Szekeres, A combinatorial problem in geometry, *Compos. Math.* 2 (1935), 463–470. [numdam.org](http://www.numdam.org/item/CM_1935__2__463_0/)
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](https://doi.org/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](https://doi.org/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](https://doi.org/10.4171/JEMS/1000)

## Source

Imported from [Erdős Problems 107](https://www.erdosproblems.com/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.