困扰了科学家将近一个世纪的数学难题，两位数学家终于解决了

诸平

Fig. 1 Jacques Verstraete and Sam Mattheus, researchers at the University of California, San Diego, have made a significant breakthrough in Ramsey theory by solving the r(4,t) problem, a challenge that has eluded mathematicians for decades.

Fig. 2 Ramsey problems, such as r(4,5) are simple to state, but as shown in this graph, the possible solutions are nearly endless, making them very difficult to solve. Credit: Jacques Verstraete

Fig. 3 Fan Chung and Ron Graham. Erdös on graphs: his legacy of unsolved problems. A. K. Peters, Ltd, January 1998. pp. 142. Published online by Cambridge University Press:  01 August 2016 

据美国加州大学圣地亚哥分校（University of California - San Diego简称UCSD, San Diego, La Jolla, CA, USA）2024年4月11日提供的消息，加州大学圣地亚哥分校（UCSD）的数学家与比利时布鲁塞尔自由大学(Vrije Universiteit Brussel, Brussels, Belgium) 的数学家合作，发现了拉姆齐数（Ramsey numbers）背后的秘密。这个数学难题困扰了科学家将近一个世纪，两位数学家终于解决了它（This Math Problem Stumped Scientists for Almost a Century – Two Mathematicians Have Finally Solved It）。

我们都有过这样的经历:盯着数学题看，题目似乎不可能解决。如果找到一个问题的解决方案需要花费将近一个世纪的时间呢?对于涉猎拉姆齐理论（Ramsey theory）的数学家来说，情况就是如此。事实上，自20世纪30年代以来，在解决拉姆齐问题（Ramsey problems）方面几乎没有取得任何进展。

现在，UCSD的研究人员雅克·佛斯特拉（Jacques Verstraete）和萨姆·马特乌斯（Sam Mattheus）已经找到了r(4, t)的答案，这个长期存在的拉姆齐问题困扰了数学界几十年。

拉姆齐问题到底是什么？（What was Ramsey’s problem, anyway?）

用数学术语来说，图就是一系列的点和点之间的线。拉姆齐理论认为，如果图足够大，你一定能在图中找到某种顺序，要么是一组点之间没有线，要么是一组点之间有所有可能的线，这些集合被称为“团”（“cliques”）。它被写成r(s, t)，其中s是有直线的点，t是没有直线的点。

对于我们这些不研究图论的人来说，最著名的拉姆齐问题r(3, 3)有时被称为关于“朋友和陌生人的定理”（“the theorem on friends and strangers”），并通过一个聚会来解释:在一个6人的小组中，你会发现至少有3个人彼此都认识，或者3个人彼此都不认识。故r(3, 3)的答案是6。

雅克·佛斯特拉说：“这是一个自然的事实，一个绝对的真理。不管情况如何，也不管你选择哪6个人，你会发现3个人都彼此认识，或者3个人都互不认识。你也许能找到更多，但你可以保证至少有3个人在一个或另一个团内。”

数学家发现r(3, 3) = 6之后发生了什么?自然，他们想知道r(4, 4)， r(5, 5)和r(4, t)其中不连接的点的数量是可变的。r(4, 4)的解是18，它是用保罗·埃德斯（Paul Erdös）和乔治·塞凯赖什（George Szekeres）在20世纪30年代创造的一个定理证明的。目前，r(5, 5)仍然是未知的。

好的问题会反击（A good problem fights back）

为什么这么简单的陈述就这么难解决?事实证明，它比看起来要复杂得多。假设你知道r(5, 5)的解在40-50之间。如果你从45个点开始，就会有超过10²³⁴个图形需要考虑!

雅克·佛斯特拉解释说：“因为这些数字是出了名的难以找到，数学家们寻找的是估计。这就是萨姆·马特乌斯和我在最近的工作中所取得的成就。我们如何找到拉姆齐数的最佳估计，而不是确切的答案? ”相关研究结果于2024年3月5日已经在《数学年鉴》（Annals of Mathematics）杂志网站发表——Sam Mattheus, Jacques Verstraete. The asymptotics of r(4,t). Annals of Mathematics, 2024,198(2): 819-941. DOI: 10.4007/annals.2024.199.2.8. Published online: 5 March 2024. https://annals.math.princeton.edu/2024/199-2/p08

数学专业的学生很早就学会了拉姆齐问题，所以r(4, t)在雅克·佛斯特拉的大部分职业生涯中一直是他关注的对象。事实上，他第一次看到这个问题是在《埃德斯在图上的问题和传奇》（Erdös on Graphs: His Legacy of Unsolved Problems）一书中，此书由加州大学圣地亚哥分校的两位教授，金芳蓉（英文名：Fan Chung Graham, 学术论文所用的英文名：Fan Chung)和已故的葛立恒(Ron Graham / Ronald Lewis Graham，31 October 1935 - 6 July 2020 )合著的（Fig. 3）。这个问题是来自保罗·埃德斯的一个猜想，他们将为第一个能解决这个问题的人支付250美元（$250）的奖金。

雅克·佛斯特拉说:“很多人都认为r(4, t)是一个90多年来一直存在的开放性问题。但这并不是我研究的重点。每个人都知道这很难，每个人都试图弄清楚，所以除非你有一个新的想法，否则你不可能取得任何进展。”

大约4年前，雅克·佛斯特拉和美国伊利诺斯大学芝加哥分校（University of Illinois-Chicago）的数学家杜茹瓦·穆巴里（Dhruv Mubayi）一起研究另一个拉姆齐问题。他们一起发现，伪随机图（pseudorandom graphs）可以推进这些老问题的现有知识。

1937年，保罗·埃德斯发现使用随机图可以给出拉姆齐问题很好的下界。雅克·佛斯特拉和杜茹瓦·穆巴里发现，从伪随机图中抽样通常比随机图给出更好的拉姆齐数边界。这些可能答案的上限和下限收紧了他们可以做出的估计范围。换句话说，他们越来越接近真相了。

2019年，令数学界高兴的是，雅克·佛斯特拉和杜茹瓦·穆巴里使用伪随机图来求解r(3, t)。然而，雅克·佛斯特拉努力构建一个可以帮助求解r(4, t)的伪随机图。

他开始涉足组合学（combinatorics）之外的不同数学领域，包括有限几何（finite geometry）、代数（algebra）和概率论（probability）。最终，他与萨姆·马特乌斯合作，萨姆·马特乌斯是他小组里的博士后学者，他具有有限几何方面的背景知识。

雅克·佛斯特拉说：“事实证明，我们需要的伪随机图可以在有限几何中找到。萨姆·马特乌斯是一个理想之人来帮助我们建立我们所需要的。”

一旦他们有了伪随机图，他们仍然需要解决一些数学问题。这花了将近一年的时间，但最终，他们意识到他们有了一个解决方案:r(4, t)接近于t的三次函数。如果你想要一个聚会，总是有4个人彼此都认识，或者t个人彼此都不认识，你需要大约t³人在场。这里需要说明，因为，记住，这是一个估计，而不是一个确切的答案。但是t³已非常接近确切的答案了。

这些发现目前正在接受《数学年鉴》（Annals of Mathematics）的审查。

雅克·佛斯特拉说:“我们确实花了好几年才解决这个问题。有很多次我们被困住了，想知道我们到底能不能解决这个问题。但是一个人不应该放弃，不管需要多长时间。”

雅克·佛斯特拉强调毅力的重要性，这也是他经常提醒学生的一点。“如果你发现这个问题很难，你被卡住了，那就意味着这是一个好问题。金芳蓉说，好的问题会反击。你不能指望它自己就会显露出来。

雅克·佛斯特拉知道这种顽强的决心会得到很好的回报:“我接到金芳蓉的电话，说她欠我250美元。”

上述介绍，仅供参考。欲了解更多信息，敬请注意浏览原文或者相关报道。

Abstract

For integers s,t ≥ 2, the Ramsey number r(s, t) denotes the minimum n such that every n-vertex graph contains a clique of order s or an independent set of order t. In this paper we prove

r(4, t) = Ω{t³ / (log⁴ t)}$    as t →∞,

which determines r(4, t) up to a factor of order log² t, and solves a  conjecture of Erdős.