数学家揭开拉姆齐数的谜团，用新工具展现秩序在随机中的形成。

数学家近日在加拿大聚集，讨论一个受2023年突破启发的拉姆齐数猜想，该猜想由Paul Erdős提出。两位研究人员结合新方法，在这一长达四十年未解的难题上取得进展。这不仅推动了数学在随机系统中的秩序形成研究，还对计算机科学有重要启发。

“论文一发表，我们就意识到要组织这样的研讨会了，”荷兰代尔夫特理工大学数学助理教授Anurag Bishnoi说。

由布鲁塞尔自由大学的Sam Mattheus博士后研究员和加州大学圣地亚哥分校的数学教授Jacques Verstraete所解决的这一猜想，源于英国逻辑学家Frank 拉姆齐近一个世纪前的证明：在六人组成的聚会中，可以保证三人彼此认识或彼此陌生。

这一最初证明基于在六个节点之间以两种颜色(代表认识与陌生)画线的可能性。无论如何着色，都将出现至少一个红色或蓝色三角形。然而，当减少到五个节点时，这一必然性消失。

随着图中节点数的增加，出现了更大的结构。在随机整数序列中也能看到类似模式。荷兰数学家Bartel Leendert van der Waerden证明，随机整数列表中可以出现算术模式。确定这些结构在随机模式中必然形成的点，成为拉姆齐理论的核心。然而，要找到特定模式出现的确切阈值极为困难。

例如，要形成红或蓝五边形所需的节点数r(5,5)尚不明确，但已知其位于43到48之间。Erdős在上世纪90年代曾预言，r(6,6)在计算上几乎无法实现。

拉姆齐理论的研究者仍在努力缩小个别问题的界限。这不仅是为了知道确切值，更在于探索新颖的证明方法。

“得知某一van der Waerden或拉姆齐数的具体值并不会大大改变我们对拉姆齐理论的理解，”加拿大西蒙菲莎大学数学教授Veselin Jungić说，“确定这些数值本身就是极具挑战的问题，吸引着数学家和计算科学家。”

上世纪Erdős和其他数学家提出的拉姆齐理论猜想，为数学家提供了许多挑战。Mattheus和Verstraete此次突破的是一种称为“非对角线”拉姆齐数的问题。

相关：拉姆齐数
拉姆齐数(Ramsey number)是图论的重要函数之一，它是一个以两个正整数作为变量的函数。设m和n为正整数。所谓拉姆齐数，常用r(m ,n)表示，是指符合一定条件的p(图的阶数)的最小值。对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；拉姆齐证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。

已知的拉姆齐数非常少，保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”

本文译自 ACM，由 BALI 编辑发布。

PREV : 世界上最古老的树？Pando森林的进化密码
NEXT : “上下铺猜想”被推翻：直觉与数学的对决