未解決問題、組合せ論と離散数学, 幾何学、1935年に提起

ハッピーエンド問題（エルデシュ・セケレシュ）

未解決エルデシュ

すべての整数 $n \ge 3$ に対し、ユークリッド平面 $\mathbb{R}^2$ 内の一般の位置（どの3点も同一直線上にない）にある任意の $2^{n-2} + 1$ 個の点の集合は、凸 $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$ へと引き下げた。	再帰の各段階で正の比率の部分集合へ移行する際に1段階あたり $O(k^4)$ の因子が失われ、 $2^{n-2} + 1$ に対して $2^{O(\sqrt{n \log n})}$ の余剰因子が蓄積してしまう。

未解決の問い

平面上の一般の位置にある任意の $33$ 点の集合は、凸七角形の頂点を必ず含むか（ $\mathrm{ES}(7) = 33$ か）。
すべての整数 $n \ge 3$ に対して $\mathrm{ES}(n) = 2^{n-2} + 1$ が成り立つか。

参考文献

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