FALSIFIABLE
Open, but could be disproved with a finite counterexample.
- $500
Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$, no three on a line, contain $n$ points which form the vertices of a convex $n$-gon. Prove that $f(n)=2^{n-2}+1$.
The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
The Erdős-Klein-Szekeres 'Happy Ending' problem. The problem originated in 1931 when Klein observed that $f(4)=5$. Turán and Makai showed $f(5)=9$. Erdős and Szekeres proved the bounds\[2^{n-2}+1\leq f(n)\leq \binom{2n-4}{n-2}+1.\](
[ErSz60] and
[ErSz35] respectively). There were several improvements of the upper bound, but all of the form $4^{(1+o(1))n}$, until Suk
[Su17] proved\[f(n) \leq 2^{(1+o(1))n}.\]The current best bound is due to Holmsen, Mojarrad, Pach, and Tardos
[HMPT20], who prove\[f(n) \leq 2^{n+O(\sqrt{n\log n})}.\]In
[Er97e] Erdős clarifies that the \$500 is for a proof, and only offers \$100 for a disproof. Graham
[Gr04] offers \$1000 for a proof.
This problem is
#1 in Ramsey Theory in the graphs problem collection.
See also
[216],
[651], and
[838].
View the LaTeX source
This page was last edited 11 April 2026. View history
Additional thanks to: Casey Tompkins and Wouter van Doorn
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #107, https://www.erdosproblems.com/107, accessed 2026-07-16
0 claimed proofs for this problem