Ramsey问题，例如r(4，5)，很容易表述，但如图所示，可能的解几乎是无穷的，这使得它们很难解决。

我们都经历过这种情况：盯着一个数学测验，上面有一个似乎不可能解决的问题。如果找到一个问题的花费了将近一个世纪呢？对于涉足 Ramsey 理论的数学家来说，情况正是如此。事实上，自 20 世纪 30 年代以来，在解决 Ramsey 问题方面几乎没有取得什么进展。

现在，加州大学圣地亚哥分校的研究人员 Jacques Verstraete 和 Sam Mattheus 找到了 r(4,t) 的答案，这是一个长期存在的 Ramsey 问题，几十年来一直让数学界困惑不已。

Ramsey 的问题到底是什么？

在数学术语中，图是由一系列点和这些点之间的线组成的。Ramsey 理论表明，如果图足够大，那么你必定会在其中找到某种顺序——要么是一组点之间没有线，要么是一组点之间有所有可能的线(这些组被称为“团”)。这写成 r(s,t)，其中 s 是有线的点，t 是没有线的点。

对于我们这些不懂图论的人来说，最著名的 Ramsey 问题 r(3,3) 有时被称为“朋友和陌生人定理”，并通过聚会的方式解释：在一群六人中，你会发现至少有三个人彼此相识或三个人彼此不认识。r(3,3) 的答案是六。

Verstraete 说：“这是自然界的事实，是绝对真理。” “无论情况如何，无论你选择哪六个人——你都会找到三个人彼此相识或三个人彼此不认识。你可能能够找到更多，但你可以保证一个团或另一个团中至少会有三个人。”

数学家发现 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 个点开始，那么将有超过 10234 个图需要考虑。

Verstraete 解释说：“因为这些数字出了名的难以找到，所以数学家们会寻找估计值。” “这就是我和山姆在最近的工作中取得的成果。我们如何找到不是确切的答案，而是对这些 Ramsey 数可能是什么的最佳估计？”

数学专业的学生很早就学习了 Ramsey 问题，所以 r(4,t) 在 Verstraete 的职业生涯的大部分时间里一直受到关注。事实上，他第一次在印刷品中看到这个问题是在 Erdös on Graphs: His Legacy of Unsolved Problems 中，该书由加州大学圣地亚哥分校的两名教授Fan Chung和已故的Ron Graham编写。这个问题是 Erdös 的一个猜想，他向第一个能解决它的人提供了 250 美元。

Verstraete 说：“许多人考虑过 r(4,t)——它已经是一个 90 多年未解决的问题了。” “但这不是我研究的最前沿的东西。每个人都知道这很难，每个人都试图弄清楚，所以除非你有一个新的想法，否则你不太可能取得任何进展。”

大约四年前，Verstraete 与伊利诺伊大学芝加哥分校的数学家 Dhruv Mubayi 研究另一个 Ramsey 问题。他们一起发现，伪随机图可以推进这些老问题上的现有知识。

1937 年，Erdös 发现使用随机图可以对 Ramsey 问题给出良好的下界。Verstraete 和 Mubayi 发现，从伪随机图中采样通常比随机图对 Ramsey 数给出更好的界限。这些界限——可能答案的上下限——缩小了他们可以做出的估计范围。换句话说，他们正在接近真相。

2019 年，令数学界高兴的是，Verstraete 和 Mubayi 使用伪随机图求解了 r(3,t)。然而，Verstraete 努力构建一个可以帮助解决 r(4,t) 的伪随机图。

他开始从组合学之外的数学不同领域引入，包括有限几何、代数和概率。最终，他与 Mattheus 联手，Mattheus 是他小组中的一名博士后学者，背景是有限几何。

Verstraete 说：“事实证明，我们需要的伪随机图可以在有限几何中找到。” “山姆是完美的人选，可以参与进来，帮助我们构建我们所需要的。”

一旦他们建立了伪随机图，他们仍然必须解出几个数学难题。这花了一年多的时间，但最终他们意识到他们有了解决方案：r(4,t) 接近 t 的三次函数。如果你想参加一个聚会，总会有四个人彼此相识，或者 t 个人彼此不认识，你需要大约有 t³ 个人在场。有一个小花星号(实际上是一个 o)，因为，请记住，这是一个估计值，不是一个确切的答案。但 t³ 非常接近确切的答案。

研究结果目前正在《数学年鉴》上进行同行评审。可以在 arXiv 上查看预印本。

Verstraete 说：“我们确实花了好几年时间才解决这个问题。” “而且有很多次我们被困住了，想知道我们是否能够完全解决它。但无论花多长时间，你都永远不要放弃。”

Verstraete 强调了毅力的重要性——他经常提醒他的学生这一点。 “如果你发现这个问题很难，而且你被困住了，那就意味着这是一个好问题。范仲淹说过，一个好的问题会反击。你不能指望它只是自行显现。”

Verstraete 知道这种顽强的决心是值得的：“我接到范仲淹的电话，她说她欠我 250 美元。”

本文译自 phys.org，由 BALI 编辑发布。

PREV : 科学家们发现了一种新的触觉
NEXT : 高代谢是阿尔茨海默病的早期迹象