【原】小乐数学科普：两位数学家的拉姆齐数r(4, t)的渐进公式终于正式发表在数学顶刊，宣布拉姆齐理论90年来的重大进展

zzllrr小乐 2024-04-04 发布于江苏

展开全文

两位数学家的研究结果《The asymptotics of r(4,t)》于2024年3月正式发表在著名的数学顶刊之一：普林斯顿《数学年鉴》（Annals of Mathematics）上，正式宣告这一90多年的难题取得重大进展。

作者：Manon Bischoff 2024-4-4

译者：zzllrr小乐（数学科普公众号）2024-4-4

图源：Simon Fraser University

正如弗兰克·拉姆齐在近100年前所指出的那样，宇宙比我们想象的要有序得多。现在，专家们已经把这个隐藏的秩序弄得更清晰了。

图源：Simon Fraser University

“完全的混乱不存在”。数学家弗兰克·拉姆齐（Frank Ramsey，1903 - 1930）在1920年代提出了这一观点，这一发现震惊了科学界。当时他研究了元素彼此之间具有一定关系的量，并发现，当这个数量达到一定程度时，必然会导致某种秩序。究竟有多少数量是非常难以计算的。但是现在，90年后的今天，加州大学圣地亚哥分校的数学家Jacques Verstraete（雅克·维斯特拉特，下图左）和Sam Mattheus（山姆·马修斯，下图右）在对这些量的估计上取得了重大进展。（参阅小乐数学科普：数学家发现预测图结构的新方法以及小乐数学科普：新数学证明显示图的结构何时涌现——译自量子杂志Quanta Magazine）

图源：Quanta Magazine

他们的研究结果《The asymptotics of r(4,t)》于2024年3月发表在著名的普林斯顿《数学年鉴》(Annals of Mathematics)上 http://dx./10.4007/annals.2024.199.2.8 或 https:///abs/2306.04007。

拉姆齐理论的思想可以用聚会上的动力学来说明。拉姆齐意识到，一个有六个客人的聚会不可避免地会有至少三个人完全陌生，或者每个人都已经认识对方。如果只安排一个五人的聚会，那就不会如此了。这种秩序（熟人或陌生人的三人组合）只有在大型活动时才会出现。

为了形象化这一点，数学家们使用网络（称为图graph，示例如上图）。这些人被表示为点，每个点都通过边与其他点连接。边表征人与人之间的关系。例如，如果两个人已经认识，可以将边涂成蓝色，而如果他们彼此陌生，则涂成红色。现在人们可能想知道，在n个点时，红色和蓝色边必然形成什么样的单色结构。在上面的聚会示例中，对于n=6，总是有3个由三条红色边或三条蓝色边连接的点，因此总是有一个单色三角形。

具有6个节点及红色边和蓝色边的各种完全图

图源：wikipedia / Theorem on friends and strangers

n点的最小数目必须包含一个只由s条红边或t条蓝边构成的结构，这是用“拉姆齐数”r(s, t)来确定的。

目前为止，我们所知的拉姆齐数很少。聚会示例给出了r(3, 3)= 6：因此至少需要六个点才能不可避免地出现蓝色或红色三角形。另一个例子是r(4, 4)=18：你必须邀请至少18个客人，才能保证有4个朋友或4个陌生人组成的聚会。在一个图中，这是通过一个具有对角线的同色矩形来实现的。不知道r(5, 5)的大小是多少。然而，专家们已经能够缩小结果：现在我们知道43 ≤ r(5, 5)≤ 49。

拉姆齐数r(4, 5)=25

43 ≤ r(5, 5)≤ 49

r(3, 3)= 6，r(3, 4)=9，r(4, 4)=18

图源：Jacques Verstraete / UC San Diego

超越任何想象力

困难的原因与可以为网络着色的方式的巨大多样性有关。例如，在6人派对问题中，总共有组合数C₆² = 15条边。这些组合中的每一种都可以是红色或蓝色，也就是说，有2¹⁵ = 32768种不同的颜色可供选择。因此，我们必须对所有32768个不同染色网络进行检查，以确定每个网络是否形成了一个相同颜色的三角形。拉姆齐以一种不同的方式解决了这个问题（有关更多细节，请参阅“数学的美妙世界”专栏）。然而，当涉及到更多点的网络时，拉姆齐的方法也失败了。90年来，这一领域几乎没有进展。

现在Verstraete和Mattheus找到了一个r(4, t)的公式。它表示至少需要多少位客人，以便在聚会上，四个人彼此完全陌生，或者彼此都认识。为了解决这个问题，两位数学家使用了随机图，这有助于缩小拉姆齐数。例如，如果你创建一个随机着色网络，其中有n个点不包含所需的结构（例如，单色三角形或对角线矩形），那么你要查找的拉姆齐数必须大于n。

图源：UC San Diego

“有很多时候，我们都没有取得进展，想知道我们能否解决它。”

Jacques Verstraete——数学家

生成一个合适的随机网络，并针对任意数量的n个点进行分析，结果是极其困难的。“我们花了很多年来解决这个问题，”Verstraete说。“有很多时候，我们都没有取得进展，想知道我们能否解决它。”永远不要放弃，不管需要多长时间。这项研究证明，r(4, t)所需点的数量随着t³ 的增加而增加。因此，如果你想在聚会上见到四个熟人或陌生人的小团体，你必须邀请大约t³个客人。

两位数学家不仅对他们的发现感到高兴，该结果发表在该领域最负盛名的期刊之一。著名数学家保罗·埃尔德什（Paul Erdős）于1996年去世，他生前喜欢悬赏难题，曾将解决r(4, t)猜想的奖金定为：250美元（托付给数学家葛立恒Ronald Graham，1935 - 2020）。加州大学圣地亚哥分校教授金芳蓉（Fan Chung Graham，数学家葛立恒遗孀）已经向Verstraete保证，他将获得奖金。