一个著名数学问题的重大突破

作者: 佐佑

来源: 原理

发布日期: 2023-04-04 20:32:46

一组数学家在拉姆齐数问题上取得了重大突破,开发了一种新的算法,成功地将上界从4k降低到3.993k,这是自1935年以来的第一次显著改进。拉姆齐数是组合数学中的一个难题,涉及如何在给定的完全图中避免出现特定大小的单色团。这一研究虽然属于纯数学领域,但其理论可能对计算机科学中的准随机性概念产生影响。

3月16日,一组数学家在论文预印网站上提交了一篇论文,表示他们在数学领域的一个最棘手的组合学问题上,取得了重大突破!这个问题涉及到拉姆齐数。拉姆齐数是一个看似简单的概念,但与它有关的问题却异常困难。上世纪20年代,英国数学家弗兰克·拉姆齐最早提出拉姆齐数的概念,这个概念与单色团有关。

我们可以通过一个实例来直观地理解拉姆齐数和单色团。

将一个有着5个顶点的图的每个点都用线段两两相连,那么我们会发现,用10条线段就可以完成这一步,得到一个由这5个顶点形成的完全图。接着,将每条边涂成绿色或橙色两种颜色。对于由5个顶点连接而成的完全图来说,用两种不同颜色为其边着色,是有可能避免出现3个顶点由相同颜色的边连接而成的情况的。现在,问题来了,我们是否可以避免出现3个顶点是用相同颜色的边连接而成的吗?

对于有着5个顶点的完全图来说,这个问题的答案是肯定的。

接下来,我们将5个顶点增加到6个顶点。同样地,我们用15条边让这6个顶点两两相连,形成完全图,并同样也给这15条边分别涂上绿色或橙色。这时,你会发现无论如何采用何种方法,都不可避免地会得到3个被相同颜色的边相互连接的点。对于由6个顶点连接而成的完全图来说,用两种不同颜色为其边着色,必然会出现3个顶点由相同颜色的边连接而成的情况。

这些被相同颜色相连的点,就是单色团。它表示,对于颜色数量为2、大小为3的单色团来说,拉姆齐数为6。

其实,这个问题有一个更耳熟能详的表达方式,那就是所谓的派对问题:想象一个有R个人聚在一起的派对,你要寻找一组大小为k的人,这组人要么认识派对上的所有人,要么对派对上的所有人都陌生。那么,对于给定的k,保证满足该条件的最小R(k)是多少?

以刚才的6(3)为例,它意味着派对上至少要有6个人,才能确保有3个人是互相认识的,或有3个人是完全陌生的。4的拉姆齐数为18,即18(4),它意味着若要确保一个派对中有4个人是相互认识的,或4个人是完全陌生的,就需要将派对的人数扩大到18。

那么,要确保一个派对上有5个人是互相认识的,或5个人是完全陌生的,需要多少人?换句话说,5的拉姆齐数是多少?这个看似简单的问题,难倒了所有数学家。

目前,数学家只知道,R(5)必须在43到48之间。随着单色团的数字增大,拉姆齐数的计算变得越来越复杂。著名数学家保罗·埃尔德曾经说,如果外星人登陆地球,要人类给出5的精确的拉姆齐数,否则就会毁灭这颗星球,那么人类应该集中所有的计算力来寻找这个问题的答案;但如果他们问的是6的拉姆齐数,那人类就做好准备应战吧!

在新提交的论文中,四名数学家开发一种新的算法。利用这种算法,数学家成功地用3.993k取代了4k!看到这里,你是不是露出了满脸问号?“这,有区别吗?!”或许你正这样想。然而,是的,这是非常值得纪念的突破!这一指数级的改善,是自1935年以来,数学家在上界上迈出的第一步。拉姆齐数在现实世界中没有特定的应用,它们属于纯数领域的课题。但对它们的研究已经对现实世界产生了不可估量的影响。

UUID: bf696daa-9aee-4614-8afa-df977e9cc0f5

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/原理公众号-pdf2txt/2023年/原理_2023-04-04_一个著名数学问题的重大突破.txt

是否为广告: 否

处理费用: 0.0046 元