Erdős–Szekeres convex-polygon problem

Open

erdos-szekeres-convex-polygon

Statement

Let $ES (n)$ be the least $N$ such that any $N$ points in general position contain a convex $n$ -gon. Prove the conjectured exact value $ES (n) = 2^{n - 2} + 1$ .

Current frontier

erdosproblems.com/107, OPEN. Erdős–Szekeres proved the upper bound (1935) and the lower bound $2^{n - 2} + 1 \leq ES (n)$ (1960), conjecturing equality; Suk (2017), refined by Holmsen–Mojarrad–Pach–Tardos (2020) to $2^{n + O (n l o g n)}$ , nearly matches. Exact values are known only through $n = 6$ ( $ES (6) = 17$ ).

When this counts as solved

VALUE-DETERMINATION

PROOF_COMPLETE for $ES (n) = 2^{n - 2} + 1$ for all $n$ , COUNTEREXAMPLE for a violating $n$ . BREAKTHROUGH for a new exact value $ES (n)$ , $n \geq 7$ , or the formula on an infinite subfamily.

Classification

Value-determination

Mine this problem →