未解决问题，组合数学与离散数学, 几何学，1935年提出

圆满结局问题（埃尔德什–塞克雷什）

未解决埃尔德什

对任意整数 $n \ge 3$ ，欧几里得平面 $\mathbb{R}^2$ 中处于一般位置（无三点共线）的任意 $2^{n-2} + 1$ 个点的集合是否必包含某个凸 $n$ 边形的 $n$ 个顶点——亦即保证存在凸 $n$ 边形的最小点数是否恒为 $\mathrm{ES}(n) = 2^{n-2} + 1$ ？

提出者, 1935保罗·爱尔特希

研究前沿截至2026年

截至2026年，精确公式 $\mathrm{ES}(n) = 2^{n-2} + 1$ 仅在 $n = 3, 4, 5, 6$ 时获证，即 $\mathrm{ES}(3) = 3$ 、 $\mathrm{ES}(4) = 5$ 、 $\mathrm{ES}(5) = 9$ 和 $\mathrm{ES}(6) = 17$ ；甚至 $n = 7$ 的情形（猜想为 $\mathrm{ES}(7) = 33$ ）仍未解决。在渐近方向上，继安德鲁·苏克2016年证明 $\mathrm{ES}(n) = 2^{n + o(n)}$ 之后，霍尔姆森、莫贾拉德、帕赫与塔尔多什（2020）将上界误差项改进为 $\mathrm{ES}(n) \le 2^{n + O(\sqrt{n \log n})}$ ，使上下界之间仅相差一个亚指数因子。

已知最佳结果

精确值： $\mathrm{ES}(3) = 3$ 、 $\mathrm{ES}(4) = 5$ （克莱因，1933）、 $\mathrm{ES}(5) = 9$ （毛科伊–图兰，1935）以及 $\mathrm{ES}(6) = 17$ （塞克雷什–彼得斯，2006）。
对所有 $n \ge 3$ ，有 $2^{n-2} + 1 \le \mathrm{ES}(n) \le 2^{n + O(\sqrt{n \log n})}$ （埃尔德什–塞克雷什 1960；苏克 2016/2017；霍尔姆森–莫贾拉德–帕赫–塔尔多什 2020）。

使用的方法及其局限

方法	取得的结果	局限所在
正比例杯-帽分解法（波尔–瓦尔特、苏克）	利用波尔–瓦尔特正比例定理将点集的主体划分为位于狭窄锥域内的 $k$ 个凸独立子集，从而能够对凸链与凹链进行联合归纳，将指数底数由 $4$ 降至 $2$ 。	在递归的每一层向正比例子集过渡时都会损失 $O(k^4)$ 量级的常数因子，层层累积后便在 $2^{n-2} + 1$ 之上产生了 $2^{O(\sqrt{n \log n})}$ 的额外开销。

尚未解决的问题

平面上一般位置的任意 $33$ 个点的集合是否必定包含一个凸七边形的顶点（即 $\mathrm{ES}(7) = 33$ 是否成立）？
等式 $\mathrm{ES}(n) = 2^{n-2} + 1$ 是否对所有整数 $n \ge 3$ 都成立？

参考文献

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