跳转到内容
← 返回研究前沿
组合学2020s约 14 分钟阅读

拉姆齐数与组合学的新工具

Ramsey Numbers and the New Toolkit of Combinatorics

2023 年 3 月，四位组合学家——Marcelo Campos 与 Robert Morris（里约热内卢 IMPA）、Simon Griffiths（里约天主教大学）、Julian Sahasrabudhe（剑桥大学）——在 arXiv 上贴出一篇 100 多页的论文，标题平淡："An exponential i…

拉姆齐数极值组合学概率方法图论容器法

2023 年 3 月，四位组合学家——Marcelo Campos 与 Robert Morris（里约热内卢 IMPA）、Simon Griffiths（里约天主教大学）、Julian Sahasrabudhe（剑桥大学）——在 arXiv 上贴出一篇 100 多页的论文，标题平淡："An exponential improvement for diagonal Ramsey"。

这篇论文做的是一件 88 年没人做到的事：把拉姆齐数 $R(k)$ 的上界从 4k4^k 真正压下来，压到 (4−ε)k(4-\varepsilon)^k。这里的 ε\varepsilon 是一个正的常数（论文未做优化，取了 ε=1/128\varepsilon = 1/128）。在普通人看来，从 4 减到 3.99 多一点不值一提；但在组合学家看来，底数上的任何一点常数级改进，都意味着统治这个领域近一个世纪的方法论天花板被击穿了。论文随后被《数学年刊》（Annals of Mathematics）接收，于 2026 年正式刊出。

破除误解：不是"又一个数被算出来"

先澄清两个常见误解。

误解一：拉姆齐数问题是要算出具体数值。 不是的。目前已精确求出的二色对角拉姆齐数只有四个：$R(3)=6$、$R(4)=18$，以及平凡的 $R(1)=1$、$R(2)=2$。$R(5)$ 至今只知道在 43 与 48 之间。Erdős 有个广为流传的玩笑（经 Ronald Graham 转述）：如果外星人逼人类交出 $R(5,5)$，我们应该集中全人类的计算机去算；如果逼我们交出 $R(6,6)$，我们应该想办法消灭外星人。真正的研究前沿不是具体数值，而是渐近行为：当 $k$ 趋于无穷时，$R(k)$ 以多快的速度增长。

误解二：上界改进只是"常数优化"。 也不是。1935 年 Erdős–Szekeres 证明 R(k)≤(2k−2k−1)<4k−1R(k) \leq \binom{2k-2}{k-1} < 4^{k-1}，1947 年 Erdős 用概率方法证明 R(k)>2k/2=(2)kR(k) > 2^{k/2} = (\sqrt{2})^k。此后几十年，上界与下界的改进都只是多项式或超多项式因子级别的——2009 年 David Conlon 在《数学年刊》上把上界改进了一个超多项式因子，但指数底数 4 纹丝不动。底数动与不动，是质与量的区别。

现场：这个问题在问什么

把完全图 KnK_n 的每条边染成红色或蓝色。$R(k)$ 是保证"无论怎么染，都必然出现一个全红或全蓝的 KkK_k"的最小顶点数 $n$。

直觉上这是个"秩序不可回避"的问题：足够多的无序之中必然藏着一块大的有序结构。Erdős 1947 年的下界证明开创了概率方法——一个随机染色大概率不含单色 KkK_k，所以这样的染色存在；但注意，这个证明没有给出任何具体构造。上界一侧，Erdős–Szekeres 的论证本质是贪心归纳：每个顶点看出去，红邻域和蓝邻域必有一个很大，递归下去就得到 4k4^k。88 年里，所有人都卡在这个框架里。

难点在哪？要改进底数，你必须证明：在染色接近"最坏情况"时，图的结构受到极强的约束，而这种约束最终与自身矛盾。这要求对中等尺度上的局部结构做精密的簿记，而不是只看一步贪心。

谁在做、做到了哪一步

Campos–Griffiths–Morris–Sahasrabudhe（2023）：击穿底数 4

四人的核心机制被概括为"书算法"（book algorithm）：不再逐步追踪单个顶点，而是同时追踪一大批"书"——即完全二部子图 Ks,tK_{s,t}——的密度演化，证明在缺乏单色团的情况下，这些结构会不可持续地膨胀，直到矛盾。这套簿记异常精细，论文超过 100 页，给出的 ε=1/128\varepsilon = 1/128 只是顺手取的值，没有优化。

Gupta–Ndiaye–Norin–Wei（2024）：简化并压到 3.8

2024 年 7 月，麦吉尔大学的 Sergey Norin 与三位合作者（arXiv:2407.19026）把书算法替换为一个干净的归纳命题，大幅缩短了证明，并在优化参数后得到

R(k)≤(3.8)k+o(k).R(k) \leq (3.8)^{k+o(k)}.

这是目前的最佳上界底数。它说明 CGMS 的突破不是一次性的苦役，而是一种可以打磨的新范式。

Ma–Shen–Xie（2025）：下界也动了

2025 年 7 月，中国科学技术大学的马杰（Jie Ma）与两位合作者（arXiv:2507.12926）引入"随机球面图"模型：在高维球面上随机取点，用高维几何的反直觉性质——随机方向之间几乎接近正交——来控制团与独立集的形成，给出了 Erdős 1947 年下界 (2)k(\sqrt{2})^k 的首次指数级改进。上下界两端在同一十年里先后松动，这是拉姆齐数研究史上从未有过的局面。

非对角与多色：整条战线都在推进

问题旧纪录新进展作者与出处
对角 $R(k)$ 上界4k4^k（1935）(4−ε)k(4-\varepsilon)^k（2023），再优化至 (3.8)k+o(k)(3.8)^{k+o(k)}（2024）CGMS，Ann. of Math. 203 (2026)；Gupta 等，arXiv:2407.19026
对角 $R(k)$ 下界(2)k(\sqrt{2})^k（1947）(2+ε)k(\sqrt{2}+\varepsilon)^k（2025）Ma–Shen–Xie，arXiv:2507.12926
非对角 $r(4,t)$上下界差多项式因子定为 t3t^3 量级（仅差对数因子）Mattheus–Verstraete，Ann. of Math. 199 (2024)
多色对角 Rr(k)R_r(k)Erdős–Szekeres 型经典界指数级改进Balister 等八人，J. Amer. Math. Soc. 39 (2026)

其中 Sam Mattheus 与 Jacques Verstraete 确定 $r(4,t)$ 渐近量级的工作尤为醒目：自 1995 年 Jeong Han Kim 确定 r(3,t)=Θ(t2/log⁡t)r(3,t) = \Theta(t^2/\log t) 之后，非对角拉姆齐数近三十年没有第二个被攻克的案例。

工具箱的换代

比单个结果更重要的是方法层的更替。2010 年代成熟的超图容器法（Balogh–Morris–Samotij 与 Saxton–Thomason，2015）教会人们如何用少量"容器"装下一个超图的全部独立集，从而把计数问题化约为稀疏性分析；Ashwin Sah 2023 年关于"有效拟随机性"的工作（Duke Math. J.）则为逼近最坏情形提供了另一种语言。2022 年 Justin Gilmer 用熵方法攻击"并集封闭集猜想"，首次给出正常数下界（随后被多方改进到 0.38 以上），展示了信息论工具侵入极值组合学的深度。书算法、容器、熵、拟随机性——这些是 2020 年代组合学的通用语。

代价与争议

下界的"存在性"原罪。 Erdős 1947 年的下界与 Ma–Shen–Xie 2025 年的改进都基于随机构造：它们证明好的染色存在，却不告诉你怎么造一个。显式构造的拉姆齐下界远远落后于随机界——这被视为组合学最令人难堪的裂缝之一，也直接连着计算复杂性理论中"去随机化"的困难。

ε\varepsilon 的现实意义。 (3.8)k(3.8)^k 与 4k4^k 在 $k$ 很大时天差地别，但对人类能算的任何具体 $k$，这种改进毫无计算价值。它的全部意义在于方法论：证明贪心框架不是极限。有学者私下质疑这类工作的"实际产出"，主流意见则认为，击穿 88 年的底数僵局本身就是范式信号——历史经验是，底数一旦松动，往往会一路被磨下去。

上下界之间仍是深渊。 即使经过 2023–2025 年的双重改进，上界底数 3.8 与下界底数略大于 2≈1.414\sqrt{2} \approx 1.414 之间仍有巨大鸿沟。没人知道真理靠近哪一端，甚至没人知道 R(k)1/kR(k)^{1/k} 的极限是否存在——这是 Erdős 生前悬赏的问题，至今无人领走奖金。

未知的边界

  • R(k)1/kR(k)^{1/k} 的极限是否存在？ 这是拉姆齐理论最著名的开放问题。若存在，其值落在 (2,3.8](\sqrt{2}, 3.8] 之间，仅此而已。
  • 显式构造何时追平随机界？ 这等价于在组合学里回答一个"P vs. 随机性"式的问题，目前连方向都不明朗。
  • 容器法的边界在哪里？ 容器法在图与超图的独立集计数上战无不胜，但对加法组合学中更"刚性"的结构（如等差数列约束）效果有限，两类工具如何合流是活跃议题。
  • 多色与高维推广。 Balister 等八人 2024 年把 CGMS 范式推广到了多色情形，但超图拉姆齐数（三元组乃至更高元的染色）的指数塔式增长行为依然几乎完全未被理解。

跨域连接

  • 概率论：Erdős 1947 年用随机染色证明下界时，概率只是"存在性的证人"；Ma–Shen–Xie 2025 年的随机球面图则把概率模型本身当作研究对象来设计。推论：在组合学里，随机性既是修辞也是引擎——造一个"足够像随机"的结构，往往就是证明本身。
  • 随机算法：拉姆齐下界断言"无大团的染色存在"，而算法理论问"能否高效找到它"。推论：存在性证明与构造性算法之间的落差，是拉姆齐理论与去随机化理论共同的伤口——一边的每次改进都在拷问另一边。
  • 信息论：Gilmer 用熵约束自由度、CGMS 的书算法在尺度间做信息簿记，本质都是"用信息量给混乱记账"。推论：香农熵正在变成极值组合学的标准度量——混乱程度第一次可以被定量地花掉。
  • 数学哲学：概率方法证明存在却不给实例，是"非构造性存在证明"最锋利的现代样本。推论：它把布劳威尔直觉主义的旧质疑逼出了新形式——当存在性只能以概率论证，"存在"到底承诺了什么。
  • 图论：拉姆齐数是图论"局部稀疏则全局必有结构"这一总主题的最纯粹形态。推论：拟随机性、正则性引理与拉姆齐理论共享同一底层直觉——足够大的图没有真正的任意性；而书算法证明，这种"没有任意性"可以在中观尺度上被逐层追踪并变现为指数级的界。

参考文献

  • Campos, M., Griffiths, S., Morris, R. & Sahasrabudhe, J. "An exponential improvement for diagonal Ramsey." Annals of Mathematics 203 (2026), 869–932；预印本 arXiv:2303.09521（2023 年 3 月上传）。
  • Mattheus, S. & Verstraete, J. "The asymptotics of $r(4,t)$." Annals of Mathematics 199 (2024), 919–941. DOI: 10.4007/annals.2024.199.2.8.
  • Gupta, P., Ndiaye, N., Norin, S. & Wei, L. "Optimizing the CGMS upper bound on Ramsey numbers." arXiv:2407.19026 (2024).
  • Ma, J., Shen, W. & Xie, S. "An exponential improvement for Ramsey lower bounds." arXiv:2507.12926 (2025).
  • Balister, P., Bollobás, B., Campos, M., Griffiths, S., Hurley, E., Morris, R., Sahasrabudhe, J. & Tiba, M. "Upper bounds for multicolour Ramsey numbers." Journal of the American Mathematical Society 39 (2026), 765–780.
  • Saxton, D. & Thomason, A. "Hypergraph containers." Inventiones Mathematicae 201 (2015), 925–992.

延伸阅读

  • Morris, R. "Some recent results in Ramsey theory." arXiv:2601.05221 (2026).（亲历者综述）
  • Radziszowski, S. "Small Ramsey numbers." Electronic Journal of Combinatorics 动态综述（持续更新的小拉姆齐数档案）。

正文中引用本条 · 1