数学家解决长期存在的拉姆齐问题

加州大学圣地亚哥分校的两位数学家找到了 r(4,t) 的答案，这是一个困扰数学界数十年的长期拉姆齐问题。

拉姆齐理论是一个数学领域，其基础是这样的哲学：在任何足够大的结构中，都存在相对较大的均匀子结构。

该领域以弗兰克·普兰普顿·拉姆齐 (Frank Plumpton Ramsey) 的名字命名，但植根于数学的各个分支，包括逻辑、集合论、拓扑、几何和数论。

著名的成果包括导致费马模素数最后定理的舒尔定理、拉多的划分正则性、范德瓦尔登算术级数定理和谢拉定理，以及度量拉姆齐理论中关于欧几里得畸变的布尔根定理等等。

该领域已发展成为现代组合学研究的基石，研究的核心数量被称为拉姆齐数。

经典的说明性例子是这样的说法：在任何六个人中，至少有三个人都互相认识，或者至少有三个人互相不认识。

“用数学术语来说，图表是一系列点和这些点之间的线，”加州大学圣地亚哥分校数学家 Jacques Verstraete 和 Sam Mattheus 说。

“拉姆齐理论表明，如果图足够大，你就一定能在其中找到某种顺序——要么是一组之间没有直线的点，要么是一组之间有所有可能的直线的点(这些点是称为派系)”。

“这可以写成 r(s,t)，其中 s 是有直线的点，t 是没有直线的点。”

“对于我们这些不研究图论的人来说，最著名的拉姆齐问题 r(3,3) 有时被称为朋友和陌生人定理，并通过派对的方式进行解释：在群体中六个人中，你会发现至少三个人都互相认识，或者三个人都互相不认识。r(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) 仍然未知。

“为什么说起来如此简单的事情却很难解决?事实证明，事情比看起来更复杂。”研究人员说。

“假设您知道 r(5,5) 的解在 40-50 之间。如果您从 45 个点开始，则需要考虑的图表将超过 10,234 张!”

“因为这些数字非常难以找到，所以数学家们会寻找估计值。”

大约四年前，Verstraete 博士与伊利诺伊大学芝加哥分校数学家 Dhruv Mubayi 一起研究另一个拉姆齐问题。

他们一起发现伪随机图可以增进对这些老问题的当前认识。

1937 年，Paul Erdös 发现使用随机图可以给出拉姆齐问题的良好下界。

Verstraete 博士和 Mubayi 博士发现，从伪随机图中采样通常比随机图给出更好的拉姆齐数界限。

这些界限——可能答案的上限和下限——收紧了他们可以做出的估计范围。换句话说，他们离真相越来越近了。

2019 年，令数学界高兴的是，Verstraete 博士和 Mubayi 博士使用伪随机图来求解 r(3,t)。

然而，他们努力构建一个可以帮助求解 r(4,t) 的伪随机图。

Verstraete 博士开始涉足组合数学之外的不同数学领域，包括有限几何、代数和概率。

“事实证明，我们需要的伪随机图可以在有限几何中找到。萨姆是帮助我们构建我们所需要的东西的最佳人选，”Verstraete 博士说。

一旦他们有了伪随机图，他们仍然需要解决一些数学问题。

花了将近一年的时间，但最终他们意识到他们有一个解决方案：r(4,t) 接近 t 的三次函数。

如果您希望聚会中始终有 4 个彼此认识的人或 t 个彼此不认识的人，那么您大约需要 t3 个人在场。

有一个小星号(实际上是 o)，因为请记住，这是一个估计值，而不是确切的答案。但 t3 非常接近确切答案。

“我们确实花了很多年的时间才解决这个问题，”Verstraete 博士说。

“很多时候我们都陷入困境，想知道是否能够解决这个问题。”

“但无论需要多长时间，一个人都不应该放弃。”

该团队的论文将发表在《数学年鉴》杂志上。