以下文章来源于原理 ，作者佐佑
3月16日，一组数学家在论文预印网站上提交了一篇论文，表示他们在数学领域的一个最棘手的组合学问题上，取得了重大突破！这个问题涉及到拉姆齐数。
单色团问题
拉姆齐数是一个看似简单的概念，但与它有关的问题却异常困难。上世纪20年代，英国数学家弗兰克·拉姆齐（Frank Ramsey）最早提出拉姆齐数的概念，这个概念与单色团有关。
我们可以通过一个实例来直观地理解拉姆齐数和单色团。
将一个有着5个顶点的图的每个点都用线段两两相连，那么我们会发现，用10条线段就可以完成这一步，得到一个由这5个顶点形成的完全图。接着，将每条边涂成绿色或橙色两种颜色。
对于由5个顶点连接而成的完全图来说，用两种不同颜色为其边着色，是有可能避免出现3个顶点由相同颜色的边连接而成的情况的。（图/原理）
现在，问题来了，我们是否可以避免出现3个顶点是用相同颜色的边连接而成的吗？对于有着5个顶点的完全图来说，这个问题的答案是肯定的。
接下来，我们将5个顶点增加到6个顶点。同样地，我们用15条边让这6个顶点两两相连，形成完全图，并同样也给这15条边分别涂上绿色或橙色。这时，你会发现无论采用何种方法，都不可避免地会得到3个被相同颜色的边相互连接的点。
对于由6个顶点连接而成的完全图来说，用两种不同颜色为其边着色，必然会出现3个顶点由相同颜色的边连接而成的情况。（图/原理）
这些被相同颜色相连的点，就是单色团。它表示，对于颜色数量为2、大小为3的单色团来说，拉姆齐数为6。它意味着你需要一个至少包含6个顶点的完全图，才能保证这样一个单色团存在。
5的拉姆齐数是多少？
其实，这个问题有一个更耳熟能详的表达方式，那就是所谓的派对问题：想象一个有R个人聚在一起的派对，你要寻找一组大小为k的人，这组人要么认识派对上的所有人，要么对派对上的所有人都陌生。那么，对于给定的k，保证满足该条件的最小R(k)是多少？
以刚才的6(3)为例，它意味着派对上至少要有6个人，才能确保有3个人是互相认识的，或有3个人是完全陌生的。4的拉姆齐数为18，即18(4)，它意味着若要确保一个派对中有4个人是相互认识的，或4个人是完全陌生的，就需要将派对的人数扩大到18。
那么，要确保一个派对上有5个人是互相认识的，或5个人是完全陌生的，需要多少人？换句话说，5的拉姆齐数是多少？这个看似简单的问题，难倒了所有数学家。目前，数学家只知道，R(5)必须在43到48之间。
上界与下界
随着单色团的数字增大，拉姆齐数的计算变得越来越复杂。著名数学家保罗·埃尔德（Paul Erdös）曾经说，如果外星人登陆地球，要人类给出5的精确的拉姆齐数，否则就会毁灭这颗星球，那么人类应该集中所有的计算力来寻找这个问题的答案；但如果他们问的是6的拉姆齐数，那人类就做好准备应战吧！
的确，在绝大部分情况下，数学家无法直接计算拉姆齐数，只能给出一个可能的取值范围，确保一个任意大小的团的拉姆齐数在某个上界和下界之间。这种通过计算思路最早是由埃尔德和乔治·塞克勒斯（George Szekeres）于上世纪30年代最先提出的。
1935年，埃尔德计算出，对给定数字k来说，它的拉姆齐数的上界是4k。1947年，他又计算出了拉姆齐数的下界，即(√2)k。
然而，上界与下界之间有着很大的差距，它们离最优解有着很大的距离。比如对于k=4来说，上界4⁴=256，而我们知道其实18就已经够了。因此几十年来，研究人员一直试图缩小这个范围。
一小步？一大步！
在新提交的论文中，四名数学家开发一种新的算法。利用这种算法，数学家成功地用3.993k取代了4k！
看到这里，你是不是露出了满脸问号？“这，有区别吗？！”或许你正这样想。然而，是的，这是一次非常值得纪念的突破！这一指数级的改善，是自1935年以来，数学家在上界上迈出的第一步。
拉姆齐数在现实世界中没有特定的应用，它们属于纯数领域的课题。但对它们的研究已经对现实世界产生了不可估量的影响。例如，在20世纪80年代，数学家用一个被称为准随机性的概念来探索拉姆齐理论。现在，准随机性出现在计算机科学中的方方面面。研究人员表示，他们将继续在现有的基础上进一步探索拉姆齐数的上界。他们相信，3.993将不会是终点。
转自：“蔻享学术”微信公众号
如有侵权，请联系本站删除！
