量子杂志：数学家成功解答了关于奇图的旧问题

选自Quanta Magazine

作者：Kevin Hartnett

机器之心编译

来自加州大学、特拉维夫大学的研究者成功的解决了图中连接数为奇数的顶点的比例问题，证明了每个图都包含一个常比例子图，其中所有的顶点都有奇数度。

几十年来，科学家一直在争论一个简单的问题，这个问题是关于图及其连接的数量问题。现在，用一个数学本科生可能会想到的论点，来自加州大学欧文校区 Asaf Ferber 、特拉维夫大学的 Michael Krivelevich 终于在今年 3 月发表的一篇文章中给出了答案。

论文地址：https://arxiv.org/pdf/2009.05495.pdf

「至少对我来说，这是一个令人惊讶的发现，这种巧妙但基本的论点组合就足够了，」来自海法大学数学家 Yair Caro 说道。

图是由边（线）连接的顶点（点）的集合。经过数百年的研究，数学家仍在研究其基本特性。一个是涉及图顶点的「奇偶性」，即它们是否与奇数或偶数个其他顶点相连。

数学家们一直在探索：图顶点的「奇偶性」问题

在过去的一个世纪里，数学家们已经证明了许多与奇偶性有关的基本结果。在 1960 年代，匈牙利数学家 Tibor Gallai 证明了始终可以将图的顶点分为两组或子图，这样所有的顶点在每个子图具有偶数个连接（忽视外连接顶点组）——一个被称为「度（degree）」的属性。

大约在同一时间里，Tibor Gallai 观察到始终可以将图中的顶点分为两个子图，这样一个图中的顶点都是偶数度，而另一个图中的顶点都是奇数度。

然而，最终的选择是不可能的：因为无法将每个图都分成两个子图，以使每个子图中的所有顶点都具有奇数度。之所以知道这一点，是因为在 1730 年，也许是历史上最最多产的数学家 Leonhard Euler 证明，如果一组顶点都具有奇数度，则该组顶点数必须是偶数。如果将一个图的顶点分成两个子图，并且每个子图中的所有顶点都具有奇数度，则每个子图必须具有偶数个顶点，因此，原始的未拆分图也只能具有偶数个顶点（因为两个偶数之和总是偶数）。也就是说，如果原始图的顶点数为奇数，则无法进行拆分。

鉴于无法将一个图分成奇数度的两个子图，因此下一个问题变为：在一个图中，可以确定的奇数度顶点的最大比例是多少？

「你不能采用奇数 - 奇数（odd-odd），因此你需要退而求其次，也就是说，对大部分的顶点做奇数，」Krivelevich 表示。

特拉维夫大学的 Michael Krivelevich。

为了进一步说明这个问题，示例如下：一个具有三个相连顶点的图（三角形），在隔离任意两个顶点后，发现它们彼此之间共享奇数个连接。换句话说，可以确定包含总顶点数三分之二的三角形子图，其中所有顶点都是奇数度。

大约 50 年前，数学家预测，对于给定大小的图，总会有一个全奇数度的子图包含整个图中至少恒定比例的顶点数，例如 1/2、1/8、32/1,007。无论图具有 20 个顶点还是 20 万亿个，子图的大小应始终满足或超过相同的比率。

「关键是，原始的图可能会越来越大，而我们仍然能够维持着相同的比例，」Krivelevich 说道。

但是多年来，没有人能找到如此具体的比率。20 世纪 90 年代初，Caro 发现了并非恒定而是随图的大小而波动的比率。他证明了如果图中有 N 个顶点，则存在这样一个子图，其中至少包含 1/sqrt(N) 个奇数度顶点。两年后，Alex Scott 将结果提升到了 1/logN，这比 Caro 的结果更接近恒定比率，但 Scott 并不特别满意。

Alexander Scott。

「这个结果没有到达真正的真理，」现为牛津大学教授的 Scott 说。

跨越 30 年，才有了新的进展

直到 30 年后，在 2020 年 2 月，这个问题才有了新的进展，Ferber 的前研究生顾问 Krivelevich 前往加利福尼亚与他会面。

加州大学欧文分校的 Asaf Ferber。

在 Ferber 的一位同事问他一个与切线相关的问题后，Ferber 重新审视了有关奇数图的问题，并与 Krivelevich 在接下来六个月内共同制定策略。

经过制定，基本的方法是将图分为三类：其中有许多很少连接其他点的顶点的「稀疏」图；其中一个顶点连接到许多其他顶点（相对于图中的顶点总数）的「密集」图；以及没有以上两图特质的「中间」图。Ferber 表示，90 年代的工作使稀疏图和密集图都很好理解，最困难的部分是了解「中间」图。

于是他们试图证明如果图既不稀疏也不稠密，则必须具有另一种品质：许多小的子图自身密集（尽管相对于整个图而言不密集），并且彼此完全不连接。证明许多小的密集子图没有相互连接，这是项目中最棘手的部分之一。

Ferber 说：「要证明它们之间没有边缘是相当痛苦的。」

Ferber 和 Krivelevich 确定可以将这些许多小而密集的子图连接在一起，以创建一个更大的子图，其中所有的顶点都有奇数度。现在已经涵盖了所有的可能性：稀疏图，密集图和介于两者之间的图，它们都必须包含一定最小尺寸的奇数子图。

在 2020 年的错误开端之后，Scott 让他们意识到了能够规避的那些严重错误。2021 年 3 月下旬，Ferber 和 Krivelevich 发布了最终结果。他们证明，每张图都包含一个子图，这个子图至少包含 1/10,000 个顶点，这些顶点之间的连接数都是奇数。最后是常数分数。

目前至少有两条路可以走。首先是尝试提高分数，连接数必须为奇数的顶点的比例很可能大于 1/10,000。第二个问题涉及一系列相关的问题，这些问题在这项工作之后焕发了新的生机。

数学家希望了解具有其他共同数值属性的顶点集合的大小，例如有一大组顶点，没有一个顶点能被 3 或 5 整除。目前还不清楚这些情况是否也可以用简单分数来表征，但令人鼓舞的是，奇数度顶点的比例可以。

Scott 表示：「证据表明，你也应该期待一个不错的答案。」

参考链接：https://www.quantamagazine.org/mathematicians-answer-old-question-about-odd-graphs-20210519/