Open problem, Combinatorics and discrete mathematics, Geometry, posed 1935

Happy ending problem (Erdős–Szekeres)

OpenErdős

For every integer $n \ge 3$ , does every set of $2^{n-2} + 1$ points in the Euclidean plane $\mathbb{R}^2$ in general position (no three collinear) contain $n$ points that form the vertices of a convex $n$ -gon—so that the minimum guaranteed number of points is $\mathrm{ES}(n) = 2^{n-2} + 1$ ?

Posed by, 1935Paul Erdős

Research frontier as of 2026

As of 2026, the exact formula $\mathrm{ES}(n) = 2^{n-2} + 1$ is proved only for $n = 3, 4, 5, 6$ , with $\mathrm{ES}(3) = 3$ , $\mathrm{ES}(4) = 5$ , $\mathrm{ES}(5) = 9$ , and $\mathrm{ES}(6) = 17$ ; even the case $n = 7$ (conjectured to be $\mathrm{ES}(7) = 33$ ) remains open. Asymptotically, following Andrew Suk's 2016 breakthrough $\mathrm{ES}(n) = 2^{n + o(n)}$ , Holmsen, Mojarrad, Pach, and Tardos (2020) improved the upper bound error term to $\mathrm{ES}(n) \le 2^{n + O(\sqrt{n \log n})}$ , leaving only a sub-exponential factor between the lower and upper bounds.

Best known results

Exact values: $\mathrm{ES}(3) = 3$ , $\mathrm{ES}(4) = 5$ (Klein, 1933), $\mathrm{ES}(5) = 9$ (Makai–Turán, 1935), and $\mathrm{ES}(6) = 17$ (Szekeres–Peters, 2006).
For all $n \ge 3$ , $2^{n-2} + 1 \le \mathrm{ES}(n) \le 2^{n + O(\sqrt{n \log n})}$ (Erdős–Szekeres 1960; Suk 2016/2017; Holmsen–Mojarrad–Pach–Tardos 2020).

Tools and where they stop

Tool	Achieved	Where it stops
Positive-fraction cups-and-caps decomposition (Pór–Valtr, Suk)	Uses the Pór–Valtr positive-fraction theorem to partition most of a point set into $k$ convexly independent subsets whose points lie in narrow cones, enabling simultaneous induction on cups and caps to lower the base from $4$ to $2$ .	Passing to a positive fraction at each recursive depth loses a factor of $O(k^4)$ per stage, accumulating the $2^{O(\sqrt{n \log n})}$ overhead above $2^{n-2} + 1$ .

Open questions

Does every set of $33$ points in the plane in general position contain the vertices of a convex heptagon ( $\mathrm{ES}(7) = 33$ )?
Is $\mathrm{ES}(n) = 2^{n-2} + 1$ for every integer $n \ge 3$ ?

References

Paul Erdős, George Szekeres (1935). A combinatorial problem in geometry
George Szekeres, Lindsay Peters (2006). Computer solution to the 17-point Erdős-Szekeres problem · DOI:10.1017/S144618110000300X
Andrew Suk (2017). On the Erdős-Szekeres convex polygon problem · DOI:10.1090/jams/869 · arXiv:1604.08657