小乐数学科普新证明揭示不含五边形的图有根本性区别量子杂志

　　作者：Steve Nadis量子杂志2021-4-26 译者：zzllrr小乐 2021-5-28
　　当你走进一个到处都是人的房间时，可以推测出各种各样的事情，从政治倾向到电视观看习惯。但是，如果房间中至少有六个人，则可以凭借绝对的数学确定性说出一些结论，这要根据弗兰克·拉姆齐（Frank Ramsey）在1930年提出的一个定理：在这些人中，要么有一个三人组，他们彼此相识，要么有一个三人组，他们之间从未谋面。
　　拉姆齐（Ramsey）理论研究的范围是随着群体的扩大而涌现出的模式，其范围远远超出了研究社交聚会。它对图论这一数学分支也具有直接和至关重要的意义。这些图由点（或顶点）的集合组成，这些点或顶点可能（或可能不）通过一条边彼此相连-等同于某个聚会上的人可能（或可能没有）见过。图的大小由 n 设置，即它具有的顶点数。图的一部分，如果其中每个顶点都通过一条边与其他每一个顶点连接，则被适当地称为团（ clique）。与之相反，图的一部分，如果其中没有顶点连接到任何其他顶点，称为反团（anti clique）或稳定集。
　　数学家保罗·厄多斯（Paul Erdős）在该领域表现出色，证明了许多定理，为拉姆齐理论中可能出现的团和稳定集设定了定量界限。但是在1989年发表的一篇论文中，Erdős和他的经常合作者András Hajnal提出了一个仍未被完全回答的问题：如果你拿出一个图并坚持认为该图的顶点的子集不会具有边和非边的确切模式匹配较小的图（称为 induced subgraphs ＂诱导子图＂），是否会最终获得比在同样大小的随机绘制的图中看到更大的团或稳定集？
　　根据普林斯顿大学的玛丽亚·楚德诺夫斯基（Maria Chudnovsky）的说法，如果Erdős-Hajnal猜想是正确的，则带有禁止的诱导子图的图的行为与普通图有很大不同。＂它告诉你，如果你向我提供有关图的一些非常局部的信息-有关少量顶点的信息-则全局性事件会发生。如果我禁止出现某种较小的结构，那么一个巨大的结构会不可避免地出现。＂
　　剑桥大学的蒂莫西·高尔斯（Timothy Gowers）说，局部限制导致全局结果是图论的一个普遍主题。但是＂与许多其他陈述相对简单但难以解决的猜想一样，[这个猜想]似乎暴露了我们理解上的空白。＂
　　现在，在2021年2月的一篇论文中，牛津大学的丘德诺夫斯基 Chudnovsky，亚历克斯·斯科特 Alex Scott，普林斯顿大学的保罗·西摩 Paul Seymour和滑铁卢大学的索菲·斯皮尔克 Sophie Spirkl在填补这一空白方面取得了巨大进展。他们没有证明整个猜想，但是他们表明，对于Erdős和Hajnal提出的一个重要的诱导子图，它仍然成立。丘德诺夫斯基说：＂我们都感到有些震惊。＂ ＂我们认为这将是错误的情况，而这种猜想将会落空。＂
　　高尔斯将这项工作称为＂令人兴奋的＂，康考迪亚大学的瓦舍克·查瓦塔尔 Vašek Chvátal说：＂多年来，许多优秀的人为解决这个问题付出了极大的努力。＂
　　＂这是图论的主要成果，＂加利福尼亚大学圣地亚哥分校的数学家范仲格伦（Fan Chung Graham）补充说。
　　缓慢的进展
　　Chvátal说，尽管 Erdős-Hajnal猜想是＂基本而有趣的＂，但它的证明是极其困难的。到目前为止，数学家已经分情况对它进行了进攻，主要是从最小的禁止结构开始，然后再向上发展。
　　但是进展一直很缓慢，主要成果大约每隔一两年才会出现一次。这意味着该猜想迄今为止仅在少数情况下得到了证实，包括所有那些排除的诱导子图具有四个顶点或更少个顶点的情况。
　　2005年，特拉维夫大学的Chudnovsky和Shmuel Safra证明，当被禁止的诱导子图是一个称为公牛的五顶点结构时，Erdős-Hajnal猜想得以维持，它类似于一个倒三角形，顶部带有两个单顶点的牛角。剩下的两种五顶点形状仍处于开放未知状态：五边形（或实际上是任何五边形多边形）（也称为五点圈）和五顶点路径，该路径由链接在一起的四个线段组成，形成一个开放链。
　　在这两个悬而未决的问题中，五点圈更为突出，这是由于Erdős和Hajnal以及后来其他所有人都赋予其重要性。＂他们认为这太复杂了，如果你能解决该案，就可以解决所有情况的猜想，＂与Erdős和Hajnal合作的布达佩斯仁爱数学学院的贾诺斯·帕赫 János Pach说。
　　Hajnal等人怀疑这一猜想最终将被证明是错误的。当他第一次开始这个项目时，西摩 Seymour也同意。他认为，特别是在五点圈的情况下，会是证明的反例。然而发生了相反的情况：他和他的合著者表明，严格按照Erdős-Hajnal猜想所规定的那样，从图中禁止该特定的诱导子图将始终产生较大的团或稳定集。
　　西摩说：＂事实证明这是真的，这让我感到非常惊讶。＂ ＂似乎没有任何理由使它成为现实。＂
　　追求结果
　　为了达到他们意想不到的结果，团队依靠经典的＂反证法＂技术。他们认为这是一个猜想的反例-一个图，该图在任何地方都不包含五点圈，但没有足够大的团或稳定集，而无视Erdős-Hajnal的要求。西摩说：＂然后，我们试图证明它有太多性质，使它不可能存在。＂ 如果反例不存在，那意味着猜想一定是正确的。
　　当然，实际的争论更多。Spirkl说，该团队对任何反例都不感兴趣-他们寻求的是最小的反例，这是图论中的一种常见策略。数学家通常会发现更容易使用最少的反例，因为他们可以专注于图中与手头问题相关的部分，而暂时忽略其余部分。
　　＂最小的反例具有这样的特性，如果我删除单个顶点，则突然不再是反例，＂ Spirkl说。剩下的图形已从 n 减少到 n  – 1个顶点，现在有一个团或稳定集，它太大了，不再符合作为反例的资格。
　　五点圈的证明还建立在2020年 Pach和István Tomon所发现的查找一个图当中特定＂梳子＂结构的方法。
　　为了解这些梳子的外观，请想象一个图，其中包含类似于简单的宽齿梳子且梳齿朝上的图。我们还假设在梳子的正上方有一个顶点，以及将其连接到所有梳齿尖端的边。在数学意义上，我们刚刚描述的对象类似于梳子：在每个梳齿的底部，存在一串顶点，这些顶点之间可能有边。
　　如果我们更仔细地观察两个这样的顶点之间的边，我们可以沿着该路径从底部穿过两个平行的齿（每个路径构成一个边）。从那里，我们将梳齿的尖端通过分开的边连接到梳子上方的单个顶点，而我们刚刚找到的形状实际上是一个五边多边形。
　　在他们的新论文中，Chudnovsky和她的同事完善了Pach和Tomon的方法，以表明每个最小的反例都在其中的某个地方包含一个大梳子。这意味着它必须有五点圈，而这是不应该的。当然，这完全不是一个反例。通过显示找不到该猜想的反例，这四个合作者证明了在这种情况下该猜想必须是正确的。
　　通往顶峰的路线？
　　既然已经回答了五点圈的问题，那么是否可以像Erdős和Hajnal所预期的那样，证明完整猜想呢？西摩说：＂很长一段时间以来，五点圈似乎和一般问题一样困难。＂ ＂我们希望，如果能做到这一点，就能解决一般性的问题。但是这种希望已经消失了。＂
　　＂这个证据几乎无法将我们带到那里，＂ Spirkl坦白说。＂目前看来，我们需要一些重要的新想法。＂ 她补充说，但是有希望。＂这可能是一系列步骤中的第一步。＂
　　Graham说：＂解决五点圈的情况使更多的人认为总的猜想必须是正确的。＂ ＂尽管还没有人找到证明这一点的方法，但取得这样的成功有助于传播这一信息。＂
　　即使单看这个证明，也仍然被认为是一项重大成就，这是十多年来与这一猜想有关的最大进展，而且其结果并不仅仅局限于五点圈情况。Chvátal说：＂他们被迫发展的解决该问题的技术可以应用于其他问题，这是我们在数学上取得进步的方式。＂
　　四位合著者已经开始了这一过程，并在同一篇论文中证明了Erdős-Hajnal猜想在其他特殊情况下的适用性，包括所谓的带有＂帽子＂的五点圈-带有额外边的六点圈，其中两个顶点连接，形成一个五边形，并且顶部为一个三角形（或帽子）。
　　但是，尤其是其中有一个诱导子图，许多数学家都留意到了。西摩说：＂下一个（要解决的）必须是五点路径。＂ ＂如果做不到，那你仍将无果而终。＂
　　＂从五点圈证明中肯定有一些想法对五点路径很有用，＂Spirkl说，＂但它们并不能一路带给我们全部所需。＂
　　鉴于目前还没有人知道如何对整个猜想进行攻克，Chudnovsky说，唯一可用的选择是＂一次解决一个问题＂。我们尽我们所能。＂
　　当然，这种零星的方法总是有可能产生巨大的回报。 Seymour说：＂我们分这些特殊情况的原因之一是，它们可能带领我们找到反例。＂从而表明该猜想是错误的。
　　Pach说，自首次发表32年后，Erdős-Hajnal猜想变成＂一个令人难以置信的高峰＂。＂ Chudnovsky, Scott, Seymour和Spirkl解决了这一特殊情况，但我们仍然不知道自己所处何地。从我们现在的位置，我们看不到山顶。也许我们快到了。也许我们还不到一半。我们必须等待大雾消散。＂