在數(shù)學抽象方面，最簡單的莫過于圖（graph）了。在平面上散放一些點，用線將其中一些連接起來，這就是一個圖了。

但圖卻非常強大。人們已經(jīng)用它來解決各種各樣的問題，從建模大腦中的神經(jīng)元到為路上的送貨卡車設(shè)計路徑。在數(shù)學領(lǐng)域，圖常被用于分類一種重要的代數(shù)對象，即群（group），其能以多種不同的方式來描述扭結(jié)（knot）。

圖論中有一個核心問題：尋找能剛好經(jīng)過圖中每個點一次的路徑，之后再回到起點。這些路徑被稱為哈密頓回路（Hamiltonian cycle），得名于 19 世紀的數(shù)學家威廉?羅文?哈密頓（William Rowan Hamilton）。

許多圖都有這樣的回路。但在另一些圖中，不管你多么努力想要找到一條哈密頓回路，你都無法做到：也許你會被困在圖中某個孤立的范圍內(nèi)，沒有前往所有點的路徑，也可能你會被迫多次經(jīng)過某些點。

對于較小的圖而言（如上圖這個），通過試錯就能相對輕松地確定是否存在哈密頓回路。在上圖的案例中，并不存在。

但如果你的圖包含成千上萬的點和線 —— 在圖論中分別稱為節(jié)點（node）和邊（edge），那么這個任務就會變得非常困難。在確定給定的大圖是否包含哈密頓回路方面，還沒有已知的高效方法。如果某人能找到這樣一個算法，那么數(shù)學和計算機科學領(lǐng)域的許多問題就將迎刃而解。（該算法也能解決千禧年大獎難題中剩余六個中的一個，然后從克雷數(shù)學研究所拿走百萬美元獎金。）

圖中左和中圖各描繪了一個哈密頓回路，而右圖中則無法找到哈密頓回路。

一些數(shù)學家則選擇了另一種策略：不再嘗試構(gòu)建一個求解哈密頓回路的通用算法，而是去證明某些特定類型的圖包含哈密頓回路 —— 這個問題更簡單。

2002 年時，特拉維夫大學的 Michael Krivelevich 和如今在蘇黎世聯(lián)邦理工學院的 Benny Sudakov 推測：一類名為 expander 圖的重要圖全都包含哈密頓回路。今年二月，與其他四位數(shù)學家一起，Sudakov 成功證明了他在 20 多年前首次提出的這一猜想。

探尋回路的旅程

在 Krivelevich 和 Sudakov 提出自己的猜想之前，數(shù)學界一直在嘗試確定圖中必定有哈密頓回路的條件。

1952 年，丹麥數(shù)學家 Gabriel Dirac（著名物理學家保羅?狄拉克的繼子）證明：對于一個有 n 個節(jié)點的圖，如果該圖中每個節(jié)點都與其它至少 n/2 的節(jié)點相連，那么其必定包含一個哈密頓回路。但該回路中的邊非常多。之后許多年時間里，許多數(shù)學家都致力于降低哈密頓圖必須包含的邊的數(shù)量。

1976 年時，匈牙利數(shù)學家 Lajos Pósa 證明：通過隨機繪出邊而構(gòu)建的某種特定的圖幾乎必定包含哈密頓回路。

再到 2001 年，Krivelevich 和 Sudakov 以及另外兩位同事再連同另一個競爭研究團隊為另一類不同的圖證明出了類似的結(jié)果。

Krivelevich 和 Sudakov 認為他們明白了隨機構(gòu)建的圖很可能包含哈密頓回路的原因。隨機圖有兩個關(guān)鍵性質(zhì)。第一個性質(zhì)涉及到這個問題：如果檢查圖中兩個大范圍且不重疊的節(jié)點群，會發(fā)現(xiàn)什么？在一個隨機圖中，非常有可能至少有一條邊連接著這兩個節(jié)點群。

第二個性質(zhì)則與小型節(jié)點群有關(guān)。取一個小型節(jié)點群并稱之為 A。現(xiàn)在，將與 A 中節(jié)點相連的每個節(jié)點都加入進來，從而使 A 擴大。數(shù)學家將這個更大的群稱為 A 的「鄰域」。在一個隨機圖中，A 的鄰域很可能遠比 A 本身大。所以數(shù)學家將這個過程說成是：A「擴展」成了大鄰域。

具備這兩個性質(zhì)（大節(jié)點群很可能有共享邊以及小節(jié)點群會擴展成遠遠更大的節(jié)點群）的圖被稱為「expander 圖」。如果 A 的鄰域比 A 大 c 倍，則該圖就被稱為一個 c-expander。

盡管許多隨機圖都算是 expander 圖，但 expander 圖并不一定隨機。按劍橋大學的 Tom Gur 說法是：expander 圖「具有隨機圖的屬性，但不需要隨機性。」

由于 expander 圖必定滿足上述條件，因此其必定是高度連接的，這就意味著以相對較少的步數(shù)就能從圖的一部分到達另一部分，即便該圖中的邊的數(shù)量并不多。Gur 說：expander 體現(xiàn)了連接性和稀疏性之間的張力。

有關(guān) expander 圖的早期研究受到了神經(jīng)元網(wǎng)絡(luò)的啟發(fā)，并且該圖也已經(jīng)出現(xiàn)在其它領(lǐng)域。某些大型在線社交網(wǎng)絡(luò)就是 expander 圖，并且 expander 圖可用于構(gòu)建高效的糾錯碼以及提升隨機算法的準確度。

Krivelevich 和 Sudakov 在他們 2002 年的論文中證明特定類型的 expander 有哈密頓回路。他們認為更廣義的 expander 也有這樣的回路，但他們當時尚不能證明。Krivelevich 說：「我們堅信這個猜想是正確的，我們也堅信（證明）這個猜想會非常非常困難。」

過去二十年里，Sudakov 不時回頭研究這個問題，但一直都沒有進展。

終得證明

2023 年 3 月時情況發(fā)生了變化，當時 Sudakov、他的學生 David Munhá Correia 以及帕紹大學的 Stefan Glock 正在改進 2002 年的結(jié)果，結(jié)果發(fā)現(xiàn)一類稍大一點的 expander 圖必定包含哈密頓回路。

「我們提出了許多想法，然后在某個時刻意識到能以正確的方式將它們組合起來。」Sudakov 說，「David 和 Stefan 對這個問題一直都充滿熱情，不愿意放棄。」

后一個月，華威大學的 Richard Montgomery 和倫敦大學學院的 Alexey Pokrovskiy 到蘇黎世拜訪 Sudakov。Montgomery 曾在 2010 年代初在劍橋攻讀博士期間嘗試過證明 Krivelevich 和 Sudakov 提出的猜想，但最后放棄了，因為他認為沒有解決該難題的適當工具。

看到了 Sudakov、Munhá Correia 和 Glock 近期的研究進展，Montgomery 覺得可以再試一次了。Montgomery 說：「我提議繼續(xù)研究這個問題，但并不一定認為我們會取得任何重大進展。」

在接下來的兩周時間里，Montgomery、Sudakov 和 Pokrovskiy 提出了一個策略。他們使用一種名為 Pósa rotation 的技術(shù)來收集長路徑并得到一個集合，他們希望最終能將這些長路徑連接起來組成哈密頓回路。Montgomery 在得到證明之前就回到了華威，但卻是帶著新的樂觀情緒回去的。Sudakov 說：「我們有這種感覺：不管怎樣，我們終于應該是有了得到結(jié)果的正確思路。」

到 2023 年底時，Munhá Correia 和 Sudakov 的一位剛畢業(yè)的學生 Nemanja Dragani? 告訴 Sudakov 他們也在研究這一猜想。Munha Correia 和 Dragani? 的想法是使用一種名為揀選網(wǎng)絡(luò)（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 說：「我們聚到一起，意識到將所有這些思路組合起來也許能解決這個問題。」

揀選網(wǎng)絡(luò)是指包含兩個匹配集合 A 和 B 的圖。揀選網(wǎng)絡(luò)的結(jié)構(gòu)比較特別：無論將 A 與 B 中的節(jié)點怎么配對，都有可能找到能將 A 中每個節(jié)點與 B 中對應節(jié)點連接起來的不相交路徑。「你告訴我你怎么進入的，然后你告訴我你想怎么出去。」Sudakov 解釋說，「揀選網(wǎng)絡(luò)有一種性質(zhì) —— 每個頂點都有一條到目的地的路徑。」

11 月的那篇論文包含一項證明：某些特定類型的 expander 圖必定包含揀選網(wǎng)絡(luò)。

Dragani?、Montgomery、Munha Correia、Pikrovskiy 和 Sudakov 認識到如果能將揀選網(wǎng)絡(luò)與 Pósa rotation 組合起來，就能夠證明該猜想。

他們使用那篇論文中的技術(shù)證明 expander 圖也必定包含揀選網(wǎng)絡(luò)。然后，通過將集合 A 和 B 作為使用 Pósa rotation 創(chuàng)建的路徑的端點，他們發(fā)現(xiàn)可以將長路徑集合組合成哈密頓回路。Sudakov 說：「我們明確了證明所需的所有關(guān)鍵概念。」

到今年 2 月份時，該團隊就完成了論文。其中不僅證明了 Krivelevich 和 Sudakov 在 2002 年時提出的原始猜想（使用了狹義的 expander 定義），而且還有更強的證明：只要 c 足夠大，任意 c-expander 都有哈密頓回路。并且他們的方法能實際生成哈密頓回路，而不僅僅是抽象地證明其存在。

• 論文標題：Hamilton cycles in pseudorandom graphs
• 預印本地址：https://people.math.ethz.ch/~sudakovb/hamiltonicity-spectral-gap.pdf

Sudakov 將論文草稿轉(zhuǎn)發(fā)給了 Krivelevich。Krivelevich 回復說：「我曾很懷疑能在我們有生之年看見它得到證明。」

結(jié)語

這個新證明能解決多個與哈密頓回路有關(guān)的問題。舉個例子，其證明某些類型的與群有關(guān)的圖（凱萊圖）必定具有哈密頓回路。

但探尋仍未結(jié)束。

數(shù)學家仍在繼續(xù)努力，希望找到擴展因子 c 可能存在的最低邊界值，以及證明一類范圍更廣的圖（tough graphs）必定包含哈密頓回路。（Sudakov 說盡管這是個好愿望，但得到其證明還「遠不可及」，并且他也警告說：「甚至還沒有足夠的證據(jù)表明這個猜想是正確的。」）

未參與此項研究的 Gur 表示：其確立了「計算機科學核心的兩個對象之間的根本聯(lián)系。」他說，這種聯(lián)系會有重要的應用。「我不知道它會以何種形式出現(xiàn)，只是看起來這必定會很有用。」