1. 首页
  2. 时报

数学界有重磅消息!林格尔猜想将被证明,60年难题被攻破? 基格尔德专属技能怎么学

点面结合构成了一个个图形,关于这些图我们可以想出各种问题,比如:如何让多个简单的小图副本完美地重构(覆盖)一张大图?

这就像你面对家里厨房的地板发问:我可以用商店中任意一种同尺寸的瓷砖完全覆盖整个地板吗?在现实生活中,不可能每一款瓷砖都适用于你家的厨房,一般来说必须组合不同形状的瓷砖(或者切割)才能覆盖整个地板。但是在特定的图形世界中,这个想法或许可以达成。

1963年,一位名叫格哈德·林格尔(Gerhard Ringel)的德国数学家提出了一个大胆的猜想:一些特定的图形总是可以被n个小图副本完美覆盖。对此,他指出:任给一棵具有 n 条边的树 T,都能在2n+1阶完全图K2n+1中找到不重合且同构于T的2n+1个子图(即2n+1个T副本可以被完美地填充到K2n+1中)

为了证明林格尔的猜想,人们发展与利用了多种数学工具,比如:概率方法、正则引理等,但似乎总有漏洞。

近日,苏黎世瑞士联邦技术学院的本尼·苏达科夫(Benny Sudakov)、伯明翰大学的理查德·蒙哥马利(Richard Montgomery)和伦敦伯克贝克大学的亚历克斯·波克洛夫斯基(Alexey Pokrovskiy)三名数学家发表的相关论文或许给证明这个困惑了人们将近60年的数学猜想带来了希望。

01 林格尔猜想是什么?完整图形和树图

发布这个猜想,林格尔提出了一些基本概念:首先,从大于3的任何奇数个点开始(这个数字必须是奇数才能使推测合理),在它们之间绘制边,以便每个点都与其他所有点相连,这样创建的图形称为完整图形。

一个拥有5个点的完整图形

接下来,我们看一下另一种类型的图。它可以是一条简单的路径;也可以有其他分支,当然我们还可以在分支上继续添加分支,只要它不包含任何闭环,就可以根据需要使图更复杂,我们把这种类型的图称为树。

简单或复杂的树图

林格尔猜想是关于完整图和树之间的关系。

他说:首先,想象一个包含2n+1个点的完整图形。然后思考使用n+1个点可以制作多少棵树,事实上可以做出很多种完全不同的树。

现在,选择其中一棵树并将其放置,以使树的每个边与完整图形中的边重合。然后,将同一棵树的另一个副本放在整个图形的不同部分上。

林格尔预测,假设你从正确的地方开始放置并持续这个动作,那么你将能够完美地复制出上面的完整图形。这意味着完整图形中的每个边都被树的每条边覆盖,且树的任何副本都不会相互重叠(如下图)。

完美复制

如何理解这个猜想呢?

当已知一个完整图,如果它的点数为n(大于3且为奇数),那么该图肯定可以被n个子图完美覆盖,且子图的形状为具有(n-1)/2条边的树图;反之,如果已知一个具有m条边的树图,那么用2m+1个该树图可以构成一个具有2m+1个点的完整图。

林格尔的猜想似乎适用于11、21、31个点的完整图形,但是随着点越来越多,完整图形逐渐复杂起来,这个猜想还成立吗?

这个范围虽然很广泛,但数学界有理由相信林格尔的猜想可能是正确的。最直接的理由是:具有2n+1个点的完整图形中的边数总是可以被具有n+1个点的树中的边数等分。

事实上,数学家们很快找到了另一条证据,表明该猜想至少是可行的。

02 旋转方法带来新问题:如何放置第一颗树

林格尔发布猜想后不久,加拿大一位名叫安东·科齐格(Anton Kotzig)的斯洛伐克裔数学家使用此示例做出了比林格尔更大胆的预测。林格尔表示,每个具有2n+1个点的完整图都可以由具有n条边的任何树图平铺;科齐格则推测,平铺总是可以旋转的方式完成。

如果想探究他们的猜想,简单的星形树图是或许是一个不错的起点。

最简单的树图之一是星形:有一个中心点,其他边从中心辐射出来。但它不同于典型的星形图,因为边不必在点周围均匀排列,只需从同一位置向外延伸,除了在中央点之外,不能在其他任何地方相交。

简单的星形树图

确实,数学家很快观察到,具有n+1个点的星形树始终可以完美地复制到具有2n+1个点的完整图形。单单这个事实就很有趣,但是如何证明却让数学家们犯了难。

举一个简单的案例。从11个点开始,将这些点排列成一个圆形,然后将每个点与其他每个点相连以形成一个完整图(如下图)。

相连之后的完整图

然后再设想一个星形树:1个中心点,5条边从该点延伸出去(如下图)。

星形树

接下来,放置星形以使中心点与完整图中的一个点对齐,然后开始旋转,这时你将拥有一个新的星形树副本,该副本与完整图形上的另外一部分重合。

持续旋转星形树,一次旋转一个点的位置。当回到起点时,就像林格尔预测的那样,你将得到一个与之前完整图形一模一样且没有任何部分重叠的图(如下图)。

旋转后完全重合

但是这个实验依然有漏洞:星形图是规则的,因此无论如何放置都无关紧要。但是大多数树并不是,假如树上有许多不同长度的不同分支,那么只有正确放置它们才能使旋转方法起作用,且此时如何放置第一步将至关重要。

幸运的是,数学家们最终找到了一个直观的色彩方法。

03 通过颜色编码找到树的彩虹副本

颜色编码在生活中有很多应用,比如它可以帮助区分日常工作的紧急程度、完成情况等。事实证明,这也是找出如何放置第一颗树的有效方法。

如何进行颜色编码呢?首先,想象围绕一个圆排列的11个点的完整图,编码规则是根据距离(通过一条边连接的两个点之间的距离)进行上色。

假设如果两个点彼此相邻,则它们之间的距离为1,如果两个点中间相隔一个点,则它们之间的距离为2(如下图)。

如何计算距离

现在根据距离为完整图的边上色。距离为1的所有点的边都涂成相同的颜色,例如蓝色。距离为2的点的所有边也都标记相同的颜色,例如黄色。继续这样操作,以使连接点的边距相等的距离都标记相同的颜色。

结果证明,在具有2n+1个点的完整图形上,你需要n种不同的颜色来执行该方案(如下图)。

上色后的完整图形

给完整图形按颜色编码后,如何找到放置第一颗树的方法呢?

这个想法是将树定位,使其覆盖每种颜色的一个边,且不覆盖任何颜色两次(如下图),数学家们将此位置称为树的彩虹副本。对于一个具有2n+1个点的完整图来说,由于着色需要n种颜色,并且其彩虹副本总是具有n+1个点的树图,因此我们知道彩虹副本是存在的。

上色后出现树的彩虹副本

至此,数学家们就可以通过证明每个具有2n+1个点的完整图包含具有n条边的树的彩虹副本,来证明林格尔的猜想。如果彩虹副本始终存在,则完全覆盖完整图始终有效。

花费了40多年的时间,三位数学家证明了这个事实。

04 如何完美放置是证明猜想的最后一步

如果有一个包含11(2n+1=11,则n=5)个点,且已用5种不同颜色上色的完整图形,以及一个包含6个点、5条边的树图,你的任务是在完整图中找到树的彩虹副本。

随着工作不断进行,放置下一个树的工作越来越难,因此你可能需要提前做好计划。三个数学家从一开始就知道,找到彩虹副本或许不难,难得是如何放置。就好像打包过行李箱,众所周知,我们应该从最困难、最复杂的物体开始,比如手提箱、自行车等,因为无论如何,你最后总能找到缝隙塞进一些小东西,数学家们也采纳了这一哲学。

想象一棵有11条边的树,其中6条边的点集中在一起。剩下的大部分是单一的形状,像卷须一样(如下图)。

类似卷须一样的复杂树图

最难放置的部分是具有6条边的点。因此,数学家将它与树的其余部分分开,然后将其首先放置。这就像你要把一张床移到楼上必须得先拆卸再进行组装一样。

通过这样做,他们确保了整个图形中的剩余空间是随机的。

这三位数学家的研究表明,一旦嵌入了树图最难的部分,且完整图的剩余空间是随机的,那么总有一种方法可以嵌入树的其余部分以获得彩虹副本。

除此之外,三位数学家的研究结果给类似未解决的问题提供了新思路。或许适当调整一下还可以解决更多未知猜想。

原创文章,作者:比本网,如若转载,请注明出处:https://www.irwinind.com/56/349360.html