在數(shù)學(xué)抽象方面，最簡(jiǎn)單的莫過(guò)于圖（graph）了。在平面上散放一些點(diǎn)，用線將其中一些連接起來(lái)，這就是一個(gè)圖了。

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

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

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

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

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

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

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

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

探尋回路的旅程

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

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

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

再到 2001 年，Krivelevich 和 Sudakov 以及另外兩位同事再連同另一個(gè)競(jìng)爭(zhēng)研究團(tuán)隊(duì)為另一類不同的圖證明出了類似的結(jié)果。

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

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

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

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

由于 expander 圖必定滿足上述條件，因此其必定是高度連接的，這就意味著以相對(duì)較少的步數(shù)就能從圖的一部分到達(dá)另一部分，即便該圖中的邊的數(shù)量并不多。Gur 說(shuō)：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)建高效的糾錯(cuò)碼以及提升隨機(jī)算法的準(zhǔn)確度。

Krivelevich 和 Sudakov 在他們 2002 年的論文中證明特定類型的 expander 有哈密頓回路。他們認(rèn)為更廣義的 expander 也有這樣的回路，但他們當(dāng)時(shí)尚不能證明。Krivelevich 說(shuō)：「我們堅(jiān)信這個(gè)猜想是正確的，我們也堅(jiān)信（證明）這個(gè)猜想會(huì)非常非常困難?！?/span>

過(guò)去二十年里，Sudakov 不時(shí)回頭研究這個(gè)問(wèn)題，但一直都沒(méi)有進(jìn)展。

終得證明

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

「我們提出了許多想法，然后在某個(gè)時(shí)刻意識(shí)到能以正確的方式將它們組合起來(lái)?！筍udakov 說(shuō)，「David 和 Stefan 對(duì)這個(gè)問(wèn)題一直都充滿熱情，不愿意放棄?！?/span>

后一個(gè)月，華威大學(xué)的 Richard Montgomery 和倫敦大學(xué)學(xué)院的 Alexey Pokrovskiy 到蘇黎世拜訪 Sudakov。Montgomery 曾在 2010 年代初在劍橋攻讀博士期間嘗試過(guò)證明 Krivelevich 和 Sudakov 提出的猜想，但最后放棄了，因?yàn)樗J(rèn)為沒(méi)有解決該難題的適當(dāng)工具。

看到了 Sudakov、Munhá Correia 和 Glock 近期的研究進(jìn)展，Montgomery 覺(jué)得可以再試一次了。Montgomery 說(shuō)：「我提議繼續(xù)研究這個(gè)問(wèn)題，但并不一定認(rèn)為我們會(huì)取得任何重大進(jìn)展?！?/span>

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

到 2023 年底時(shí)，Munhá Correia 和 Sudakov 的一位剛畢業(yè)的學(xué)生 Nemanja Dragani? 告訴 Sudakov 他們也在研究這一猜想。Munha Correia 和 Dragani? 的想法是使用一種名為揀選網(wǎng)絡(luò)（sorting network）的機(jī)制將路徑連接成哈密頓回路。該想法源自 2023 年 11 月的一篇論文《Spanning trees in pseudorandom graphs via sorting networks》。

• 論文標(biāo)題：Spanning trees in pseudorandom graphs via sorting networks
• 論文地址：https://arxiv.org/pdf/2311.03185

Munhá Correia 說(shuō)：「我們聚到一起，意識(shí)到將所有這些思路組合起來(lái)也許能解決這個(gè)問(wèn)題?！?/span>

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

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

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

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

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

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

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

結(jié)語(yǔ)

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

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

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

未參與此項(xiàng)研究的 Gur 表示：其確立了「計(jì)算機(jī)科學(xué)核心的兩個(gè)對(duì)象之間的根本聯(lián)系?！顾f(shuō)，這種聯(lián)系會(huì)有重要的應(yīng)用。「我不知道它會(huì)以何種形式出現(xiàn)，只是看起來(lái)這必定會(huì)很有用?！?/span>