科学网—在高度连接的网络里，圈一定存在
精选
已有 4745 次阅读
2024-11-2 10:10
| 个人分类: 图论 | 系统分类: 科研笔记
在高度连接的网络里，圈一定存在
数学家证明，某种常见类型的图一定包含经过每个点恰好一次的回路。
Leila Sloman 著
左 芬 译
【译注：原文2024年6月7日刊载于QuantaMagazine。】
Icosian 图中的Hamiltonian回路
在 数学的抽象概念里，图可以说是最简单的了。将一堆点撒到平面上，用线把一些点连起来，这就是图了。然而它们却无比地强大。它们可以用来对付一大类的问题，从模拟大脑里的神经元，到规划运输卡车的路线。在数学内部，它们可以用于对群这种重要的代数对象进行分类，用于描述扭结，以及种种其它方向。
图论中的核心问题之一是找到经过图中每个点恰好一次并返回出发点的路径。这些路径被称为Hamiltonian圈，以19世纪数学家William Rowan Hamilton命名。
许多图都有这种圈。但在其它图里，无论你多么努力去寻找Hamiltonian圈，你最终总会碰壁：要么你会陷在图的一个孤岛里，没法访问到所有点，要么你被迫折返之前的点。
对于小图，比如上面这个，可以轻易地通过试错法查明是否存在Hamiltonian圈。在这个图里，显然不存在。
可是如果你考虑有成千上万，甚至上百万点和线的图，这一任务就变得极其困难了。还没有已知的有效算法可以判别一个给定的大图是否存在圈。如果有人发现了一个这样的算法，它将为数学和计算机科学里一大类问题提供答案。（这样一个算法还可以解决现存六大千禧年大奖难题之一，从而从克雷数学研究所赢取一百万奖金。）
左图和中图画出了两个Hamitonian圈，而在右边的图里，无法找出这样的圈。
于是一些数学家不再试图开发找Hamiltonian圈的一般性算法，而是聚焦于证明特定类型的图必然包含这种圈这样一个简单些的问题上。2002年，特拉维夫大学的Michael Krivelevich和如今在瑞士苏黎世联邦理工学院的Benny Sudakov猜想一类重要的图，所谓扩展图（expander graph），全都包含Hamiltonian圈。今年2月，Sudakov与另四名数学家一起，成功证明他在20年前开始探索的这个猜想是对的。
圈的搜寻
Krivelevich 和Sudakov的猜想对放松条件以确保Hamiltonian圈存在的一系列探索做了一个小结。早在1952年，丹麦数学家Gabriel Dirac（著名物理学家Paul Dirac的继子）就证明对于n个点或者说节点的图，如果每个节点连到至少n/2个其它节点，则该图必然包含Hamiltonian圈。但这里的线（通常叫做边）太多了。在后来的岁月里，数学家们一直努力缩减Hamiltonian图里的边数。1976年，匈牙利数学家Lajos Pósa证明通过随机画边的某些图几乎可以确保包含Hamiltonian圈。到了2001年，Krivelevich和Sudakov和另两位同行，与另一个竞争小组分别都证明了关于另一类图的类似性质。
Krivelevich 和Sudakov觉得他们明白了为何随机生成的图很可能包含Hamiltonian圈。随机图有两条关键性质。第一条性质关注的是图中两个大的，互不重叠的节点群体的行为。在随机图中，极有可能两个群体之间至少连有一条边。
第二条性质涉及小的节点群体。选取一个小的节点群体，并称之为A。接着添加与A中某处相连的每个节点来扩大它。数学家们称这个放大了的群体为A的“邻域”。在随机图中，A的邻域很有可能比A本身大得多。因此数学家称A“扩展”到了一个大的邻域。
拥有这两条性质的图——其中大的节点群体很可能共享边，而小的节点群体可以扩展到大得多的群体——被称为扩展图（expander graph）。如果A的邻域是A的c倍大，则该图被称作c-扩展图。
尽管许多随机图其实都是扩展图，但扩展图不一定要是随机的。相反，扩展图“拥有随机图的性质而无需随机性”。剑桥大学的Tom Gur说。
“我们坚信这一猜想一定是对的，但我们也坚信【证明】它会是极其困难的。”
Michael Krivelevich
扩展图必须满足的条件导致它们必然是高度连通的，意味着你可以用相对少量的步数从图的一处到达另一处，尽管图中的边并不是太多。Gur称，扩展图反映了连通性与稀疏性之间的冲突。
关于扩展图的早期工作是由神经网络激发的，但这些图后来也在其它领域出现了。一些大型线上社交网络是扩展图，而且扩展图可以用于构建有效纠错码以及改进随机算法的精度。
在2002年那篇文章中，Krivelevich和Sudakov证明某种类型的扩展图包含Hamiltonian圈。他们认为在更一般的情况下扩展图也会包含这种圈，但他们没法证明。“我们坚信这一猜想一定是对的，但我们也坚信【证明】它会是极其困难的。”Krivelevich称。
在之后的二十年里，Sudakov不时地回到这一问题，但没能取得多少进展。情况在2023年3月发生了变化，Sudakov和他的学生David Munhá Correia以及帕绍大学的Stefan Glock证明一类稍微广泛的扩展图也一定包含Hamiltonian圈。“我们想到了很多主意，然后在某一时刻意识到它们恰好可以组合在一起。”Sudakov说，“David和Stefan一直对这个问题非常热衷，不愿放弃。”
接下来的一个月，华威大学的Richard Montgomery和伦敦大学学院的Alexey Pokrovskiy来苏黎世访问Sudakov。在2010年代早期Montogomery曾试图证明Sudakov和Krivelevich的猜想作为其在剑桥的博士工作的一部分，但最终放弃了，因为他觉得没有适当的工具可以处理这一难题。随着Sudakov, Munhá Correia和Glock最新进展的出现，Montgomery觉得可以再尝试一次。“我建议继续研究这个，但并没有强烈地感觉到我们会做出任何显著的进展，”Montgomery说道。
在之后的两周里，Montgomery, Sudakov和Pokrovskiy想到了一种策略。他们使用一种所谓Pósa转动的技术来累积大量长的路径，希望最终能把这些路径连成一个Hamiltonian圈。Montgomery回到华威的家中时还没想到证明，但已经重新变得乐观。“我们有这种感觉，最终不管以哪种方式，我们总会有适当的想法来得出结果。”Sudakov说道。
2023 年快到年底时，Munhá Correia和Sudakov一个刚毕业的学生Nemanja Dragani ć 告诉Sudakov他们也一直在研究这一猜想。 Munhá Correia 和Dragani ć 有一个办法可以把路径连成 Hamiltonian 圈，需要用到一个叫排序网络（sorting network）的装置，而这个是他们在2023年11月的一篇文章中遇到的。“我们聚在一起后意识到，把所有这些想法合起来有可能解决这一问题，” Munhá Correia说道。
排序网络就是包含两个匹配集合A和B的图。它非常结构化，以致无论你怎么对A和B中的点进行配对，它都可以找到不相交的路径来连接A中的每个点与其在B中的对应点。“你告诉我从哪儿进，以及想从哪儿出，”Sudakov解释道，“排序网络的特性就是从每个顶点到终点都有一条路径。”
11 月的那篇文章证明特殊类型的扩展图必然包含排序网络。Dragani ć , Montgomery, Munhá Correia, Pokrovskiy 和Sudakov意识到，如果他们能用Pósa转动把排序网络组合起来，就能证明猜想了。他们用2023年11月那篇文章的技术来说明，只要是扩展图，就必然包含排序网络。接着，将集合A和B选为使用Pósa转动生成的路径的端点，他们发现可以将长路径的总和接成一个Hamiltonian圈。“我们结晶了证明所需的所有关键概念。”Sudakov说。
到今年2月份，团队把文章撰写完成。它不仅证明了Krivelevich和Sudakov 2002年涉及狭义扩展图的原始猜想，还给出了更强的结果：只要c 足够大，任何c-扩展图都有Hamiltonian圈。他们的方法还可以生成一个实际的Hamiltonian圈，而不是抽象地证明有一个存在。Sudakov将文稿发给了Krivelevich。“我还以为在我们有生之年都看不到它被解决呢，”Krivelevich回复道。
新证明解决了关于Hamiltonian圈的多个问题。例如，它证明某种跟群有关的图，所谓Cayley图，一定拥有Hamiltonian圈。但它还不是最终答案。数学家们还可以努力找出扩展因子c的最小可能下界，并试着去证明一类更广泛的图，所谓韧图（tough graph），也必然包含圈。（Sudakov说尽管这很诱人，证明还“遥不可及”，并且他警告说“甚至没有很好的证据表明这一猜想会是对的”。）
没有参与这一工作的Gur称，它在“计算机科学的两个核心对象间”建立了“一种基本关系”。这一关系，他认为，会导致重要的应用。“我还不清楚它会以何种形式呈现。但一眼看上去就感觉这一定会大有用途。”
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。 链接地址： https://blog.sciencenet.cn/blog-863936-1458165.html
上一篇： 存在与否？两难的设计问题终获解决 下一篇： 物理学家意图分类所有可能的物质相