只用三页纸，他就推翻了困扰学界半世纪的重要猜想
2019/7/4 14:08:39Erica Klarreich 千人智库
导读
解决这个问题可以帮助我们更加高效地应对许多日常生活中的场景，例如如何在婚礼上为来宾安排座位，或如何为工厂安排不同时段的任务，甚至可以还用来解决数独问题。
来源：Quanta Magazine、科研圈(ID：keyanquan)
翻译：刘悦晨
四色猜想是数学界最著名的猜想之一，即能否只用四种颜色给任意一张地图上色。这一猜想已经被证明是正确的，但它的衍生问题仍然让数学家着迷不已。最近，一位俄罗斯数学家发表了一篇仅有三页的论文，推翻了该领域存在了53年的一个重要猜想。
图片来源：Olena Shmahalo/Quanta Magazine
今年5月在线发表的一篇论文推翻了53年前提出的一个猜想，为图着色问题提出了新的最优解。这篇论文仅仅三页，却证明了对于某些特定的网络而言，着色问题存在许多数学家没有想到的更好的解法。
图着色问题最早来源于人们在为地图上色时的思考——最少使用多少种颜色，就能够保证地图中有相邻边界的国家或地区颜色不同？为了解决这一问题，数学家们钻研了近200年。
这一问题可以被进一步简化：将一张网络的每个节点染色，使得任意两个相连节点颜色不同，最少需要多少种颜色？解决这个问题可以帮助我们更加高效地应对许多日常生活中的场景，例如如何在婚礼上为来宾安排座位，或如何为工厂安排不同时段的任务，甚至可以还用来解决数独问题。
图着色问题往往表述非常简单，但是证明起来十分困难。即使是开启了这一领域的问题，即能否只用四种颜色就能给任何一张地图上色，保证两个相邻的区域颜色各不相同，也历经了一个世纪的求解。(答案是能，如果你想知道的话。)
这篇最新发表的论文也没有推翻“四色规则”，却提出了一种更好的解法。这一问题之所以50多年来一直都未能被解决，是因为它涉及到了复杂的张量积(tensor product)问题，即由两个不同的图形(图论中将其称为G和H)以特定的方式组成的新图形。G和H的张量积是一个更大的新图形，其中每一个节点都代表了来原始图形中的一对节点，分别来自G和于H；并且，如果张量积中的两个节点在G中对应的节点和在H中对应的节点都是相连的，那么它们也是相连的。
设想一下，如果你是一名音乐老师，你想为五年级孩子们的音乐会找到好的二重奏组合。你便可以绘制这样的两幅图：一幅图中，用不同的点代表不同的学生，点与点之间的连接代表两个学生相处融洽、可以配对；另一幅图中，用不同的点代表不同的乐器，点与点之间的连接代表二重奏乐谱中包括有这两件乐器的乐谱。那么，这两幅图的张量积中所包含的点则代表一名学生及其会演奏的一种乐器，如果张量积中的两个点相连，则意味着两名学生能相处得很好，乐器的种类也能搭档，可以组成二重奏。
1966 年，现为克莱姆森大学(Clemson University)教授的Stephen Hedetniemi在他的博士论文中提出，填充张量积时需要的最少颜色数量与填充组成它的两张图时需要的颜色数量较少的那张相同。“这是图论当中一个非常重要的假设。”耶路撒冷希伯来大学(Hebrew University of Jerusalem)的Gil Kalai说，“许多研究者们都思考过这个问题。”
几十年以来，数学家积累了一系列有关这一猜想的研究证据，其中一些表明它是正确的，而另一些则认为它是错误的。尽管数学家们对于这个猜想的正确与否各执一词，但似乎每个人都同意，无论是证明还是证伪都非常困难。
“我个人认为这个猜想应该是真的，因为很多聪明的人都研究过它，如果有的话，应该早能够找到一个反例。”多伦多瑞尔森大学(Ryerson University)的Anthony Bonato说。
但现在，俄罗斯数学家Yaroslav Shitov提出了一种简单的方法来构建反例：填充张量积需要的颜色比填充两个组成图时需要的颜色都要少。加拿大本拿比西蒙弗雷泽大学(Simon Fraser University)的Pavol Hell认为，这一方法“虽然简单，却十分巧妙”。
Hell指出，张量积与不同图形之间应该如何相互映射的问题密切相关。在数学领域，Hedetniemi的猜想可能是最大的开放问题之一，“这篇论文的发表是一个重要的突破”。
Yaroslav Shitov 找到了一个反例，推翻了 Hedetniemi 在 53 年前提出的猜想。图片来源：?zde Bayer, Max Planck Institute for Mathematics in the Sciences
色彩斑斓的聚会
为了更好地理解可以用着色张量积的思维方式解决怎样的现实问题，请想象这样一种情形：你计划在几个周末邀请不同的朋友到你的乡村庄园聚会，作为一名细心的主人，你希望将那些有共同话题的人聚集在一起。
你知道你的一些朋友有工作，他们可以立即建立联系，但另外一些人却没有。同样，你知道每个朋友都有一个爱好，因此客人们可能会通过聚会找到分享他们兴趣和爱好的对象。你希望在每一次聚会中，每两位客人之间都能够找到一些共同语言，无论是在工作方面，还是在兴趣爱好方面；并且你想知道一共需要组织多少次聚会，才能邀请完列表中的所有人。
你可以用一张图来表示不同工作之间的关系，不同的点代表工作，点之间的连接代表两个工作之间没有共同话题。(这听起来好像标反了，但是这样的连接方式在图着色问题中是有意义的，因为我们最终需要用颜色来区分有问题的配对方式。)同样地，你可以用另一张图来表示不同兴趣爱好之间的关系，点之间的连接代表两个兴趣爱好之间不存在共同话题。
这两个图的张量积将为每个工作-爱好配对提供一个节点，如果两个工作和两个爱好都不存在共同的话题，则两个节点相连——这正是你希望在聚会时避免发生的情况。
现在，你可以为张量积的节点着色，使得相互连接的节点具有不同的颜色，从而得到一份在不同周末组织聚会的访客列表。你可以在“绿色”周末邀请绿色节点对应的朋友，“红色”周末邀请红色节点对应的朋友，以此类推，从而确保没有共同话题的客人将在不同的周末参加聚会。所使用的颜色数量可以告诉你在日历中需要被预留的周末的数量。
从这个例子中可以注意到的是，在与工作相关的图形中，任何有效着色都会延伸到张量积——在着色时，可以简单地将每个工作-爱好组合的节点直接用工作对应的颜色着色。如果根据这种着色方法组织聚会，那么每对客人将完全基于他们共同的职业兴趣进行交谈，无论他们的爱好如何。同样地，任何在兴趣图中的着色方式也可以延伸到整个张量积的图中。Hedetniemi猜想，在两张图的着色方法中，使用颜色较少的是为张量积着色的最佳方法。
从表面上看，Hedetniemi的猜想似乎不太可信。毕竟，如果你基于工作图的着色进行张量积的着色，就得忽略朋友们之间存在的共同爱好，那些本来非常合适在一起聚会的客人可能就会被分开。反之，如果你把所有关于工作和爱好的信息结合起来，你或许就能用更少的颜色来预留周末安排聚会，为自己留出多一些清净的周末时光。
然而，五十多年来，数学家们仍然找不到任何一种张量积图形，可以用比组成它的两个图都要少的颜色来填充。他们发现，只要两个组成图中的一个着色时需要四种或更少的颜色，Hedetniemi的猜想就是正确的。在更广泛的“分数”着色中也是如此，即每个节点可以分配一个颜色组合，例如2/3黄色和1/3绿色。(就上文提到的周末家庭聚会的例子而言，这相当于你有三个会打网球的记者朋友，你在标记为“黄色”的周末邀请其中两位，在标记为“绿色”的周末再邀请第三位。)
这些证据表明Hedetniemi的猜想可能是正确的，但也有证据指向了相反的方向。例如，数学家已经证明，对于需要无限多种颜色的图形或者是有向图(即其中的每个连接都有一个偏好的方向)，Hedetniemi的猜想将不再适用。但是，即使数学家在一些更广泛的场景下证明了 Hedetniemi 的猜想，在另一些场景下又推翻了猜想，他们也似乎无法在 Hedetniemi 最初考虑的情形下解决它，即具有非分数着色的有限无向图。
终结争议
现在，Shitov通过一个清晰、简单的证明终结了这些争议，证明Hedetniemi的猜想是错误的。在那篇研究论文中，他仅用了略多于一页密集的数学论证，便展示了如何构造一个张量积反例，使得填充它所需要的颜色比填充其任何一张组成图所需要的颜色都要少。
Shitov首先考虑将图G与它的指数图(exponential graph)之一组合形成张量积的情况。用固定数量的颜色对G着色，每一种可能的情况在指数图中对应一个节点(这里允许每种可能的着色，而不仅仅是相互连接的节点着色不同的情况)。例如，如果图形G具有7个节点，而着色板中有5种颜色，那么指数图将有有57个节点，“指数图”的名字也由此而来。
接下来，看看相连节点颜色不同的着色方式。我们无法保证调色板中的5种颜色足以使图G着色；同样，它们可能也不足以给有57个节点的指数图着色。但是数学家早就知道有一张图，用这5种颜色就可以完成着色——G和它的指数图生成的张量积。
事实上，所有指数图都具有以下属性：要给一张图及其指数图的张量积着色，使用的颜色数量可以等于生成指数图所需的颜色数量。Shitov展示了如何构建一个图G，使得G及其指数图都需要比张量积图中更多的颜色进行着色，从而反驳了Hedetniemi的猜想。
Stephen Hedetniemi的猜想近半个世纪后终于被推翻。图片来源：Courtesy of Stephen Hedetniemi
Hedetniemi的猜想历时几十年终于被推翻，他本人表示对此感到“非常高兴”。Shitov的证据“具备一定的优雅和简洁，而且绝对优质，”他在一封电子邮件中写道。还有数学家认为，Shitov举出的反例是聪明且有创造力的，它不需要任何复杂的、尖端的数学工具。“对图论的研究者而言，你可以用两句话解释它的构造，”Kalai说。
至于为什么这样的论点一直被忽视了超过50年，这对于数学家们来说还是一个谜。“有时，一块小宝石常会被树叶覆盖，”Hell说，“Shitov只是设法比任何人都更深刻地理解它。”
Shitov 论文中举例的图非常庞大：虽然他没有精确计算它们的大小，但他估计图G可能至少有4100个节点，而指数图至少有410000个节点——这个数字远远大于可观测的宇宙中所有粒子的估计数量。
然而，“庞大”只存在于旁观者的眼中。对于Shitov来说，这次提出的反例“并不是非常巨大”。他说：“在数学研究中存在一些更大的反例，相比之下这个只是非常微小的一个。”虽然你不太可能邀请到410000位客人到你的乡村别墅进行聚会，但Shitov的工作并没有排除存在更小反例的可能。
如今，既然数学家知道Hedetniemi的猜想是错误的，那么自然地，下一个问题就是它到底错到什么程度——张量积需要的颜色可能比其组成图要少多少？这些反例的节点和连接数量最少是多少？
Alon指出，这篇论文给数学家们提供了一个重要的教训：“有时候，一个猜想很难被证明，可能仅仅是因为它是错误的。”
感谢作者的付出，版权归原作者所有，如转载稿涉及版权等问题，请立即联系我们，我们会予以更改或删除相关文章，保证您的权利!注：文中内容和观点不代表本平台立场。
http://weixin.100md.com
返回 千人智库 返回首页 返回百拇医药