中国数学家三jié联手（马杰、申武杰、谢晟捷）升级著名的埃尔德什（Erdős）概率方法，改进拉姆齐数下界——译自量子杂志Quanta Magazine|中国数学家|保罗|埃尔德什|拉姆齐|斯宾塞|申武杰|谢晟捷

★置顶zzllrr小乐公众号，追踪《小乐数学科普》系列报道，参与数学 vs AI投票！

几十年前，保罗·埃尔德什（Paul Erdős）利用随机性来阐明庞大而奇特的网络世界。如今，数学家们正在使他的方法更加强大。

图源：Robert Neubecker | 量子杂志

AI vs Math 投票火热进行中

Your Vote Matters! We Value Your Value!

作者：Leila Sloman（莱拉·斯洛曼，量子杂志特约作家）2026-6-26

译者：zzllrr小乐（数学科普公众号）2026-6-27

求喜欢

1947 年，常年辗转各地的匈牙利数学家保罗・埃尔德什（Paul Erdős）创造出日后成为数学界最强证明手段之一的方法。当时他需要证明一类数学对象必然存在：由节点相互连接形成的网络，也就是图（graph）。他没有直接构造出这个网络，而是另辟蹊径：在所有可能的网络里随机选取一个，抽到符合条件网络的概率大于 0。这就足以证明，满足条件的网络一定存在，哪怕我们写不出它的具体结构。

这套方法后来被称作概率方法（probabilistic method），想法简单却石破天惊。苏黎世联邦理工学院数学家本尼・苏达科夫（Benny Sudakov）评价道：“放在过去，如果我说某个对象一定存在，别人会要求我举出实例。但有些对象结构极为复杂，根本很难直观构造出来。”

埃尔德什（Erdős）完美破解了这一困境，证明随机性可以被用在数学家从前难以想象的地方。纽约大学的乔尔・斯宾塞（Joel Spencer）说道：“在当年，用随机性完成证明是惊世之举，如今它已经成为一项基础通用技术。”

时至今日，概率方法已经渗透到数学与计算机科学的众多分支：素数判定、电路设计、数据去偏处理，都会用到它。

长期以来，研究者对该方法做过各类优化，但埃尔德什最初研究的网络核心问题，整整八十年都没有本质突破。现在，僵局终于被打破。

荒野中的孤声

设想一张由大量节点构成的完全图（complete graph），任意两个节点（node）之间都有一条边。

图源：Mark Belan / Quanta Magazine

我们把每一条边染成红色或者蓝色，同时要规避大规模同色节点团。这种被禁止的结构叫作单色团（monochromatic clique）。由 3 个顶点构成的单色团，就是 3 阶团。

一个大小为3的单色团的例子。

只要图的顶点足够多，无论怎么染色，都躲不开单色团。举个例子：想要完全避开 3 阶单色团，整张图最多只能有 5 个顶点；一旦顶点数达到 6，必然会产生 3 阶单色团。

数学家把对应 3 阶团的拉姆齐数记作 R(3)=6。拉姆齐数（Ramsey number）刻画一张图在必然出现指定单色团之前，最多可以容纳多少个顶点。

我们还可以定义两种不同规模的团对应的拉姆齐数。例如：8 个顶点的完全图可以染色做到既不含红色 3 阶团，也不含蓝色 4 阶团；只要再多一个顶点，就一定会冒出某一种单色团。于是就有 R(3,4)=9。

随着团的规模变大，求解难度呈爆炸式增长。人类至今只算出极少数小拉姆齐数。丹佛大学的保罗・霍恩（Paul Horn）表示：“构造不含规整结构的图异常艰难，或许是人类思维本身就带有固有偏见。”

几十年来，数学家一直在寻找拉姆齐数更精确的下界，这正是 1947 年埃尔德什（Erdős）创立概率方法的初衷。他不去直接构造无单色团的图，而是遍历全部染色方案，证明存在非零比例的染色结果不含单色团。

埃尔德什（Erdős）用这一论证证明：如果同时规避红、蓝两种 k 阶单色团，对角拉姆齐数 R(k) 一定大于(√2)ᵏ。规模相同的红团和蓝团的拉姆齐数称为对角拉姆齐数。

对于“非对角”拉姆齐数 R(k,l)（规避红色 k 阶团、蓝色 l 阶团），他也用同一思路给出了下界。

短短几行证明，得出了震撼学界的结论。

一开始，数学家并不愿意接受这种思路，大家更偏爱看得见的构造实例。斯宾塞（Joel Spencer）回忆：“很长一段时间里，埃尔德什（Erdős）就像旷野里独自呐喊的人。仅凭随机性就能推出深刻结论，这在以前闻所未闻。”

很快，概率方法（probabilistic method）展现出强大威力。如今它是离散数学（Discrete Mathematics，离散数学研究的是分离而非连续的对象，例如图）的核心工具，还广泛应用于物理与计算机科学。霍恩（Paul Horn）说道：“随机性可以捕捉到我们直观想象不到的抽象规律。”

近些年，学者改造埃尔德什的方法，对两个团规模差距悬殊的非对角拉姆齐数得到了更优估计（详情参阅。2025年，霍恩与三位合作者使用改良版概率方法，证明了当 l 充分大时，R(3,l) 更加精确的下界 https://arxiv.org/abs/2510.19718 ，推动图论实现重大进展 https://arxiv.org/abs/2512.20392 。

保罗・埃尔德什（Paul Erdős）开创了借助随机性证明对象存在的范式，即便我们无法把对象具体构造出来。这套概率方法（probabilistic method）彻底重塑了数学与计算机科学诸多分支。

图源：奥伯沃尔法赫数学研究所，加布里埃拉・博洛巴斯（Gabriella Bollobás）摄

可是当两个禁团规模比较接近时 —— 尤其是埃尔德什最早研究的对角拉姆齐数，概率方法长期止步不前。举个例子：我们要避开 1000 阶单色团，埃尔德什给出 R(1000)＞2⁵⁰⁰；八十年间反复打磨，下界仅仅被小幅改进到 2⁵⁰¹。同样，从1970年代开始，两个团都很大的非对角拉姆齐数研究几乎陷入停滞。

就在此时，一名几乎没有拉姆齐理论（Ramsey Theory）研究经历的研究生提出了新方案。

关联染色法

申武杰（YMSC清华大学丘成桐数学科学中心博士研究生）在清华大学入学初期，主要研究几何与拓扑。2024年春季，他读到一篇拉姆齐数论文 https://annals.math.princeton.edu/2024/199-2/p08 ，立刻被这个问题深深吸引。

他非常熟悉埃尔德什的经典套路：抛掷硬币决定每条边的颜色，正面染红、反面染蓝，再计算整张图不含单色团的概率。但顶点数量变大之后，这项计算会变得极度复杂。申武杰开始思考：能不能设计一种随机模型，比传统埃尔德什方法更容易生成无单色团的染色方案？

依托自身几何方向的训练，他很自然地引入几何手段。普通图染色完全不考虑几何结构：只关心两点之间是红边还是蓝边，顶点在空间中的位置无关紧要。

申武杰打算依靠几何距离来给边定色，核心工具是高维球面，也就是空间中到定点距离相等的全体点构成的集合。

加州理工学院的戴维・康伦（David Conlon）评价：“高维球面完全违背日常直觉。二维、三维球面的经验在高维空间全部失效：高维球面体积极小、表面积巨大，绝大多数点都聚集在赤道附近。” 苏达科夫（Benny Sudakov）坦言：“高维球面的计算十分棘手。”

即便如此，申武杰连同两位合作者 —— 秋季来清华授课的马杰（USTC中国科技大学数学科学院教授），以及马杰的研究生谢晟捷（中国科学技术大学数学科学学院三年级博士研究生，本科毕业于中国科学技术大学少年班学院），决定试水这套几何模型。

三人的操作步骤：

把所有顶点独立随机撒在高维球面表面；

布点完成后，依据两点之间的球面距离染色：两点间距超过临界阈值（发生概率小于 1/2），边染红色；距离更近，则染蓝色。

左到右：马杰（Jie Ma）、申武杰（Wujie Shen）、谢晟捷（Shengjie Xie）；图源：马杰提供、申武杰提供、赵子元拍摄

这套构造会大幅降低产生红色单色团的概率。原因是：想要形成大规模红色团，必须有一大批彼此相距极远的顶点，而在球面空间里，这种情形很难出现。

但方案存在取舍：相比埃尔德什原始模型，它更容易长出蓝色单色团。康伦（David Conlon）提出疑问：“等于压制了红色团，却抬高了蓝色团，这么做还有意义吗？”

尽管存在短板，马杰、申武杰、谢晟捷依然看好这条路径。他们先在小规模图上做检验：即便大部分随机染色都会产生单色团，仍然有非零概率得到完全不含单色团的合格染色。这让他们确信，针对大规模图，收益足以抵消缺陷。

随后三人展开严格证明，突破口就在于高维球面独有的几何性质。

要证明该模型可以避开指定规模的单色团，需要控制随机布点形成 “相互远离” 或者 “相互靠近” 顶点簇的概率。他们发现：把每个顶点和球心连线，绝大多数连线几乎两两垂直；二维球面随机布点绝不会有这种现象，但在超高维空间里，这条结论严格成立。

这一几何约束直接限制了顶点之间的远距离分布，压低了形成单色团的概率。

经过一年、总计40页严密推导，三人在2025年7月发布预印本论文 https://arxiv.org/abs/2507.12926 。他们成功改进了埃尔德什（Erdős）给出的拉姆齐数下界，虽然只适用于蓝色团大于红色团的情形；当红蓝团大小相等时，新方法不再占优。

即便如此，当红色团规模大约是蓝色团一半时，他们把原来埃尔德什给出的阶数 ((√5+1)/2)ᵏ 小幅提升到 ((√5+1)/2 + 10⁻²¹)ᵏ。数值改动微乎其微，却是近50年来人类第一次对近对角拉姆齐数（near-diagonal Ramsey number）下界取得实质性突破。

马杰说：“我们很幸运，漫长的付出终于有了结果，整个研究过程充满煎熬。”

剑桥大学朱利安・萨哈斯拉布德（Julian Sahasrabudhe）评论：“用一个早已为人熟知的几何工具攻克拉姆齐难题，实在出人意料。办法一直摆在眼前，只是没人想到这么用。”

随机性的研究沃土

马杰、申武杰、谢晟捷的论文问世之后，学界接连诞生一系列后续成果。2025年12月，苏达科夫（Benny Sudakov）和两名学生大幅简化了这套几何染色模型，进一步收紧拉姆齐数下界 https://arxiv.org/abs/2512.17718 ；后续还有学者依托该模型，研究三种染色情形下的拉姆齐数 https://arxiv.org/abs/2601.15183 。

这正是概率方法八十年发展的缩影。几十年来，数学家不断改造埃尔德什的随机证明框架，叠加几何、代数结构放大威力，而这些改良又持续反哺其他数学分支。苏达科夫说道：“概率方法是孕育新思想的沃土。”

三人的成果，是这段八十年研究历程的最新篇章，也是数十年来学界重新深耕近对角拉姆齐难题的标志性进展。

他们搭建的几何框架，有望持续推动这个长期停滞的经典问题不断取得新结果。斯宾塞（Joel Spencer）感慨：“概率方法还远非完美，但它的威力已经足够震撼，彻底改写了组合数学（Combinatorics）的研究格局。”

参考资料

https://www.quantamagazine.org/after-80-years-mathematicians-give-famed-erdos-method-an-upgrade-20260626/

https://arxiv.org/abs/2507.12926

https://arxiv.org/abs/2512.17718

https://arxiv.org/abs/2601.15183

https://arxiv.org/abs/2510.19718

https://arxiv.org/abs/2512.20392

https://annals.math.princeton.edu/2024/199-2/p08

https://news.ustc.edu.cn/zqzjg/info/1005/1182.htm

小乐数学科普近期文章

小乐数学科普历年合集

版权声明：本文首发于微信公众号“zzllrr小乐”的专栏《小乐数学科普》。欢迎个人转发。如需转载，请在“zzllrr小乐”公众号后台回复“转载”，还可通过公众号菜单、发送邮件到zzllrr@gmail.com与我们取得联系。相关图文音视频内容默认遵守CC BY-NC 4.0知识共享协议，未获作者和译者授权，禁止用于营销宣传和商业目的。如有勘误，请反馈给zzllrr小乐公众号第一时间更正，其他平台非首发或无法多次同步，未必会及时更正同一错误，望予以谅解。

·开放 · 友好 · 多元 · 普适 · 守拙·