俄罗斯数学家仅需要三页就能描述一种超出专家期望的着色网络的方法
在线
论文中驳斥了一个已有53年历史的关于为网络节点分配颜色的最佳方法的假设。 仅三页的工作就表明存在为某些颜色着色的方法，这些方法超出了专家的所有期望。
着色网的任务[
参见色数 /约 佩雷夫 受到近乎200年的数学家研究的关注，这是由地图着色的问题所启发的，其中相邻国家的地图具有不同的颜色。 任务是了解如何为特定网络的节点（或
图形 ，他们的数学家称为它们）着色，以使任何两个相连的节点具有不同的颜色。 根据上下文的不同，这种着色可以提供一种有效的方式，在婚礼上让客人坐下，安排空闲时间的生产任务，甚至解决
数独问题 。
图形着色任务通常很容易制定，但是难以解决。 即使在寻找整个研究领域开始的问题的答案时，
四种颜色是否足以为任何地图着色 ？ -花了一百多年（如果您有兴趣，答案是肯定的）。
到目前为止，新工作中考虑的任务尚未被视为例外。 它不能解决超过50年的时间，它涉及
张量乘积 -由两个不同图的特殊组合（称为G和H）组成的图。 图G和H的张量积是一个更大的新图，其每个顶点表示原始图的一对顶点-一个来自G，一个来自H--如果如果G和H中的两个对应顶点都相连，则张量积的两个顶点将相连。它们在H中的对应顶点
假设您是一位音乐老师，并且需要为五年级音乐会找到好的二重奏夫妇。 您可以制作一个图形，其顶点将是学生，并且两对之间的键将指示它们之间存在良好的关系。 然后，您可以制作第二张图，其中每个节点将指示不同的乐器，并且它们之间的连接是这两个乐器的二重奏的乐谱的存在。 在这两个图的张量积中，学生和乐器（例如，爱丽丝和长号）的每种可能的结合将有一个顶点，并且如果两个学生一起工作良好，并且两个乐器兼容，则两个顶点将连接在一起。
1966年，现为南卡罗来纳州克莱姆森大学教授的
史蒂芬·赫德涅米 （
Stephen Hedetniemi）在其
博士论文中
建议 ，张量积着色所需的最小颜色数是对两个图形之一进行着色所需的两种颜色中的最小颜色。 耶路撒冷希伯来大学的
吉尔·凯莱 （
Gil Kalai）说：“这是图论的主要假设之一。” “许多人都在想她。”
在过去的几十年中，数学家收集了大量的证据，其中一些论证了该假设的真实性，而另一些论证了该假设的虚假性。 关于最终选择哪种方案，不同的数学家有不同的假设。 但是每个人都同意，至少这是一项艰巨的任务。
多伦多瑞尔森大学的
安东尼·博纳托 （
Anthony Bonato）说：“就个人而言，我认为这个假设是正确的，因为大量聪明的人都在研究它，因此必须提出反例。”
因此，俄罗斯数学家
Yaroslav Nikolayevich Shitov提出了一种创建反例的简单方法，即张量作品所需的颜色少于组成它们的两个图形中的任何一个。 来自加拿大本那比的西蒙·弗雷泽大学（Simon Fraser University）的
Pavol Hell说，证据“基本而出色”。
张量图与关于不同图相互映射的问题密切相关，在数学领域，Hedetniemi假设可能是最大的开放问题，Hell说。 “这是一项重大突破。”
多彩的视频群聊
想象一下从张量图着色中可以提取什么信息，想象一下您将在每个周末邀请您的朋友到郊区居住。 并且，作为好主人，您想聚集将彼此相伴的人们。
您知道有些朋友可以在工作的基础上快速结交朋友，而另一些朋友则不能。 您还知道您的朋友有一种爱好-来宾可以找到共同兴趣的另一种方式。 您推测小提琴舞蹈老师可以和瑜伽教练打网球或与农民联系，他们会教枫糖浆并弹奏钢琴，但是可能与他无关比他将与一位政治学家收集邮票讲话的时候。 您希望每对客人都能在每个周末找到一些共同的兴趣，无论是工作还是业余爱好，并且您想知道需要多少次聚会才能从列表中挑选出所有客人。
Yaroslav Shitov从图论中发现了53岁的Hedetniemi假设的反例您可以想象图形形式的各种类型的工作之间的关系，其中的节点将是工作，而任何两个工作都将通过边连接起来，在这两个边之间，很可能将找不到用于对话的通用主题（但是，这种方法在着色的情况下似乎反过来了）图，这样的顶点连接很有意义，因为我们将使用颜色来分隔这些有问题的对。 您还可以制作一个图，其顶点是不同的兴趣爱好，并将所有不兼容的爱好互连。
这两个图的张量积将为每个工作爱好对都具有节点，并且如果两个工作和两个爱好都不兼容，则两个顶点将被合并-这正是您希望在周末避免的情况。 如果您可以对张量乘积的顶点着色，以使通过肋骨连接的顶点具有不同的颜色，这将为您提供一种创建不同周末的来宾列表的方法：您可以将与绿色顶点对应的人邀请到“绿色”周末，将红色顶点对应的人邀请到“红色”周末。 ”，依此类推，并确保不兼容的客人会在不同的周末出现在名单上。 您使用的颜色数量将告诉您日历需要休息多少天。
从该示例可以看出，可以将工作图的任何有效着色都转移到张量积中-您可以简单地以与工作相同的颜色为每个工作爱好组合着色。 这样的颜色将导致这样一个事实，在聚会上，每对客人将根据他们的专业兴趣而完全兼容，而不论他们的爱好如何。
反之亦然，爱好图的任何可允许的着色都将延续到张量积。 Hedetniemi建议，给张量图着色的最佳方法是使其中一个原始图的颜色最少。
乍看之下，Hedetniemi假说似乎不太可能。 毕竟，如果将张量着色基于工作图的着色，那么您将忽略关于朋友的兼容爱好的所有知识，并可能共享彼此相处的来宾。 如果将有关工作和爱好的所有信息结合在一起，则可以减少使用鲜花的时间，并在没有客人的情况下享受当之无愧的周末。
然而，在过去的50多年中，数学家找不到单一的张量积，因为着色所需的颜色比其任何组成图都少。 他们能够证明如果为两个图之一上色不超过四种颜色，则该假设是正确的。 在“分数”着色的更一般情况下也是如此，可以为每个顶点分配颜色的组合-例如，2/3黄色和1/3绿色。 （就周末聚会而言，这可能对应于您的朋友名单上有三名记者，其中一名打网球，并且您邀请其中两名参加“黄色”周末，邀请第三名参加“绿色”周末的情况）。
这些发现表明该假设可能是正确的，但其他人则相反。 例如，数学家已经证明，对于需要使用无限数量的颜色进行着色的图形，或者对于其边沿具有首选方向的有向图，Hedetniemi假设就不成立了。 但是，尽管数学家在某些情况下证明了Hedetniemi假设并为其他情况反驳了这一事实，但他们无法解决Hedetniemi最初考虑的领域中的问题：带有整数着色的有限无向图。
普林斯顿大学的诺加·埃隆说：“每个人普遍认为这是真的，但很难证明或反驳。”
着色页
Shitov清楚，简单地证明了Hedetniemi假说的虚假性，粉碎了所有这些不确定性。 在这幅作品的主要证明载于一页上，里面充斥着数学知识，他展示了如何创建一种特殊类型的张量产品，该张量产品所需要的颜色涂漆少于其任何组件。
Shitov的工作开始于观察如果将图G与它的一个指数图结合并获得它们的张量积将会发生什么。 对于具有一定固定数量的颜色的每种可能的颜色G，指数图都有一个节点（允许所有可能的颜色，不仅是那些连接的顶点具有不同颜色的颜色）。 例如，如果图G具有7个顶点，并且在调色板中有5种颜色，则指数图将具有5
7个顶点-这就是为什么将其称为指数的原因。
斯蒂芬·赫德涅米（Stephen Hedetniemi）关于为图形的张量积着色的最小颜色数的假设在过去的50年中一直未得到证实如果返回到着色选项，其中连接的顶点必须具有不同的颜色，则我们不能保证调色板的五种颜色足以为图形G着色，并且以相同的方式，它们可能不足以为具有5个
7个顶点的指数图着色。 但是，数学家早就知道，对于一个图，五种颜色是足够的：它是由G及其指数图组成的张量积。
实际上，所有指数图都具有此属性：将指数图与从中创建指数图的图相结合的张量积可以使用与原始图完全相同的颜色数进行着色。 Shitov驳斥了Hedetniemi的假设，表明了如何创建这样的图G，即为该图及其指数图着色需要更多的颜色。
Hedetniemi表示，经过几十年的假设，他对情况的解决感到“完全满意”。 他在一封电子邮件中写道，Shitov的证据“具有一定的优雅，简洁和纯粹的品质”。
数学家说，新的反例非常狡猾和有创造力，不需要复杂的高级数学工具。 “对于图论专家来说，这种设计可以用两句话来解释，” Kalai说。
为什么没有人注意到这一论点已有50多年了，这对数学家来说是一个谜。 地狱说：“有时候，一些宝石藏在一堆树叶下。” “ Shitov只是比其他所有人更深入地理解了这个问题。”
Shitov的图原来是巨大的：他没有计算它们的确切大小，但估计图G可能有大约
4,100个顶点，而指数图将至少有
4,000个顶点，即远远大于其中的基本粒子的数量。可观测的宇宙[
约10 80 /约 佩雷夫 ]。
但是，当然，这全都取决于观察者。 Shitov相信他的反例“不是那么大。 在数学中，您可以找到反例，与之相比，这将是很小的。”
尽管您不太可能邀请
4,000人参加您的乡间别墅，但Shitov的工作并没有拒绝存在规模较小的反例。 但是现在数学家知道Hedetniemi的假设是错误的，自然的问题将是它到底是错误的：与张量积的组成图相比，张量积着色所需的颜色数量更少，并且这些反例可以拥有的最小结点和边数是多少？
同时，伊隆说，新著作为所有数学家提供了重要的一课：“有时，很难证明假设的原因是它是错误的。”