加州大学圣地亚哥分校的研究人员Jacques Verstraete和Sam Mattheus通过解决r(4,t)问题，在拉姆齐理论中取得了重大突破，这个问题几十年来一直困扰着数学家。
我们都有过这样的经历:盯着数学题看，题目似乎不可能解决。如果找到一个问题的解决方案需要花费将近一个世纪的时间呢?对于涉猎拉姆齐理论的数学家来说，情况就是如此。事实上，自20世纪30年代以来，在解决拉姆齐问题方面几乎没有取得任何进展。
现在，加州大学圣地亚哥分校的研究人员Jacques Verstraete和Sam matthews已经找到了r(4,t)的答案，这个长期存在的拉姆齐问题困扰了数学界几十年。
拉姆齐到底有什么问题?
用数学术语来说，图就是一系列的点和点之间的线。拉姆齐理论认为，如果图足够大，你肯定能在图中找到某种顺序——要么是一组点之间没有线，要么是一组点之间有所有可能的线(这些集合被称为“团”)。它被写成r(s,t)其中s是有直线的点t是没有直线的点。
对于我们这些不研究图论的人来说，最著名的拉姆齐问题r(3,3)有时被称为“关于朋友和陌生人的定理”，它是通过一个聚会来解释的:在一个六人的小组中，你会发现至少有三个人彼此都认识，或者三个人彼此都不认识。r(3,3)的答案是6。
Ramsey问题，如r(4,5)，表述起来很简单，但如图所示，可能的解决方案几乎是无穷无尽的，这使得它们很难解决。来源:Jacques Verstraete
“这是自然的事实，绝对的真理，”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解释说:“因为这些数字很难找到，所以数学家们寻找的是估计。”“这就是山姆和我在最近的工作中所取得的成就。我们如何找到不是确切的答案，而是对这些拉姆齐数字的最佳估计?”
数学学生很早就学会了拉姆齐问题，所以r(4,t)在Verstraete的大部分职业生涯中一直是他关注的对象。事实上，他第一次看到这个问题是在Erd?s上的“图表:他未解决问题的遗产”上，由加州大学圣地亚哥分校的两位教授，范·钟和已故的罗恩·格雷厄姆撰写。这个问题是来自Erd?s的一个猜想，他给第一个能解决这个问题的人250美元。
Verstraete说:“很多人都考虑过r(4,t)，这是一个90多年来一直悬而未决的问题。”“但这并不是我研究的重点。每个人都知道这很难，每个人都试图弄清楚，所以除非你有一个新的想法，否则你不可能取得任何进展。”
大约四年前，Verstraete和伊利诺斯-芝加哥大学的数学家Dhruv Mubayi一起研究另一个拉姆齐问题。他们一起发现，伪随机图可以推进这些老问题的现有知识。
1937年，Erd?s发现使用随机图可以给出拉姆齐问题很好的下界。Verstraete和Mubayi发现，从伪随机图中抽样通常比随机图给出更好的拉姆齐数边界。这些界限——可能答案的上限和下限——收紧了他们可以做出的估计范围。换句话说，他们越来越接近真相了。
2019年，令数学界高兴的是，Verstraete和Mubayi使用伪随机图来求解r(3,t)。然而，Verstraete努力构建一个可以帮助求解r(4,t)的伪随机图。
他开始涉足组合学之外的不同数学领域，包括有限几何、代数和概率论。最终，他与马修斯合作，马修斯是他小组里的博士后学者，他的背景是有限几何。
“事实证明，我们需要的伪随机图可以在有限几何中找到，”Verstraete说。“山姆是一个完美的人，可以帮助我们建立我们所需要的东西。”
一旦他们有了伪随机图，他们仍然需要解决一些数学问题。这花了将近一年的时间，但最终，他们意识到他们有了一个解决方案:r(4,t)接近于t的三次函数。如果你想要一个聚会，总是有四个人彼此都认识，或者t个人彼此都不认识，你将需要大约t3人在场。这里有一个小星号(实际上是一个0)，因为，记住，这是一个估计，而不是一个确切的答案。但是t3非常接近确切的答案。
这些发现目前正在接受《数学年鉴》的审查。
Verstraete说:“我们确实花了很多年才解决这个问题。”“有很多次，我们陷入了困境，想知道我们是否能够解决这个问题。但一个人不应该放弃，不管需要多长时间。”
Verstraete强调毅力的重要性，这也是他经常提醒学生的一点。“如果你发现这个问题很难，你卡住了，那就意味着这是个好问题。范锺说，好的问题会反击。你不能指望它自己就会显露出来。”
Verstraete知道这种顽强的决心会得到回报:“我接到范的电话，说她欠我250美元。”
参考文献:《r(4,t)的渐近性》，Sam matthews和Jacques Verstraete, 2024年3月5日，《数学年鉴》。DOI: 10.4007 / annals.2024.199.2.8
