Get best of the week

彩虹证明证明了图形中存在标准组件

数学家已经证明，较小图的副本始终可以理想地覆盖较大图。



1月8日，三位数学家发表了将近60年前制定的组合论定理的证明，即林格假设。粗略地说，她预测图表-由点和线组成的结构-可以从较小尺寸的相同零件上理想地折叠。

数学家热情地接受了这一假设的证实。耶路撒冷希伯来大学的数学家吉尔·凯莱（Gil Kalai）

说：“幸运的是，这项工作解决了一个非常古老的假设，无法用其他方法验证。”

林格尔的假设预测，可以“平铺”特殊类型的复杂图形（具有数万亿个顶点和边），即 完全覆盖，带有特定类型的较小图的单独副本。从概念上讲，这个问题类似于以下内容：我可以使用商店中所有瓷砖的相同副本完全在厨房的地板上瓷砖吗？在现实生活中，大多数类型的瓷砖都不适合您的厨房-要完全覆盖地板，您必须结合其不同的形状。但是在图论的世界中，该假设预测您总是可以平铺图。

在厨房和图形中，精确放置第一块瓷砖的位置很重要。新作品突出了这个关键问题-既令人惊讶又令人惊讶地直观。

森林与树木


在组合数学中，数学家研究顶点（点）和边缘（线）如何组合以形成称为图的更复杂的对象。您可以问很多关于图形的问题。基本原理之一：在什么情况下最好将较小和较简单的图嵌入较大和较复杂的图？斯坦福大学的雅各布·福克斯（Jacob Fox）

说：“您有一套拼图，您不知道是否可以用这些拼图组装它。” 1963年，德国数学家Gerhard Ringel

他提出了一个简单但广泛的问题。他说，让我们从任何大于3的奇数个顶点开始（为了使假设成立，顶点的数量必须是奇数，我们将在后面看到）。用边连接它们，以便每个顶点都与所有其他顶点相连。然后我们得到一个称为全图的对象。



然后想象一个不同类型的图。这可能是一种简单的方法-将多条边连接成一条线。或带有分支肋的路径。分支可以添加到其他分支。您可以制作任意复杂的图形，而避免仅使用闭环。这样的图称为树。



林格尔的问题与完整图和树的关系有关。他说：首先，想象一个2n + 1个顶点（奇数）的完整图形。然后想象任何由n + 1个顶点组成的树-这样的树可能非常不同。

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

Ringel预测，以这种方式行事，并从正确的位置开始，您可以完美地桥接整个完整图表。这意味着完整图的每个边缘将被树的边缘覆盖，并且树的副本不会重叠。



“我可以复制这棵树。我在整个图表上放了一个副本。她遮住了肋骨。然后，我重复该过程。新证据的共同作者，瑞士联邦理工学院的本尼·苏达科夫说，这一假设表明这可以涵盖一切。伦敦大学伯克翰大学的理查德·蒙哥马利和伯克贝克学院的阿列克谢·波克罗夫斯基说。

最后，Ringel预测，无论将使用许多树选项中的哪一个，都可以对图形进行平铺。这种说法似乎太笼统了。林格尔的猜想适用​​于具有11个顶点的完整图和具有11万亿+ 1个顶点的完整图。并且，完整图形越大，可以为n +1个顶点绘制的可能树的数量就越多。他们每个人如何理想地桥接对应的完整图形？

但是，有理由相信Ringel的假设可能是正确的。最初的确认是，最简单的组合算法并未排除这样的选择：具有2n +1个顶点的完整图中的边数始终可以完全除以具有n +1个顶点的树中的边数。

蒙哥马利说：“将完整图形的边数除以树的边数非常重要。”

数学家很快找到了该假设合理性的进一步证据，从而触发了一系列发现，最终导致了证明。

放置并转动


最简单的树之一是星星：中央山峰，边缘散发出来。但这与恒星的典型图像有所不同，因为边缘不必围绕顶部均匀分布。它们都必须来自一个地方，并且除了中央峰外，不应相交。如果要证明林格尔假设的正确性，那么星形树将是一个自然的起点。



而且，当然，数学家很快发现，一个n +1个顶点的恒星总是完美地铺开一个2n +1个顶点的完整图。这个事实本身很有趣，但是它的证明使数学家有了进一步的思考。

举一个简单的例子。让我们从11个峰开始。我们将它们圈成一个圆圈，并将每个顶点与所有其他顶点连接起来，以获得完整的图形。



现在考虑与之相对应的星形：从中散发出五个边的中心点。



现在，我们放置星形，以使中心顶点与完整图形的顶点之一重合。我们将覆盖几个边缘，但不是全部。现在，将星形移动一个顶点，就好像旋转指南针一样。我们得到了一个新的恒星副本，它叠加在完整图形的完全不同的一组边上。

我们将进一步旋转恒星。当我们回到起点时，我们将铺平整个图而不会叠加星，这与Ringel预测的完全一样。



苏达科夫说：“我们知道，至少如果我们采取星状的树，就不能立即放弃这一假设。” “此外，我们甚至可以非常漂亮地演示这一点：在圆上绘制图形，移动星星，获取新副本并替换整个图形。”

在Ringel提出他的假设后不久，斯洛伐克-加拿大数学家Anton Kotzig使用该示例进行了比Ringel更大的预测。林格尔说，每个具有2n + 1个顶点的完整图都可以与任何具有n + 1个顶点的树平铺，科茨格建议可以用与星形完全相同的方式来平铺：将树放在完整的图上并简单地旋转它。

这个想法似乎是不现实的。恒星是对称的，因此无论如何放置。大多数树木都是弯曲的。为了使旋转方法起作用，需要以非常特定的方式放置它们。

“星星是一个可以手动放置的简单结构，但是如果您手上有一棵正在蔓延的树，上面有一束不同长度的树枝，那么很难想象如何仔细放置它，” Pokrovsky说。

为了使用Kotsig旋转方法解决Ringel假设，数学家需要弄清楚如何放置树的第一个副本，以免出现无法逾越的灌木丛。幸运的是，他们找到了一个丰富多彩的解决方案。

彩虹色通常使生活更轻松。它可以帮助您组织日历或快速区分大型家庭中的一个食物容器和另一个食物容器。事实证明，这也是找出正确将第一棵树正确放置在完整图中的有效方法。

再次想象一个完整的图形，其中有11个顶点排列成一个圆形。根据考虑两个顶点之间距离的简单规则，用颜色代码标记其边缘。

该距离由在一个圆上从一个顶点到另一个顶点（不切掉圆内的路径）必须采取的步数确定。当然，在一个圆圈中，您总是可以沿两个方向前进，因此我们将距离定义为两个峰之间的最短路径。如果这些是相邻的顶点，则它们之间的距离将是1，而不是10。如果它们被一个顶点分开，则距离将是2。



现在，我们根据该距离为图形的边缘着色。我们用一种颜色（例如蓝色）绘制连接距离1的峰的所有边缘。我们绘制连接峰的所有边缘，而峰之间的距离为两个单位之间的距离，例如黄色。

我们继续为图形着色，以使连接相同距离的顶点的所有边具有相同的颜色。不同的距离将以不同的颜色编码。对于具有2n + 1个顶点的完整图形，您需要n种颜色。结果是一幅美丽而有用的图片。



在Ringel和Kotzig提出他们的假设后不久，Kotzig意识到为他的完整图形着色可能是在其上放置树的指南。

想法是安排树，使其覆盖每种颜色的一个边缘，而不覆盖任何颜色两次。数学家称这种安排为一棵树的彩虹复制品。由于着色需要n种颜色，并且n +1个顶点的树将具有n个边缘，因此我们立即知道，很有可能找到彩虹副本。



到1960年代末，数学家已经知道一棵树的彩虹副本具有一个特殊的属性：它仅表示您可以通过旋转树来桥接整个图形的位置。

“如果您制作彩虹副本，那么一切都会起作用，”波克罗夫斯基说。

之后，数学家已经知道，他们可以通过证明每个具有2n + 1个顶点的完整图包含任何具有n + 1个顶点的树的彩虹副本，来证明Ringel假设。而且，如果始终存在彩虹副本，则可以随时桥接图形。

但是，很难证明总有东西存在。为此，数学家将不得不证明，完整的图形只能包含彩虹的树木副本。花费了40多年，但这正是Sudakov和合著者在新工作中取得的成就。

完美包装


假设您有一个包含11个顶点的完整图形和一个包含6个顶点的树。完整的图形以五种不同的颜色绘制。这棵树有五个边缘。您的任务是在完整图中找到树的彩虹副本。

您可以只将树的边缘依次放在图上。第一个很容易放置：您可以为其选择任何颜色的任何边缘。第二个要难一些。它可以躺在几乎任何地方，除了肋骨的颜色与刚覆盖的颜色相同。而且，您将树的边缘放置得越多，任务就越困难。到达最后一根肋骨后，您将完全失去对颜色的选择-只有一种。仍然希望您能提前计划好所有事情。

当您将树的边缘越来越多地放在图形上时，寻找树的彩虹副本的任务变得更加复杂的想法是三位数学家用来解决此问题的方法的必要组成部分。他们寻求在过程结束时保持尽可能多的灵活性的方法。

从一开始，他们就知道很容易找到非常简单的树木的彩虹副本-看起来很长的路，没有树枝或只有很少的树木。最困难的事情是正确放置树木，使许多边缘会聚在一个点上-像星星一样，只是形状和凹凸不平。放置它们就像将婴儿推车推入半满的汽车后备箱中。

“当您尝试用看起来像星星的笨拙的东西填充完整的图形时，困难就开始了，”波克罗夫斯基说。

装满后备箱的任何人都知道，您始终需要从最复杂的物体开始-大行李箱和大型不弯曲的物品，例如自行车。然后可以随时推夹克。数学家也采用了这种哲学。

想象一棵有11条边的树。其中六个会聚在一个中心点。几乎所有其他形式都形成一个单一形式，远离主要形式。



最难放置的部分是树的一部分，该部分由具有六个边缘的峰组成。因此，数学家将其与树的其余部分分开，然后将其首先放置，以便稍后再连接该部分-好像您决定将床分开之前，将其拖到第二层，然后在所需的房间中重新组装。他们甚至没有一次将星的这一部分放置在图中-他们发现了适合将其副本放置在完整图中的各种位置。

然后他们随机选择一份。通过这样做，他们保证了图形中剩余的自由空间也是随机的-也就是说，不同颜色的边缘分布大致相等。他们需要在这个地方放置树的其余部分，这是他们最初放置的路径。

他们在选择放置位置时面临限制。路径应该连接到星星-它们已经放置在树的那部分，并且还必须覆盖它所连接的星星先前未覆盖的颜色。

但是数学家为他们自己留下了选择。他们可以将路径与恒星的几乎所有复制品连接起来。更好的是，由于恒星周围的空间是随机的，因此他们可以选择其他颜色来覆盖树的其余部分。

蒙哥马利说：“到了树的尽头，当情况变得复杂时，我没有剩下一种强制性的颜色，而是一个很小的选择。”

三位数学家以概率论的论据完成了他们的证明。他们表明，在嵌入树木的最复杂部分之后，如果整列中剩余的空间基本上是随机的，那么总有可能找到一种方法在其余的树木中进行构建以获得彩虹副本。

普林斯顿大学的诺加·阿隆说：“现在，您可以从一开始就强加您想要的东西，就好像吸收了树上剩下的东西并获得完整的彩虹色一样。”

数学家尚未描述在每个具有2n +1个顶点的完整图中为n +1个顶点的每棵树查找彩虹副本的确切方法。但是，他们证明必须有彩虹副本。

而且，如果始终存在彩虹副本，则可以始终使用Ringel预测的方法来桥接图形。因此，他的假设是正确的。

该证明还提供了解决组合学中类似的未解决问题的新工具，例如“优美的标记”问题，该问题预测即使在更严格的条件下也可以平铺完整的图形，根据该条件，甚至需要更精确地放置树木。

福克斯说：“这表明人们长期思考的方法确实具有巨大的潜力。” “如果正确应用它们，则可以解决以前似乎无法解决的问题。”

More articles:


All Articles