小乐数学科普：在高度连通的网络中，必有一个环路——译自量子杂志Quanta Magazine

数学家证明，某种常见类型的图必定包含一条恰好访问每个点一次的路线。

图源：Nico Roper / Quanta Magazine

作者：Leila Sloman 量子杂志特约记者 2024-6-7

译者：zzllrr小乐（数学科普公众号）2024-6-9

随着数学抽象的发展，图是其中最简单的抽象物。在平面上散布一堆点。用直线连接其中一些点。这就是图的全部内容。然而，它们非常强大。它们可用于解决各种各样的问题，从模拟大脑中的神经元到安排路上跑的送货卡车的路线。在数学中，它们可被用来对于称为群的重要代数对象进行分类，描述纽结以及用于无数的其它地方。

图论的核心问题之一是找到在返回起点之前恰好访问图中每个点一次的路线。这些路线被称为哈密顿环路、哈密顿回路（Hamiltonian cycle），以19世纪数学家威廉·罗文·哈密顿（又译哈密尔顿，汉密尔顿，William Rowan Hamilton，1805 - 1865）的名字命名。

许多图都有这样的环路。但在其他情况下，无论你多么努力地寻找哈密顿环路，你最终都会陷入困境：也许你会被困在图的一个孤立的气泡中，无法访问所有的点，或者你可能会被迫回溯你的步骤。

图源：Merrill Sherman / Quanta Magazine

对于像上面这样的小图，通过反复试验来确定哈密顿环路是否存在相对容易。在这个例子中，不存在这种环路。

但是，如果你开始考虑包含数百个、数千个或数百万个点和线的图，那么这项任务就会变得非常困难。没有已知的有效算法来确定给定的大图是否包含环路。如果有人找到这样的算法，它将为数学和计算机科学中的大量问题提供解决方案 https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9 。（这样的算法还可以解决剩下的六个千禧年奖问题 https://www.claymath.org/millennium/p-vs-np/ 之一，从克莱数学研究所获得一百万美元的净收入。）

前两个图描绘了两个哈密顿环路，而在第三个图上，不可能找到这样的环路。

因此，一些数学家没有试图产生一种寻找哈密顿环路的通用算法，而是专注于证明特定类型的图包含此类环路的更简单的问题。2002年，特拉维夫大学的迈克尔·克里夫列维奇（Michael Krivelevich）和现供职于瑞士苏黎世联邦理工学院的本尼·苏达科夫（Benny Sudakov）猜测 https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.10065 ，一类重要的图称为扩展图（expander graph），都包含哈密顿环路。今年2月，苏达科夫与其他四位数学家一起，成功地证明了他在二十多年前首次提出的猜想 https://arxiv.org/abs/2402.06603 。

寻找环路

克里夫列维奇和苏达科夫的猜想打断了一连串的尝试，试图解开保证有哈密顿环路的条件。早在1952年，丹麦数学家加布里埃尔·狄拉克（Gabriel Dirac，1925 - 1984，是著名物理学家保罗·狄拉克Paul Dirac的继子）就证明了每个具有n个点或节点的图，其中每个节点至少连接到n/2个其他的点，都包含一个哈密顿环路。但这种情形下含有很多直线（通常称为边）。多年来，数学家们一直在努力减少哈密顿图必须具有的边数。1976年，匈牙利数学家拉乔斯·波萨（Lajos Pósa，1947 -）证明了通过随机绘制边构建的某些图几乎可以保证包含哈密顿环路 https://www.ceid.upatras.gr/webpages/courses/pithmeth/hamilton-cycles.pdf 。到2001年，克里夫列维奇和苏达科夫，和另外两位同事 https://people.math.ethz.ch/~sudakovb/reghigh.pdf ，以及另一个竞争小组 https://www.math.cmu.edu/~af1p/Texfiles/conham.pdf ，已经证明了关于另一类图的类似结果。

克里夫列维奇和苏达科夫认为他们知道为什么随机绘制的图可能包含哈密顿环路。随机图有两个关键性质。第一个性质涉及检查图中两个大型、不重叠的节点组时会发生什么。在随机图中，很可能至少有一条边连接组。

第二个性质涉及一小组节点。取一小组节点，并将其称为 A。现在通过添加连接到 A 中某一点的每个节点来扩大它，数学家称这个更大的组为 A 的“邻域”。在随机图中，A 的邻域可能远大于 A 本身。所以数学家说A“扩展”到一个大邻域。

具有这两个性质的图（其中大型节点组可能共享一条边，以及小型节点组扩展为更大的组）称为扩展图（expander graph）。如果 A 的邻域是 A的c倍，则该图称为一种c-扩展图。

尽管许多随机图最终成为扩图，但扩展图不一定是随机的。相反，扩展图“具有随机图的性质，而不需要随机性，”剑桥大学的汤姆·古尔（Tom Gur）说。

由于它们必须满足的条件，扩展图是高度互连的，这意味着即使边不多，你也可以通过相对较少的步骤从图的一部分到达另一部分。古尔说，扩展图体现了连通性和稀疏性之间的紧张关系。

扩展图的早期工作受到神经元网络的启发，这些图也出现在其他领域。一些大型在线社交网络是扩展图，扩展图可用于构建高效的纠错码 https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf ，提高随机算法的准确性。

在他们2002年的论文中，克里夫列维奇和苏达科夫证明了某些类型的扩展图具有哈密顿环路 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=90605361a8c0a33901c2742eb749952e44361455 。他们认为扩展图更普遍地也有这样的环路，但他们无法证明这一点。“我们坚信这个猜想应该是真的，我们也非常坚信（证明）这个猜想将非常非常困难，”克里夫列维奇说。

在接下来的二十年里，苏达科夫偶尔会回到这个问题上，但没有取得太大进展。这种情况在 2023年3月发生了变化，当时苏达科夫、他的学生戴维·蒙哈·科雷亚（David Munhá Correia）和帕绍大学的史蒂芬·格洛克（Stefan Glock）对2002年的结果进行了改进 https://arxiv.org/abs/2303.05356 ，证明一类稍大的扩展图必定具有哈密顿环路。“我们产生了许多想法，并在某个时候意识到它们可以以正确的方式组合，”苏达科夫说。“David和Stefan一直对这个问题非常热情，不愿意放弃。

接下来的一个月，华威大学的理查德·蒙哥马利（Richard Montgomery）和伦敦大学学院的阿列克谢·波克罗夫斯基（Alexey Pokrovskiy）来到苏黎世拜访苏达科夫。蒙哥马利在2010年代初在剑桥大学攻读博士学位时曾试图证明苏达科夫和克里夫列维奇的猜想，但他放弃了，因为他认为自己没有合适的工具来解决这个问题。随着苏达科夫、蒙哈·科雷亚和格洛克最近取得的进展，蒙哥马利认为值得再试一次。蒙哥马利说：“我建议继续努力，但不一定有任何强烈的感觉，我们会取得任何重大进展。”

在接下来的几周里，蒙哥马利、苏达科夫和波克罗夫斯基提出了一个策略。他们使用一种称为波萨Pósa旋转的技术来收集长路径的集合，希望最终将这些路径连接成哈密顿环路。蒙哥马利回到沃里克的家中时并没有带回证明，但带着新发现的乐观情绪。“我们有一种感觉，最终，不管怎样，我们应该有正确的想法来获得结果，”苏达科夫说。

在2023年底，穆哈·科雷亚和苏达科夫最近毕业的学生内马尼亚·德拉加尼奇（Nemanja Draganić）告诉苏达科夫，他们也一直在研究这个猜想。穆哈·科雷亚和德拉加尼奇有一个想法，即使用一种称为排序网络的装置将路径连接到哈密顿环路中，他们在 2023年11月的一篇论文中 https://arxiv.org/abs/2311.03185 撞见了这个想法。“我们坐在一起，意识到所有这些想法都可以放在一起，也许可以解决问题，”穆哈·科雷亚说。

排序网络（sorting network）是包含两个匹配集 A 和 B 的图。排序网络的结构使得无论你如何将 A 中的点与 B 中的点配对，都可以找到将 A 中的每个点与其在 B 中的相应点连接起来的不相交路径。“你告诉我你如何进入，你告诉我你想如何退出，”苏达科夫解释道。“排序网络有一个性质，即从每个顶点到目的地都有一条路径。”

11月的论文包含了一个证明，即特定类型的扩展图必须包含排序网络。德拉加尼奇、蒙哥马利、穆哈·科雷亚、波克罗夫斯基和苏达科夫意识到，如果他们能够将排序网络与Pósa旋转结合起来，他们将能够证明这个猜想。他们使用2023年11月论文的技术来证明扩展图也必须包含排序网络。然后，通过将集合 A 和 B 作为他们使用Pósa 旋转创建的路径的端点，他们发现可以将他们的长路径集合连接到哈密顿环路中。“我们明确了证明所需的所有关键概念，”苏达科夫说。

到二月份，该小组已经写完了他们的论文。它不仅证明了2002年克里夫列维奇和苏达科夫的最初猜想，该猜想对扩展图使用了更狭义的定义，而且证明了更强大的东西：任何c-扩展图，只要c足够大，都有一个哈密顿环路。他们的方法还产生了一个实际的哈密顿环路，而不是抽象地证明一个哈密顿环路的存在。苏达科夫将草案转发给克里夫列维奇。“我相当怀疑我们能否在有生之年看到它得到解决，”克里夫列维奇回应道。

新的证明解决了关于哈密顿环路的几个问题。例如，它证明了某些类型的图与群有关，称为凯莱图（Cayley graph），必定具有哈密顿环路。但这不是最终结论。数学家仍然可以尝试找到c的最低边界，即扩展因子（expansion factor），并可能证明更广泛的一类图，称为坚韧图（tough graph），必定包含环路。（苏达科夫说，尽管这是一个愿望，但对它的证明“还远未达到”，他警告说，“甚至没有充分的证据显示这个猜想是正确的。）

没有参与这项工作的古尔说，它建立了“两个对计算机科学至关重要的对象之间的基本联系”。他说，这种联系将导致重要的应用。“我不知道它会采取什么形式。看来这注定是有用的。”

参考资料

https://www.quantamagazine.org/in-highly-connected-networks-theres-always-a-loop-20240607/

https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9

https://www.claymath.org/millennium/p-vs-np/

https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.10065

https://arxiv.org/abs/2402.06603

https://www.ceid.upatras.gr/webpages/courses/pithmeth/hamilton-cycles.pdf

https://people.math.ethz.ch/~sudakovb/reghigh.pdf

https://www.math.cmu.edu/~af1p/Texfiles/conham.pdf

https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=90605361a8c0a33901c2742eb749952e44361455

https://arxiv.org/abs/2303.05356

https://arxiv.org/abs/2311.03185

·开放 · 友好 · 多元 · 普适 · 守拙·

让数学

更加

易学易练

易教易研

易赏易玩

易见易得

易传易及

欢迎评论、点赞、在看、在听

收藏、分享、转载、投稿

查看原始文章出处

点击zzllrr小乐

公众号主页

右上角

数学科普不迷路！