有望解决一个千禧年大奖难题，这个20多年前的猜想终於得到证明 https://www.jiqizhixin.com/articles/2024-06-16-7 机器之心 在数学抽象方面，最简单的莫过於图（graph）了。 在平面上散放一些点，用线将其中一 些连接起来，这就是一个图了。 但图却非常强大。 人们已经用它来解决各种各样的问题，从建模大脑中的 神经元 到为 路上的送货卡车设计路径。 在数学领域，图常被用来分类一个重要的代数对象，即群（ group），其能以多种不同的方式来描述扭结（knot）。 图论 中有一个核心问题：寻找能刚好经过图中每个点一次的路径，之後再回到起点。 这 些路径被称为 哈密顿 回路（Hamiltonian cycle），得名於19 世纪的数学家威廉・ 罗文・ 哈密顿 （威廉·罗文·汉密尔顿）。 许多图都有这样的回路。 但在另一些图中，不管你多麽努力想要找到一条 哈密顿 回路，你都无法做到：也许你会被困在图中某个孤立的范围内，没有前往所有点的路径， 也可能你会被迫多次经过某些点。 对於较小的图而言（如上图这个），透过试误就能相对轻松地确定是否存在 哈密顿 回路。 在上图的案例中，并不存在。 但如果你的图包含成千上万的点和线—— 在 图论 中分别称为节点（node）和边（edge ），那麽这个任务就会变得非常困难。 在确定给定的大图是否包含 哈密顿 回路方 面，还没有已知的高效率方法。 如果某人能找到这样一个演算法，那麽数学和电脑科学 领域的许多问题就会迎刃而解。 （演算法也能解决千禧年大奖难题中剩余六个中的一个 ，然後从克雷数学研究所拿走百万美元奖金。） 图中左和中图各描绘了一个 哈密顿 回路，而右图中则无法找到 哈密顿 回路。 有些数学家则选择了另一种策略：不再尝试建构一个求解 哈密顿 回路的通用演算法 ，而是去证明某些特定类型的图包含 哈密顿 回路—— 这个问题比较简单。 2002 年时，特拉维夫大学的Michael Krivelevich 和如今在苏黎世联邦理工学院的 Benny Sudakov 推测：一类名为expander 图的重要图全都包含 哈密顿 回路。 今年 二月，与其他四位数学家一起，Sudakov 成功证明了他在20 多年前首次提出的这个猜想 。 探寻回路的旅程 在Krivelevich 和Sudakov 提出自己的猜想之前，数学界一直在尝试确定图中必定有 哈 密顿 回路的条件。 1952 年，丹麦数学家Gabriel Dirac（着名物理学家保罗・狄拉克的继子）证明：对於一 个有n 个节点的图，如果该图中每个节点都与其它至少n/2 的节点相连，那麽其必定包含 一个 哈密顿 回路。 但该回路中的边非常多。 在之後许多年里，许多数学家都致力 於降低 哈密顿 图必须包含的边的数量。 1976 年时，匈牙利数学家Lajos Pósa 证明：透过随机绘出边而建构的某种特定的图几 乎必定包含 哈密顿 回路。 再到2001 年，Krivelevich 和Sudakov 以及另外两位同事再连同另一个竞争研究团队为 另一类不同的图证明出了类似的结果。 Krivelevich 和Sudakov 认为他们明白了随机建构的图很可能包含 哈密顿 回路的原 因。 随机图有两个关键性质。 第一个性质涉及到这个问题：如果检查图中两个大范围且 不重叠的节点群，会发现什麽？ 在一个随机图中，非常有可能至少有一条边连接这两个 节点群。 第二个性质则与小型节点群有关。 取一个小型节点群并称为A。 现在，将与A 中节点相 连的每个节点都加入进来，从而使A 扩大。 数学家将这个较大的群称为A 的「邻域」。 在一个随机图中，A 的邻域很可能远比A 本身大。 所以数学家将这个过程说成是：A「扩 展」成了大邻域。 具备这两个性质（大节点群很可能有共享边以及小节点群会扩展成远远更大的节点群）的 图被称为“expander 图”。 如果A 的邻域比A 大c 倍，则该图就称为一个c-expander。 尽管许多随机图都算是expander 图，但expander 图不一定是随机。 按剑桥大学的Tom Gur 说法是：expander 图「具有随机图的属性，但不需要随机性。」 由於expander 图必定符合上述条件，因此其必定是高度连接的，这就意味着以相对较少 的步数就能从图的一部分到达另一部分，即便该图中的边的数量并不多。 Gur 说： expander 体现了连接性和稀疏性之间的张力。 有关expander 图的早期研究受到了 神经元 网路的启发，而该图也已经出现在其它领域 。 某些大型线上社交网路就是expander 图，而expander 图可用於建立高效率的纠错码 以及提升随机演算法的准确度。 Krivelevich 和Sudakov 在他们2002 年的论文中证明特定类型的expander 有 哈密 顿 回路。 他们认为更广义的expander 也有这样的回路，但他们当时尚不能证明。 Krivelevich 说：「我们坚信这个猜想是正确的，我们也坚信（证明）这个猜想会非常非 常困难。」 过去二十年里，Sudakov 不时回头研究这个问题，但一直都没有进展。 终得证明 2023 年3 月时情况发生了变化，当时Sudakov、他的学生David Munhá Correia 以及帕 绍大学的Stefan Glock 正在改进2002 年的结果，结果发现一类稍大一点的expander 图 必定包含 哈密顿 回路。 「我们提出了许多想法，然後在某个时刻意识到能以正确的方式将它们组合起来。」 Sudakov 说，「David 和Stefan 对这个问题一直都充满热情，不愿意放弃。」 後一个月，华威大学的Richard Montgomery 和伦敦大学学院的Alexey Pokrovskiy 到苏 黎世拜访Sudakov。 Montgomery 曾在2010 年代初在剑桥攻读博士期间尝试过证明 Krivelevich 和Sudakov 提出的猜想，但最後放弃了，因为他认为没有解决该难题的适当 工具。 看到了Sudakov、Munhá Correia 和Glock 最近的研究进展，Montgomery 觉得可以再试 一次了。 Montgomery 说：「我提议继续研究这个问题，但不一定认为我们会取得任何重 大进展。」 在接下来的两周时间里，Montgomery、Sudakov 和Pokrovskiy 提出了一个策略。 他们使 用一种名为Pósa rotation 的技术来收集长路径并得到一个集合，他们希望最终能将这 些长路径连接起来组成 哈密顿 回路。 Montgomery 在得到证明之前就回到了华威， 但却是带着新的乐观情绪回去的。 Sudakov 说：「我们有这种感觉：不管怎样，我们终 於应该是有了得到结果的正确思路。」 到2023 年底时，Munhá Correia 和Sudakov 的一位刚毕业的学生Nemanja Dragani告 诉Sudakov 他们也在研究这个猜想。 Munha Correia 和Dragani的想法是使用一种名 为拣选网路（sorting network）的机制将路径连接成 哈密顿 回路。 这个想法源自 於2023 年11 月的一篇论文《Spanning trees in pseudorandom graphs via sorting networks》。 论文标题：Spanning trees in pseudorandom graphs via sorting networks 论文网址：https://arxiv.org/pdf/2311.03185 Munhá Correia 说：「我们聚到一起，意识到将所有这些思路组合起来也许能解决这个 问题。」 拣选网路是指包含两个符合集合A 和B 的图。 拣选网路的结构比较特别：无论将A 与B 中的节点怎麽配对，都有可能找到能将A 中每个节点与B 中对应节点连接起来的不相交路 径。 「你告诉我你怎麽进入的，然後你告诉我你想怎麽出去。」Sudakov 解释说，「拣 选网络有一种性质—— 每个顶点都有一条到目的地的路径。」 11 月的那篇论文包含一项证明：某些特定类型的expander 图必定包含拣选网络。 DraganiBMontgomery、Munha Correia、Pikrovskiy 和Sudakov 认识到如果能将拣选 网络与Pósa rotation 组合起来，就能够证明该猜想。 他们使用那篇论文中的技术证明expander 图也必定包含拣选网。 然後，透过将集合A 和 B 作为使用Pósa rotation 建立的路径的端点，他们发现可以将长路径集合组合成 哈密 顿 回路。 Sudakov 说：「我们明确了证明所需的所有关键概念。」 到今年2 月时，团队就完成了论文。 其中不仅证明了Krivelevich 和Sudakov 在2002 年 时提出的原始猜想（使用了狭义的expander 定义），而且还有更强的证明：只要c 足够 大，任意c-expander 都有 哈密顿 回路。 而他们的方法能实际生成 哈密顿 回 路，而不仅仅是抽像地证明其存在。 论文标题：Hamilton cycles in pseudorandom graphs 预印本网址： https://people.math.ethz.ch/~sudakovb/hamiltonicity-spectral-gap.pdf Sudakov 将论文草稿转寄给了Krivelevich。 Krivelevich 回覆说：「我曾很怀疑能在我 们有生之年看见它得到证明。」 结语 这个新证明能解决多个与 哈密顿 回路有关的问题。 举个例子，其证明某些类型的 与群有关的图（凯莱图）必定具有 哈密顿 回路。 但探寻仍未结束。 数学家仍在继续努力，希望找到扩展因子c 可能存在的最低边界值，以及证明一类范围更 广的图（tough graphs）必定包含 哈密顿 回路。 （Sudakov 说尽管这是个好愿望 ，但得到其证明还「远不可及」，他也警告说：「甚至还没有足够的证据表明这个猜想是 正确的。」） 未参与此项研究的Gur 表示：其确立了「电脑科学核心的两个物件之间的根本联系。」他 说，这种联系会有重要的应用。 「我不知道它会以何种形式出现，只是看起来这必定会 很有用。」 原文连结： https://www.quantamagazine.org/in-highly-connected-networks-theres-always-a-loop-20240607/ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.253.149.17 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1718629349.A.163.html