有望解決一個千禧年大獎難題，這個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://www.ptt.cc/bbs/Math/M.1718629349.A.163.html