小乐数学科普：数学家给出图论中一个关于奇数度的老问题的答案

作者：Kevin Hartnett 量子杂志高级作家 2021-5-19 译者：zzllrr小乐 2021-5-20

上图高亮部分形成一个子图，其中各顶点之间的连接数均为奇数。现在数学家知道任何图中必有此类子图最小大小

几十年来，数学家一直在争论一个关于图及其连接数量的简单问题。现在，利用大学数学系学生可能会接受的论据，加利福尼亚大学欧文分校的Asaf Ferber，特拉维夫大学的Michael Krivelevich终于在三月发表的证明中给出了答案。

海法大学的数学家Yair Caro表示：“至少对我来说，如此巧妙但基本的论据组合起来就足够了，有点令人惊讶。”

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

在上个世纪，数学家已经证明了许多与奇偶性有关的基本结果。在1960年代，Tibor Gallai证明了始终可以将图的顶点分为两组（或两个子图），使得每个子图中的所有顶点之间具有偶数个连接（忽略它们与组外顶点的连接 ）——被称为偶数“度”的一种性质。

大约在同一时间，他观察到始终可以将图中的顶点分为两个子图，使得一个子图的所有顶点具有偶数度，而另一个子图的所有顶点具有奇数度。

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

基于你不能始终将一个图分成两个奇数度的子图的事实，下一个自然的问题就变成了：一个图最多有多大比例的顶点数，可以始终确保它具有奇数度？

Krivelevich表示：“不能按奇-奇来分，因此需要为下一个最好的事情做好准备，也就是说，让我们对尽可能多的顶点得到奇数度子图。”

特拉维夫大学的Michael Krivelevich（上上图）和加利福尼亚大学欧文分校的Asaf Ferber（上图）表明，任何图，至少有个子图，顶点数占总顶点数比例1/10000，（子图中所有顶点之间的连接数均为奇数）。

—— 图片提供者：MFO； 利亚姆·哈迪曼（Liam Hardiman）

为了进一步说明这个问题，请考虑一个简单的示例：一个具有三个相连的顶点的三角形图形。可以圈出任意两个顶点，并查看它们彼此之间共享奇数个（1个）连接。 换句话说，可以确定三角形的一个子图，该子图包含其总顶点的三分之二，其中所有顶点都具有奇数度。

大约50年前，数学家预测，对于给定大小的图，总会有一个奇数度的子图，其顶点数占整个图的顶点总数比例，至少达到某个常数比例，例如1/2、1/8或32/1007。 无论一个图具有20个还是20万亿个顶点，子图的大小应始终满足或超过此占比。

“要点是，原始图可能会越来越大，而我们仍然能够保持相同的比例，” Krivelevich说。

但是多年来，没有人能找到如此具体的比率。 在1990年代初期，Caro发现该比率随图的大小而波动，而不是恒定的。 他证明了，如果图中有N个顶点，则存在一个奇数度子图（其中至少包含1√N 个顶点）。 两年后，亚历克斯·斯科特（Alex Scott）将结果改进到了1/logN，这比Caro的结果更接近常数比率，但并非一直如此。

“当时差一点就成功了”，现为牛津大学教授的斯科特说。

这个问题一直未有进展持续了将近30年，直到2020年2月，当时费伯（Ferber）的前研究生导师克里维列维奇（Krivelevich）前往加利福尼亚与他会面。

费伯（Ferber）最近重新探讨了有关奇数度图的问题，这是由他的一位同事问他一个与切线相关的问题引起的。他向Krivelevich提出了问题，并且他们开始为在接下来六个月内发展出的策略而努力。

他们的基本方法（这也是他们之前的人所遵循的）是将图分为三类：

1. “稀疏”图，其中许多顶点很少连接到其他几个顶点；
2. “密集”图，其中单独1个顶点连接到许多其它顶点（相对于图中的顶点总数）；
3. “中间”图，都没有这些性质。

1990年代初始的工作使“稀疏”和“密集”的情况易于理解。最困难的部分是了解“中间”图。

费伯说：“问题是，你在这中间做什么？”

他们搞了一个程序，使他们能够证明一个既不稀疏也不密集的图，必有另一种性质：许多小的子图在它们自己内部是密集的（尽管相对于整个图而言是不密集的），并且它们彼此之间是完全断开的（不相互连接）。 最后一点的证明，许多小的密集子图没有相互连接，这是项目中最棘手的部分之一。

费伯说：“要证明它们之间没有任何边是相当痛苦的。”

Ferber和Krivelevich确定了可以将这些很多小而密集的子图连接在一起，以创建一个更大的子图，其中所有顶点都是奇数度。 现在，它们涵盖了所有可能性-稀疏图，密集图和介于两者之间的图-并表明它们都必然包含一个固定最少顶点数的奇数度子图。

在2020年一个错误的开始之后，斯科特（Scott）让他们知道了可以规避的严重错误，费伯（Ferber）和克里维列维奇（Krivelevich）在2021年3月下旬发表了最终结果。他们证明了每个图，都包含一个子图（顶点数至少占总体的1/10000），其中所有顶点之间的连接数均为奇数。 最终，他们得到一个常数分数比。

（他们得出的实际比例略大，但出于审美原因，他们将其舍入为1/10000。“想象一下，如果我们写1/9456或其他丑陋的表达方式，” Ferber说。）

从这里开始，至少有两种方法。 首先是尝试改进分数。 必有奇数个连接，顶点数比例很可能大于1/10000。 斯科特（Scott）在1990年代推测这个比例可能会多达2/7，后来的工作可以追赶这个数字。

第二种方法涉及这项工作之后开启新路子的一系列相关问题。

数学家想了解具有其他共同数字属性的顶点集合的大小，（例如一大群顶点，它们中的任何一个都不与许多其他顶点连接），可被3或5整除。目前尚不清楚这些情况是否可以也具有简单分数的特征，但是令人鼓舞的是，具有奇数度的顶点的比例具有这个特征。

斯科特说：“ [这个证明]提示你也应该在那里期待一个好的答案。”