花了近一个世纪才解决的数学问题

发布时间：2024-04-25 15:55:20 栏目：精选百科

导读 我们都经历过这样的情况：盯着数学考试，发现一个似乎无法解决的问题。如果找到问题的解决方案花了近一个世纪怎么办?对于涉足拉姆齐理论的...

我们都经历过这样的情况：盯着数学考试，发现一个似乎无法解决的问题。如果找到问题的解决方案花了近一个世纪怎么办?对于涉足拉姆齐理论的数学家来说，情况确实如此。事实上，自 20 世纪 30 年代以来，解决拉姆齐问题的进展甚微。



现在，加州大学圣地亚哥分校的研究人员 Jacques Verstraete 和 Sam Mattheus 找到了 r(4,t) 的答案，这是一个困扰数学界数十年的长期拉姆齐问题。

拉姆齐的问题到底是什么?

用数学术语来说，图形是一系列点和这些点之间的线。拉姆齐理论表明，如果图足够大，您一定会在其中找到某种顺序 - 要么是一组之间没有直线的点 ，要么是 一组之间有所有可能的直线的点(这些点集称为“派系”)。这可以写为 r(s,t)，其中 s 是有直线的点， t 是没有直线的点。

对于我们这些不研究图论的人来说，最著名的拉姆齐问题 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 个点开始，则需要考虑的图表将超过 10 234 个 !

“因为这些数字非常难以找到，所以数学家们会寻找估计值，”维斯特拉特解释道。 “这就是萨姆和我在最近的工作中取得的成就。我们如何找到拉姆齐数字可能的最佳估计而不是确切的答案?”

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

“许多人都考虑过 r(4,t)——90 多年来它一直是一个悬而未决的问题，”Verstraete 说。 “但这并不是我研究的前沿内容。每个人都知道这很难，每个人都试图解决它，所以除非你有新的想法，否则你不可能取得任何进展。”

大约四年前，Verstraete 与伊利诺伊大学芝加哥分校的数学家 Dhruv Mubayi 一起研究另一个拉姆齐问题。他们一起发现伪随机图可以增进对这些老问题的当前认识。

1937 年，Erdös 发现使用随机图可以给出拉姆齐问题的良好下界。 Verstraete 和 Mubayi 发现，从 伪随机图采样通常比随机图给出更好的拉姆齐数界限。这些界限——可能答案的上限和下限——收紧了他们可以做出的估计范围。换句话说，他们离真相越来越近了。

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

他开始涉足组合数学之外的不同数学领域，包括有限几何、代数和概率。最终，他与团队中的博士后学者马修斯联手，马修斯的背景是有限几何。

“事实证明，我们需要的伪随机图可以在有限几何中找到，”Verstraete 说。 “Sam 是帮助我们打造所需产品的最佳人选。”

一旦他们有了伪随机图，他们仍然需要解决一些数学问题。花了将近一年的时间，但最终他们意识到他们有一个解决方案： r(4,t) 接近 t的三次函数。如果您想要一个聚会中总是有四个人都互相认识或 有 t 个 互相不认识的人，那么您大约需要 t 3 个人在场。有一个小星号(实际上是 o)，因为请记住，这是一个估计值，而不是确切的答案。但 t 3 非常接近确切答案。

该研究结果目前正在接受 《数学年鉴》的审查。

“我们确实花了很多年的时间才解决这个问题，”Verstraete 说道。 “很多时候我们都陷入困境，想知道是否能够解决这个问题。但无论需要多长时间，一个人都不应该放弃。”

Verstraete 强调坚持不懈的重要性——他经常提醒学生这一点。 “如果你发现这个问题很难并且被困住了，那就说明这是一个好问题。范仲说好问题还击。你不能指望它会自行显现。”

Verstraete 知道这种顽强的决心会得到很好的回报：“我接到范的电话，说她欠我 250 美元。”