问题
快乐结局定理(Erdős–Szekeres 1935, «Happy Ending» 的恋爱史话):任意足够多的平面一般位置点(无三点共线)含 k 点凸 k 边形。 ES(k) = 最少点数。已知 ES(5) = 9(35 年悬置,2006 年计算机穷举解决)、ES(6) = 17(Suk 2016);ES(7) 起完全开放(已知 33 ≤ ES(7))。
主要概念
上界机器:cup–cap 与 Suk 机器
原证明用 «cup–cap» 二分(Erdős–Szekeres 单调子列定理的几何版)给 ES(k) ≤ C(2k−5, k−2) + 1(双指数);Suk 2016 的机器用 «立方体分割 + 洞引理» 把渐近压到 ES(k) = 2k+o(k)——与下界 2k−2+1( «Erdős–Szekeres 构造»)在指数层匹配。 «渐近之后» 的残余:常数层与中等 k 的精确值。
下界构造
«Erdős–Szekeres 构造»:递归 «cup 块 ∪ cap 块» 得无凸 k 边形的 2k−2 点集——下界 2k−2+1。ES(7) 的已知下界 33 vs 已知上界(Suk 型的显式常数)之间仍有数倍。
主要命题与证明
命题 1(原 cup–cap 定理,完整骨架) ES(k) ≤ C(2k−4, k−2) + 1。
梗概 每点赋对 (a, b)(向左最长 cup 长度、向右最长 cap 长度); «鸽笼 » 论证:点数 ≥ C(2k−4, k−2)+1 时必有两点同对,而 «同对两点» 的 «连线延长» 必破 a 或 b 的极值性——推出矛盾前的 «新 cup/cap» 增长;归纳得 «大点集含 k-cup 或 k-cap»,二者皆含凸 k 边形。□
命题 2(Suk 渐近定理骨架) ES(k) ≤ 2k+6k2/3log k。机器: «凸链分解»(点集按 «上凸链» 分层)+ «空凸链引理»(每层有 «富» 凸结构)+ «层间拼接»—— «概率吸收» 的离散几何首秀。
进展与文献
Erdős–Szekeres 1935/1961;Szekeres–Peters 的 ES(5) 计算机证明(2006);Suk 2016(ES(6)=17 与渐近,JAMS);Holmsen–Mojarrad–Pach–Tardos 的 «空凸» 变体;Šileikis–... 的概率下界。开放核心:ES(7)(33 与 «Suk 显式» 之间的窄带—— «中等 k 精确值» 需 «混合方法»:Suk 机器的 «层» 结构 + 计算机可证的小层引理); «空凸 k 边形» 版(GER(k), k = 7 已证存在、 k ≥ 8 开放)独立成趣。