Problem Statement
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$.
Categories:
Geometry Convex
Progress
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.This problem is #1 in Ramsey Theory in the graphs problem collection.
See also [216], [651], and [838].
Source: erdosproblems.com/107 | Last verified: January 13, 2026