The Erdős–Szekeres (happy ending) conjecture: is $ES(n)=2^{n-2}+1$?

The Erdős–Szekeres conjecture — the central open problem of the combinatorial geometry of planar point sets, dating to 1935 and colloquially known as the happy ending problem — predicts that every set of $2^{n-2}+1$ points in the plane in general position (no three collinear) contains $n$ points in convex position, i.e. that $ES(n)=2^{n-2}+1$ for every $n\ge 3$. The lower bound $ES(n)\ge 2^{n-2}+1$ has been known since the 1961 construction of Erdős and Szekeres, and Suk's 2016 theorem $ES(n)\le 2^{n+6n^{2/3}\log_2 n}$ brought the upper bound down to $2^{n+o(n)}$, leaving only a lower-order additive gap in the exponent. The conjecture is verified for $n\le 6$ (with $ES(6)=17$ proved by computer), and the first open case is $ES(7)$, conjectured to equal $33$. As of August 2026 the conjecture remains open: no improvement of the $2^{n+o(n)}$ order of Suk's bound (the error term in the exponent was improved to $O(\sqrt{n\log n})$ by Holmsen–Mojarrad–Pach–Tardos in 2020), no counterexample, and explicit 2025–2026 statements that the problem is unresolved. The problem posed is to prove or refute $ES(n)=2^{n-2}+1$; a refutation would be an explicit set of $2^{n-2}+1$ points in general position containing no $n$ points in convex position for some $n\ge 7$.

Background

A finite set of points in the plane is in general position if no three of its points lie on a common line, and a subset is in convex position if its points are exactly the vertices of a convex polygon. Writing $ES(n)$ for the smallest integer $N$ such that every set of $N$ points in the plane in general position contains $n$ points in convex position, the problem of determining $ES(n)$ is among the oldest in combinatorial geometry. It originated around 1933 with an observation of Esther Klein in a Budapest discussion group — every sufficiently large point set in general position contains some fixed number of points in convex position — and its study by Paul Erdős and George Szekeres produced the monotone subsequence lemma and, with it, modern Ramsey theory. It is affectionately known as the happy ending problem, in reference to the marriage of Klein and Szekeres.

Erdős and Szekeres proved in 1935 that $ES(n)\le\binom{2n-4}{n-2}+1=4^{n-o(n)}$, using the cups-caps argument: a $k$-cup (respectively $k$-cap) is a set of $k$ points forming an $x$-monotone convex chain, i.e. lying in order of increasing $x$-coordinate on the graph of a convex (respectively concave) function, and any long cup or cap is automatically in convex position. In 1960–61 they constructed, for every $n$, a set of $2^{n-2}$ points in general position with no $n$ points in convex position, giving $ES(n)\ge 2^{n-2}+1$, and conjectured this to be sharp:

$ES(n)=2^{n-2}+1\quad\text{for all }n\ge 3.$

For eight decades the upper bound resisted every change in its order of magnitude: refinements by Tóth and Valtr ($ES(n)\le\binom{2n-5}{n-2}+1$) and subsequent constant-factor improvements by Norin–Yuditsky and by Mojarrad–Vlachos brought $\limsup_{n\to\infty}ES(n)/\binom{2n-4}{n-2}\le 7/16$, still a constant times $4^n/\sqrt{n}$. The breakthrough came in 2016, when Andrew Suk proved that for all sufficiently large $n$,

$ES(n)\le 2^{\,n+6n^{2/3}\log_2 n},$

so $ES(n)=2^{n+o(n)}$: the remaining gap to the conjectured value is only a lower-order additive term in the exponent. Suk's proof is stated in the language of order types — the combinatorial classification of a planar point set by the orientation (left or right turn) of each ordered triple of points — and combines the cups-caps framework with positive-fraction and same-type transference tools for point sets.

The error term in the exponent was subsequently refined by Holmsen, Nassajian Mojarrad, Pach, and Tardos (2020), who carried Suk's argument over to pseudo-configurations — point sets whose connecting lines are replaced by an arrangement of pseudolines (curves that any two of which cross exactly once), a combinatorial relaxation formalized by uniform rank-3 acyclic oriented matroids — and thereby improved the known upper bound to

$ES(n)\le 2^{\,n+O\left(\sqrt{n\log n}\right)},$

still of the form $2^{n+o(n)}$ but with a smaller second-order term.

The exact conjecture is verified so far only for small $n$: $ES(3)=3$, $ES(4)=5$, $ES(5)=9$, and $ES(6)=17$, the last established by the computer-assisted work of Szekeres and Peters and later formalized in a proof assistant by Marić; the first open case is $ES(7)$, conjectured to equal $33$. Two cautions delimit what a resolution may look like. First, natural strengthenings can fail: the ps-gon conjecture of Peters and Szekeres (2006) — an ordered, monotone-path statement about edge-colorings of complete 3-uniform hypergraphs that would have implied the Erdős–Szekeres conjecture — was refuted by Balko and Valtr using SAT solvers, so the classical inductive framework cannot prove that stronger statement. Second, relaxations can hold at exactly the conjectured threshold: Baek and Balko (2026) proved that every $2^{k-2}+1$ points in general position contain a split $k$-gon — a configuration strictly weaker than convex position — and showed this threshold to be tight. As of August 2026, the conjecture $ES(n)=2^{n-2}+1$ itself remains open for every $n\ge 7$.

Problem Statement

Prove or disprove the Erdős–Szekeres conjecture:

$ES(n)=2^{n-2}+1\quad\text{for every integer }n\ge 3,$

where $ES(n)$ denotes the smallest integer $N$ such that every set of $N$ points in the plane in general position (no three collinear) contains $n$ points in convex position.

Since the lower bound $ES(n)\ge 2^{n-2}+1$ (Erdős–Szekeres, 1961) is known and the cases $n\le 6$ are verified, the open content is the matching upper bound: show that every set of $2^{n-2}+1$ points in general position contains $n$ points in convex position for every $n\ge 7$. In asymptotic form, a proof of the conjecture would close the gap

$2^{n-2}+1\le ES(n)\le 2^{\,n+O\left(\sqrt{n\log n}\right)}$

between the 1961 lower bound and the best known upper bound (Suk's $2^{\,n+6n^{2/3}\log_2 n}$, with the error term improved to $O(\sqrt{n\log n})$ by Holmsen–Mojarrad–Pach–Tardos, 2020), by bringing the additive term in the exponent down to the value $-2$ implied by the conjecture. A disproof consists of a single explicit counterexample: an integer $n\ge 7$ and a set of exactly $2^{n-2}+1$ points in general position, no $n$ of which are in convex position.

The conjecture asserts $ES(n)=2^{n-2}+1$ for every $n\ge 3$, so a bound valid only for all sufficiently large $n$ would leave the finitely many cases $7\le n<N_0$ unsettled; a refutation is a single counterexample configuration. This is the source question in its original unrestricted form: Suk's paper states it 'nearly settles' the conjecture and leaves the exact value, the optimal additive error in the exponent, and the structure of extremal configurations open.

References

1. Paul Erdős and George Szekeres, 'A combinatorial problem in geometry', Compositio Mathematica 2 (1935), 463–470. Full-text scan: https://www.renyi.hu/~p_erdos/1935-01.pdf
2. Paul Erdős and George Szekeres, 'On some extremum problems in elementary geometry', Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica 3–4 (1960/1961), 53–62. Full-text scan: https://www.renyi.hu/~p_erdos/1960-09.pdf
3. Géza Tóth and Pavel Valtr, 'The Erdős–Szekeres theorem: upper bounds and related results', in Combinatorial and Computational Geometry, MSRI Publications 52, Cambridge University Press (2005), 557–568. DOI: 10.1017/9781009701259.031, https://doi.org/10.1017/9781009701259.031
4. George Szekeres and Lindsay Peters, 'Computer solution to the 17-point Erdős–Szekeres problem', The ANZIAM Journal 48 (2006), 151–164. DOI: 10.1017/S144618110000300x, https://doi.org/10.1017/S144618110000300x
5. Sergey Norin and Yelena Yuditsky, 'Erdős-Szekeres without induction', arXiv:1509.03332 (2015); journal version in Discrete & Computational Geometry 55 (2016), 963–971. DOI: 10.1007/s00454-016-9778-2, https://arxiv.org/abs/1509.03332
6. Hossein Nassajian Mojarrad and Georgios Vlachos, 'An Improved Upper Bound for the Erdős–Szekeres Conjecture', Discrete & Computational Geometry 56 (2016), 165–180. DOI: 10.1007/s00454-016-9791-5, arXiv:1510.06255, https://arxiv.org/abs/1510.06255
7. Andrew Suk, 'On the Erdős–Szekeres convex polygon problem', Journal of the American Mathematical Society 30 (2017), 1047–1053 (online 2016). DOI: 10.1090/jams/869, arXiv:1604.08657, https://arxiv.org/abs/1604.08657
8. Filip Marić, 'Fast Formal Proof of the Erdős–Szekeres Conjecture for Convex Polygons with at Most 6 Points', Journal of Automated Reasoning 62 (2017), 301–329. DOI: 10.1007/s10817-017-9423-7, https://doi.org/10.1007/s10817-017-9423-7
9. Martin Balko and Pavel Valtr, 'A SAT attack on the Erdős–Szekeres conjecture', European Journal of Combinatorics 66 (2017), 13–23. DOI: 10.1016/j.ejc.2017.06.010, https://doi.org/10.1016/j.ejc.2017.06.010
10. Jineon Baek, 'On the Erdős–Tuza–Valtr Conjecture', arXiv:2206.04260 (2022); journal version in European Journal of Combinatorics 124 (2025), 104085 (online 2024). DOI: 10.1016/j.ejc.2024.104085, https://arxiv.org/abs/2206.04260
11. Jineon Baek and Martin Balko, 'The Erdős–Szekeres conjecture revisited', Journal of Combinatorial Theory, Series A 222 (2026), 106195. DOI: 10.1016/j.jcta.2026.106195, https://doi.org/10.1016/j.jcta.2026.106195
12. Bogdan Dumitru, 'Notes on the 33-point Erdős–Szekeres problem', arXiv:2512.24061 (2025). https://arxiv.org/abs/2512.24061