困扰世界近一个世纪的数学难题：拉姆齐问题已被破解
困扰世界近一个世纪的数学难题：拉姆齐问题已被破解拉姆齐问题，如r(4,5)，陈述起来很简单，但如图所示，可能的解几乎是无穷无尽的图/JacquesVerstraete/加州大学圣地亚哥分校拉姆齐定理（英语：Ramsey'stheorem），又称拉姆齐二染色定理，断言对任意正整数k和l，若一个聚会的人数n足够大，则无论相识关系如何，必定有k个人相识或l个人互不相识。给定k,l时，保证前述结论的最小n值称为拉姆齐数R(k,l)，其值取决于k,l。用图论术语复述：若将足够大的完全图各边染红蓝两色，则不论如何染，必定有红色的k阶完全图或蓝色的l阶完全图。拉姆齐定理是组合数学的重要结论，以弗兰克·普伦普顿·拉姆齐命名。他在1930年论文《论形式逻辑的一个问题》证明此定理最初的版本，开创现称拉姆齐理论的组合理论分支。拉姆齐理论的主题是从“无序”寻找“规律”，希望找出某数学结构中，存在规律子结构的一般条件。在拉姆齐定理的图论表述中，此“规律子结构”是同色集（monochromaticset），即顶点集的子集，其中各边皆染成同一颜色。拉姆齐理论是以英国数学家和哲学家弗兰克-P-拉姆齐（FrankP.Ramsey）的名字命名的数字游戏的一个分支，非常复杂。在这个图论数学的角落里，最著名的问题是r(3,3)，通常被称为朋友和陌生人定理，它假设在一个由六个人组成的小组中，你会发现至少有三个人互相认识，或者有三个人互相不认识。显然，r(3,3)的答案是6。"这是自然界的事实，是绝对真理。不管情况如何，也不管你选择哪六个人，你都能找到三个互相认识的人，或者三个互相不认识的人。也许你能找到更多的人，但你能保证至少有三个人在一个小集团或另一个小集团中。"一旦找到了r(3,3)，数学家们就开始寻找后续问题的答案：r(4,4)、r(5,5)和r(4,t)，在这些问题中，不相连的点的数量各不相同。数学家们发现r(3,3)的答案是6之后，又发生了什么呢？自然，他们想知道r(4,4)、r(5,5)和r(4,t)，其中不相连的点的数目是可变的。上世纪，埃尔德什和乔治-塞克雷斯发现r(4,4)的答案是18。与此同时，r(5,5)仍然是个未知数。"很多人都想过r(4,t)--90多年来，这一直是个悬而未决的问题，"Verstraete说。"但这并不是我研究的重点。每个人都知道这很难，每个人都想把它弄明白，所以除非你有新的想法，否则你不可能取得任何进展。"虽然从表面上看，这似乎不是那种需要花费近百年时间才能弄明白的问题，但在图论中，外表是会骗人的。例如，在求解r(5,5)时，如果你知道答案介于40和50之间，并且从图形上的45个点开始，那么将有10234个图形需要研究。Verstraete解释说："因为这些数字很难找到，所以数学家们都在寻找估计值。这就是山姆和我最近的研究成果。'我们如何找到这些拉姆齐数字的最佳估计值，而不是准确答案？'"Verstraete第一次意识到r(4,t)是在《ErdösonGraphs》中：这本书由加州大学圣地亚哥分校教授FanChung和已故的RonGraham合著。这个问题是埃尔德斯提出的一个猜想，他向第一个能解决这个问题的人提供了250美元。我们可以想象，在20世纪30年代，250美元的奖金可能会比2023年要"丰厚"得多。虽然Verstraete在一段时间内一直惦记着r(4,t)，但直到大约四年前，在与另一位数学家研究另一个问题时，他才在伪随机图方面取得了突破性进展，从而走上了解决拉姆齐之谜的道路。2019年，Verstraete和那位数学家DhruvMubayi解决了r(3,t)，但也仅此而已。直到他与具有有限几何背景的马修斯合作，解决下一个问题的梦想才开始看起来有可能成为现实。"结果证明，我们需要的伪随机图可以在有限几何中找到，"Verstraete说。"山姆是最合适的人选，他可以帮助我们构建我们所需要的东西。我们花了将近一年的时间，终于找到了r(4,t)的解：从根本上说，如果要举办一个总是有4个相互认识的人或t个相互不认识的人参加的派对，那么大约需要t3个人参加。(因为不是精确的3，所以是近似值）。"Verstraete说："我们真的花了很多年才解决这个问题。"有很多次我们都被卡住了，不知道我们是否能解决它。但无论花多长时间，我们都不应该放弃。"数学家们没有透露r(5,5)现在是否已经出现在白板上，因为他们在此期间要等待他们的研究通过同行评审和验收。"如果你发现问题很难，而且卡住了，那就说明这是一个好问题，好问题会反击。你不能指望它自己就显现出来。"他补充说："我接到Fan的电话，说她欠我250美元。"遗憾的是，遥远的那笔1930年代的"找人费"没有进行通货膨胀调整。这项研究正在《数学年鉴》（AnnalsofMathematics）杂志上接受评审。...PC版：https://www.cnbeta.com.tw/articles/soft/1394101.htm手机版：https://m.cnbeta.com.tw/view/1394101.htm
