困扰世界近一个世纪的数学难题：拉姆齐问题已被破解

拉姆齐问题，如 r(4,5)，陈述起来很简单，但如图所示，可能的解几乎是无穷无尽的 图/Jacques Verstraete/加州大学圣地亚哥分校

拉姆齐定理（英语：Ramsey's theorem），又称拉姆齐二染色定理，断言对任意正整数 k 和 l ，若一个聚会的人数 n 足够大，则无论相识关系如何，必定有 k 个人相识或 l 个人互不相识。给定 k , l 时，保证前述结论的最小 n 值称为拉姆齐数 R ( k , l ) ，其值取决于 k , l 。用图论术语复述：若将足够大的完全图各边染红蓝两色，则不论如何染，必定有红色的 k 阶完全图或蓝色的 l 阶完全图。

拉姆齐定理是组合数学的重要结论，以弗兰克·普伦普顿·拉姆齐命名。他在1930年论文《论形式逻辑的一个问题》证明此定理最初的版本，开创现称拉姆齐理论的组合理论分支。拉姆齐理论的主题是从“无序”寻找“规律”，希望找出某数学结构中，存在规律子结构的一般条件。在拉姆齐定理的图论表述中，此“规律子结构”是同色集（monochromatic set），即顶点集的子集，其中各边皆染成同一颜色。

拉姆齐理论是以英国数学家和哲学家弗兰克-P-拉姆齐（Frank P. Ramsey）的名字命名的数字游戏的一个分支，非常复杂。在这个图论数学的角落里，最著名的问题是 r(3,3)，通常被称为朋友和陌生人定理，它假设在一个由六个人组成的小组中，你会发现至少有三个人互相认识，或者有三个人互相不认识。显然，r(3,3)的答案是6。

"这是自然界的事实，是绝对真理。不管情况如何，也不管你选择哪六个人，你都能找到三个互相认识的人，或者三个互相不认识的人。也许你能找到更多的人，但你能保证至少有三个人在一个小集团或另一个小集团中。"

一旦找到了 r(3,3)，数学家们就开始寻找后续问题的答案：r(4,4)、r(5,5)和 r(4,t)，在这些问题中，不相连的点的数量各不相同。

数学家们发现 r(3,3) 的答案是 6 之后，又发生了什么呢？自然，他们想知道 r(4,4)、r(5,5) 和 r(4,t)，其中不相连的点的数目是可变的。上世纪，埃尔德什和乔治-塞克雷斯发现 r(4,4) 的答案是 18。与此同时，r(5,5) 仍然是个未知数。

"很多人都想过 r(4,t)--90 多年来，这一直是个悬而未决的问题，"Verstraete 说。"但这并不是我研究的重点。每个人都知道这很难，每个人都想把它弄明白，所以除非你有新的想法，否则你不可能取得任何进展。"

虽然从表面上看，这似乎不是那种需要花费近百年时间才能弄明白的问题，但在图论中，外表是会骗人的。例如，在求解 r(5,5)时，如果你知道答案介于 40 和 50 之间，并且从图形上的 45 个点开始，那么将有 10234 个图形需要研究。

Verstraete解释说："因为这些数字很难找到，所以数学家们都在寻找估计值。这就是山姆和我最近的研究成果。'我们如何找到这些拉姆齐数字的最佳估计值，而不是准确答案？'"

Verstraete 第一次意识到 r(4,t) 是在《Erdös on Graphs》中： 这本书由加州大学圣地亚哥分校教授 Fan Chung 和已故的 Ron Graham 合著。这个问题是埃尔德斯提出的一个猜想，他向第一个能解决这个问题的人提供了 250 美元。我们可以想象，在 20 世纪 30 年代，250 美元的奖金可能会比2023年要"丰厚"得多。

虽然 Verstraete 在一段时间内一直惦记着 r(4,t)，但直到大约四年前，在与另一位数学家研究另一个问题时，他才在伪随机图方面取得了突破性进展，从而走上了解决拉姆齐之谜的道路。

2019 年，Verstraete 和那位数学家 Dhruv Mubayi 解决了 r(3,t)，但也仅此而已。直到他与具有有限几何背景的马修斯合作，解决下一个问题的梦想才开始看起来有可能成为现实。

"结果证明，我们需要的伪随机图可以在有限几何中找到，"Verstraete 说。"山姆是最合适的人选，他可以帮助我们构建我们所需要的东西。我们花了将近一年的时间，终于找到了r(4,t)的解： 从根本上说，如果要举办一个总是有 4 个相互认识的人或 t 个相互不认识的人参加的派对，那么大约需要 t3 个人参加。(因为不是精确的 3，所以是近似值）。"

Verstraete 说："我们真的花了很多年才解决这个问题。"有很多次我们都被卡住了，不知道我们是否能解决它。但无论花多长时间，我们都不应该放弃。"

数学家们没有透露r(5,5)现在是否已经出现在白板上，因为他们在此期间要等待他们的研究通过同行评审和验收。

"如果你发现问题很难，而且卡住了，那就说明这是一个好问题，好问题会反击。你不能指望它自己就显现出来。"他补充说："我接到 Fan 的电话，说她欠我 250 美元。"

遗憾的是，遥远的那笔1930 年代的"找人费"没有进行通货膨胀调整。

这项研究正在《数学年鉴》（Annals of Mathematics）杂志上接受评审。