上个月在网上发表的一篇论文驳斥了53年前的一个猜测，即给网络节点分配颜色的最佳方式。这篇论文仅用三页纸就展示更好的措施来给网络图上色。 网络图着色问题是近200年来数学家们研讨的一个热点问题，它的灵感来自于如何将相邻区域的颜色映射成不同的颜色。目的是弄分明如何给某些网络的节点上色，这样就不会有两个衔接的节点“共享”相同的颜色。依据细致状况，网络着色可思想能够用来布置如何让客人在婚礼上就座，能够布置工厂任务，以至处置数独难题。 图的着色问题常常易于表述，但常常很难处置。四种颜色能否足以为任何图形着色？ 直到往常，这篇新论文所处置的问题似乎也不例外。它触及张量积——由两种不同的图(称为G和H)以特定的方式组合而成的图。G和H的张量积是一个新的、更大的图中，其中每个节点代表原始图中的一对节点，一个来自G，一个来自H，并且张量积中的两个节点都衔接在一同。 假定你是一位音乐教员，想为五年级的音乐会找到一对好的二重唱组合。您能够制造一个以学生为节点的图表，并在每一对相处得很好的学生之间树立链接。假如你有两种乐器之间的衔接，假如你咏男尹们为特征的二重唱乐谱，那么你能够制造第二个图表，其中每个节点都是不同的乐器。这两个图的张量积关于一个学生和一个乐器的每一个可能的配对都有一个节点，只需两个学生在一同工作得很好，而且这两个乐器兼容，两个节点就会衔接起来。 斯蒂芬在他的博士论文中推测，张量积所需的最小颜色数与其两个构成图之一所需的颜色数相同 。这是图论中的一个主要猜测。” 几十年来，数学家们积聚了大量的证据，其中一些证据表明这个猜测是正确的，另一些则是错误的。关于哪种可能性最终会占上风，数学家们有不同的猜测。但至少每个人似乎都同意，这个问题很难处置。 多伦多瑞尔森大学的安东尼博纳托表示：“我个人以为，这个猜测应该是正确的，由于很多聪明人都看过这个猜测，假如存在的话，他们应该曾经找到了一个反例。” 但往常，俄罗斯数学家雅罗斯拉夫提出了一种结构这种反例的简双措施：张量积需求的颜色比两种构成图中的任何一种都少。这个证明“很简单，但很巧妙”。 张量图与不同的图之间如何映射的问题密切相关，在数学范畴，斯蒂芬的猜测可能是最大的开放问题，这是一个重要的突破。 五光十色的聚会为了对你能从一张张量图上色中搜集到的信息有所了解，想象一下你计划约请朋友到你的乡村庄园渡过一系列的周末。作为一个好的主人，你想要汇集那些喜欢彼此陪伴的人。 你知道，你的一些朋友有同样工作，他们能够立刻联络。同样，你知道每个朋友都有自己的喜好，这也是客人们发现共同兴味的另一种方式。你想，会拉大提琴的舞蹈教员可能喜欢和会打网球的瑜伽教练谈笑风生，但可能很难和集邮的政治科学家交谈。你希望参与任何聚会的每一对客人都能找到一些共同感兴味的范畴，无论是经过工作还是喜好，你想知道在约请名单上的每一个人之前，你需求举行多少次聚会。
您能够运用节点为作业的图来表示不同作业之间的关系，并运用链接衔接任何两个不利于共享业务对话的作业。同样，您能够制造一个节点是不同喜好的图表，并在两个喜好不兼容时将它们衔接起来。 这两张图的张量积将为每个工作—喜好配对有一个节点，假如两个工作和两个喜好都不相容，两个节点就会衔接起来——这正是你在周末请客时想要避免的状况。往常，您能够为张量的节点着色以使衔接的节点具有不同的颜色，那么将为您提供一种措施来构成不同周末的访客列表：您能够在“绿色”周末约请与绿色节点对应的人员，“红色”周末约请与红色节点对应的人等，保障不相容的客人将在不同的周末访问。您运用的颜色数量能够通知您日历中要“关闭”的周末数量。 从这个例子中需求留意的一件事是，任何工作图的有效着色都能够持续到张量积——你能够运用的相同颜色简单地将每个工作喜好的颜色组合到他们的工作中。这样的颜色能够很好的布置聚会，每一对客人都是完整基于他们共同的职业兴味。 从名义上看，斯蒂芬的推测似乎不太可能。究竟，假如你把你的张量着色树立在工作图的着色基础上，你就疏忽了你所知道的关于你朋友的兼容喜好的一切事情，并且有可能把原本能够相处得很好的客人分开。相反，假如你把你一切关于工作和喜好的信息分离起来，或许你能够少用一些颜色，享用一些应得的免费周末。 但是，在50多年的时间里，数学家们找不到一个张量积比它的两个组成图中的颜色更少。在更普遍的“分数”颜色设置中也是如此，在这种状况下，每个节点都能够分配一组颜色——可能是2/3黄色和1/3绿色。(就周末家庭聚会而言，这可能相当于有三个不同的朋友打网球，约请其中两个在“黄色”周末，第三个在“绿色”周末。) 这些发现暗示了这个猜测可能是正确的，但是其他的发现却提出了相反的观念。例如，数学家们曾经证明，斯蒂芬的猜测关于需求无限多种颜色的图或者关于每个链接都有一个首选方向的矢量图来说是不成立的。但是，即便数学家们在一些更普遍的背景下证明了斯蒂芬的猜测，并在另一些更普遍的背景下证明了它的错误，他们似乎也无法在斯蒂芬最初思索的设置中处置它：有限的、无向的、带有非分色的图。 普林斯顿大学的Noga Alon说:“人们普遍以为这很可能是真的，但无论如何，这是十分艰难的。” 着色页面雅罗斯拉夫往常用一个明晰、简单的例子，从这些不肯定性中找到答案，证明斯蒂芬猜测是错的。在一篇论文中，他展示了如何结构一种张量积，这种张量积所需的颜色比它的任何一个组成图都要少。 雅罗斯拉夫首先思索当把一个图G和它的一个“指数”图分离起来构成一个张量积时会发作什么。一个指数图关于G的每一种可能的颜色都有一个节点，每个节点都有固定数量的颜色(这里，我们允许每一种可能的颜色，而不只是衔接节点的颜色不同)。假如图G有7个节点，而调色板有5种颜色，那么指数图就有5^7个节点——因而得名“指数图”。
将我们的留意力返回到颜色上，其中衔接的节点应该是不同的颜色，我们不能保障调色板中的五种颜色足以为图G着色;同样，它们可能也缺乏以给57节点的指数图上色。但数学家们早就知道，有一个图形，这五种颜色足以着色:由G和它的指数图构成的张量积。 事实上，一切的指数图都有这样的性质：把指数图和它所树立的图分离起来的张量积能够用与最初用来制造指数图的调色板完整相同的颜色来着色。雅罗斯拉夫经过展示如何构建一个图G来反驳史蒂芬的猜测，使得G和它的指数图都需求比调色板中更多的颜色。 史蒂芬宣称自己“十分快乐”自己的猜测在这么多年后得到理处置。希托夫在一封电子邮件中写道，他的证明“具有某种文雅、简单和明白的质量”。 数学家们说，这个新的反例很聪明，很有创意，不需求任何复杂、前沿的数学工具。“关于图理论家来说，你能够用两句话来解释这个结构，”卡莱说。 为什么这样的论点被忽视了50多年对数学家来说是一个谜。“有时分，一小块宝石会被树叶掩盖，”黑尔说。“他只是比任何人都更深化天文解了这一点。” 雅罗斯拉夫的图是庞大的：固然他没有精确计算出它们有多大，但他估量G图可能至少有4^100个节点，而指数图至少有4^10000个节点——这个数字远远大于可观测宇宙中粒子的估量数量。 再说一次，“巨量”是在旁观者的眼中。关于雅罗斯拉夫来说，他的反例“不是特别大”.他说。“在数学范畴也有反例(与之相比)，这的确是一件小事。” 固然你不可能约请4^100名客人到你的乡间别墅做客，但雅罗斯拉夫的研讨并没有扫除存在更小的反例。既然数学家们曾经知道史蒂芬的猜测是错误的，那么下一个自然的问题就是它有多错误：一个张量积可能比它的组成图少多少种颜色，以及这样的反例能有多少节点和链接。 同时，这篇新论文给数学家上了重要的一课。有时分，一个猜测很难被证明的缘由很简单，那就是它是错误的。 |
名表回收网手机版
