新证据揭示了没有五角星的图表是根本不同的

当你走进一个充满别人的房间时，你可以推测各种各样的东西，从政治倾向于电视观看习惯。但如果房间至少有六个人，你可以用绝对的数学确定性来说些什么，谢谢弗兰克里克西的1930年定理：在这些人中，有一群三个人彼此认识，或者一群人三个人从未见过面。

Ramsey理论的范围，审查了作为群体变大的模式，超越社交聚会。它对称为图形理论的数学分支也具有直接和至关重要的影响。这些图表包括点或顶点的集合，即可能（或可能不会）通过边缘相互连接 - 相当于可能（或可能不）之前的派对的人。图的大小由n设置为n，它具有它的顶点数。其中每个顶点通过边缘连接到每个其他顶点的图形的一部分是拟合的，称为Clique。相反，没有顶点连接到任何其他顶点的图形的一部分称为actinlique或稳定集。

Mathematician PaulErdōs在这方面是多产的，证明了许多定理，在Ramsey理论中可以出现的群体和稳定集合的定量界定。但是在1989年发布的文件中，Erdōs和他的常见的合作者和他的哈杰尔仍然提出了一个仍然没有完全回答的问题：如果你采取大图并坚持那个图形的顶点的子集将具有边缘和非边缘的确切模式匹配较小的图表（称为“诱导的子图”），您是否会自动最终最大的Clique或稳定集，而不是您在随机绘制的相同尺寸的图表中看到？

据普林斯顿大学Maria Chudnovsky称，如果禁止诱导的子图的图表与一般图表的表现相差不同。 “它告诉您，如果您向我提供有关图表的一些非常本地信息 - 有关少数顶点的信息 - 那么全局会发生一些全局。如果我禁止一定的小结构，那么巨大的结构将不可避免地出现。“

剑桥大学的Timothy Gowers表示，当地限制的全球后果是图形理论中的共同主题。但是，“像许多其他猜想相对较简单的态度，但令人惊讶地难以解决，[这个猜想]似乎揭露了我们的理解差距。”

现在，在2021年2月份，牛津大学亚历克斯基斯科特·斯科特·苏特·斯科特·苏格兰大学，滑铁卢大学的索菲斯·斯普尔克（Sophie Spirkl）对填补这种差距取得了巨大进展。他们没有证明整个猜想，但他们表明它对于被Erdōs和Hajnal挑选的关键诱导的子图来说是正确的。 “我们都有一点震惊，”Chudnovsky说。 “我们认为这将是假的，猜想会落下。”

哥伦比亚大学的Gowers称之为“令人兴奋”的工作“令人兴奋”，“多年来，一些好人在多年来努力解决这个问题。”

“这是图表理论的一个重大结果，”加州大学的数学家，圣地亚哥的数学家增加了范胜格雷厄姆。

虽然Erdōs-hajnal猜想是“基本而迷人”，但Chvátal说，证明它已经变得非常困难。到目前为止，数学家逐一攻击了它，主要从最小的禁止结构开始并从那里移动。

但进步一直缓慢，主要结果每十年或两个人出现一次。这意味着猜想仅在迄今为止的诸如迄今为止的情况下确认，包括所有排除的诱导子图具有四个顶点或更少的那些。

2005年，Chudnovsky和Shmuel Safra的Tel Aviv大学证明，当禁止的诱导的子图是称为公牛的五个顶点结构时，Erdős-hajnal猜想被维持，这类似于顶部有两个单顶角的倒三角形。只剩下两个五个顶点配置仍然打开：五角大楼（或真正任何五边多边形），也称为五周期，以及五个顶点路径，由四个线段连接在一起，形成开放链。

在两个突出的问题中，五个周期是更突出的，因为埃尔德斯和哈吉纳的情况提高了它，因此由其他人授予它。 “他们认为它足以使这是一个复杂的是，如果你能解决这种情况，你可以解决所有案件的猜想，”布达佩斯的雷尼数学研究所的JánosPach·帕纳斯·帕赫说，他与鄂尔德斯和哈吉尔共同合作。

哈吉纳等人涉嫌猜想最终会变成假。当他第一次开始这个项目时，Seymour会同意。他认为五个周期案，特别是展示了这一点的反例。而是相反，他和他的共同作者表明，禁止图表中的这种特定的诱导子图将总是产生大的集团或稳定的集合，完全按照Erdős-hajnal猜想规定。

“这对我来说是一个很大的惊喜，结果是真的，”Seymour说。 “似乎没有任何理由是真实的。”

为了达到意外的结果，该团队依赖于“通过矛盾证明”的经典技术。他们认为，猜想有一个反例 - 一种不含任何地方的五周期的图表，而且没有足够大的集团或稳定集合，其蔑视Erdős-hajnal。 “我们试图证明这是如此多的事情，即它不可能存在，”Seymour说。如果无法存在反击范围，这意味着猜想必须首先是正确的。

当然，实际的论点是更涉及的。 Spirkl说，该团队对他们寻求最小的可能性，这是一个常见的策略。数学家经常找到最小的Consterexamples，因为它们可以专注于与手头问题相关的图表的那些部分，并且暂时忽略其余部分。

“最小的反例是属性，这样如果我删除一个顶点，那么它突然不是一个反例，”spirkl说。从n到n - 1顶点减少的剩余图表，现在具有一个集团或稳定的集合，这是如此之大，它不再有资格作为反例。

五个周期证明还建立在Pach和IstvánTomon的2020 pape r上，呈现了一种在图表中找到一个名为“Combs”的某些结构的方法。

为了了解这些梳子看起来像什么，想象一个图形，其中包含类似于简单宽齿梳子的图表，牙齿向上指向牙齿。我们还假设梳子上方有一个顶点，以及将其连接到所有牙齿的尖端的边缘。我们刚刚描述的对象类似于数学意义上的梳子：在每个牙齿的底座上，呈现在它们之间的边缘的一系列顶点。

如果我们在两个这样的顶点之间的边缘看起来更仔细，我们可以遵循从底座上通过两个平行齿（每个构成边缘）的路径。从那里，我们通过单独的边缘将牙齿的尖端连接到梳子上方的单个顶点，并且我们刚刚追踪的形状实际上是一个五边形多边形。

在他们的新论文中，Chudnovsky和她的同事精致的PACH和Tomon的方法，以表明每一个最小的反射率都包含在其中的某处，是一个大梳子。这意味着它必须有五个周期 - 它不应该拥有的一件事。当然，这意味着它根本不是一个反例。通过显示没有找到猜想的反例，四个合作者证明了在这种情况下猜想必须是真的。

既然五个循环问题已得到解答，可能导致完全猜想的证明，因为Erdős和Hajnal预期？ “很长一段时间，五个周期似乎就像一般问题一样难，”Seymour说。 “希望是，如果我们能做到这一点，我们就可以做到一般问题。但这希望困扰了一点。“

“这个证据几乎没有给我们带来，”Spirkl忏悔。 “目前似乎我们需要一些重要的新想法。”但有希望，她补充说。 “它可能是一系列漫长的一系列步骤中的第一个。”

“解决五个周期案件使更多人认为一般猜想必须是真的，”格雷厄姆说。 “虽然没有人找到一种方法来证明它，但是取得了这样的成功，就是这样有助于传播这个词。”

即使是自己，证据仍然被认为是一个重大成就 - 在十多个十多年中，关于这种猜想的最大发展，而且结果不仅限于五个周期案例。 “他们被迫开发解决这个问题的技术可以应用于其他问题，”Chvátal说：“这就是我们在数学中取得进展的方式。”

这四个共同作者已经开始了这个过程，证明了同样的论文，即Erdős-hajnal猜想为其他特殊情况持有，包括所谓的五个周期，带有“帽子” - 一个六个周期，额外的边缘加入两个顶点，在顶部形成一个带有三角形（或帽子）的五角大楼。

但是，有一个诱导的子图，特别是许多数学家在他们的景点中。 “五顶路径必须接下来，”Seymour说。 “如果你不能这样做，你仍然无处可去。”

“似乎有一个似乎是五个周期的证据，对五个顶点路径看起来很有用，”Spirkl说：“但他们不会把我们一路走在那里。”

鉴于，目前，没有人知道如何攻击猜想整体，唯一可用的选择Chudnovsky表示，“一次接近这个问题。 我们做我们能做的事情。“ 当然，这种零碎的方法可能会产生重大回报。 “我们正在做这些特殊情况的一个原因是他们可能会导致我们的反例，”西摩说，这将表明猜想是假的。 第一次出版后三十二年，Erdōs-hajnal猜想已经证明是“令人惊讶的奸诈巅峰”，Pach说。 “Chudnovsky，Scott，Seymour和Spirkl已经解决了这个特殊的案例，但我们仍然不知道我们在哪里。 从我们现在的位置，我们看不到峰会。 也许我们几乎在那里。 也许我们不到一半。 我们必须等待雾升。“