小樂數學科普：新證明揭示不含五邊形的圖有根本性區別-量子雜誌

作者：Steve Nadis量子雜誌2021-4-26 譯者：zzllrr小樂 2021-5-28

當你走進一個到處都是人的房間時，可以推測出各種各樣的事情，從政治傾向到電視觀看習慣。但是，如果房間中至少有六個人，則可以憑藉絕對的數學確定性說出一些結論，這要根據弗蘭克·拉姆齊（Frank Ramsey）在1930年提出的一個定理：在這些人中，要麼有一個三人組，他們彼此相識，要麼有一個三人組，他們之間從未謀面。

拉姆齊（Ramsey）理論研究的範圍是隨著群體的擴大而湧現出的模式，其範圍遠遠超出了研究社交聚會。它對圖論這一數學分支也具有直接和至關重要的意義。這些圖由點（或頂點）的集合組成，這些點或頂點可能（或可能不）透過一條邊彼此相連-等同於某個聚會上的人可能（或可能沒有）見過。圖的大小由

設定，即它具有的頂點數。圖的一部分，如果其中每個頂點都透過一條邊與其他每一個頂點連線，則被適當地稱為團（

clique）

。與之相反，圖的一部分，如果其中沒有頂點連線到任何其他頂點，稱為反團（anti

clique

）或穩定集。

數學家保羅·厄多斯（Paul Erds）在該領域表現出色，證明了許多定理，為拉姆齊理論中可能出現的和穩定集設定了定量界限。但是在1989年發表的一篇論文中，Erds和他的經常合作者András Hajnal提出了一個仍未被完全回答的問題：如果你拿出一個圖並堅持認為該圖的頂點的子集不會具有邊和非邊的確切模式匹配較小的圖（稱為

induced subgraphs

“誘導子圖”），是否會最終獲得比在同樣大小的隨機繪製的圖中看到更大的團或穩定集？

根據普林斯頓大學的瑪麗亞·楚德諾夫斯基（Maria Chudnovsky）的說法，如果Erds-Hajnal猜想是正確的，則帶有禁止的誘導子圖的圖的行為與普通圖有很大不同。“它告訴你，如果你向我提供有關圖的一些非常區域性的資訊-有關少量頂點的資訊-則全域性性事件會發生。如果我禁止出現某種較小的結構，那麼一個巨大的結構會不可避免地出現。”

劍橋大學的蒂莫西·高爾斯（Timothy Gowers）說，區域性限制導致全域性結果是圖論的一個普遍主題。但是“與許多其他陳述相對簡單但難以解決的猜想一樣，［這個猜想］似乎暴露了我們理解上的空白。”

現在，在2021年2月的一篇論文中，牛津大學的丘德諾夫斯基

Chudnovsky，

亞歷克斯·斯科特

Alex Scott

，普林斯頓大學的保羅·西摩

Paul Seymour

和滑鐵盧大學的索菲·斯皮爾克

Sophie Spirkl

在填補這一空白方面取得了巨大進展。他們沒有證明整個猜想，但是他們表明，對於Erds和Hajnal提出的一個重要的誘導子圖，它仍然成立。丘德諾夫斯基說：“我們都感到有些震驚。” “我們認為這將是錯誤的情況，而這種猜想將會落空。”

高爾斯將這項工作稱為“令人興奮的”，康考迪亞大學的瓦舍克·查瓦塔爾

Vaek Chvátal

說：“多年來，許多優秀的人為解決這個問題付出了極大的努力。”

“這是圖論的主要成果，”加利福尼亞大學聖地亞哥分校的數學家範仲格倫（Fan Chung Graham）補充說。

緩慢的進展

Chvátal

說，儘管

Erds-Hajnal

猜想是“基本而有趣的”，但它的證明是極其困難的。到目前為止，數學家已經分情況對它進行了進攻，主要是從最小的禁止結構開始，然後再向上發展。

但是進展一直很緩慢，主要成果大約每隔一兩年才會出現一次。這意味著該猜想迄今為止僅在少數情況下得到了證實，包括所有那些排除的誘導子圖具有四個頂點或更少個頂點的情況。

2005年，特拉維夫大學的Chudnovsky和Shmuel Safra證明，當被禁止的誘導子圖是一個稱為公牛的五頂點結構時，Erds-Hajnal猜想得以維持，它類似於一個倒三角形，頂部帶有兩個單頂點的牛角。剩下的兩種五頂點形狀仍處於開放未知狀態：五邊形（或實際上是任何五邊形多邊形）（也稱為五點圈）和五頂點路徑，該路徑由連結在一起的四個線段組成，形成一個開放鏈。

在這兩個懸而未決的問題中，五點圈更為突出，這是由於Erds和Hajnal以及後來其他所有人都賦予其重要性。“他們認為這太複雜了，如果你能解決該案，就可以解決所有情況的猜想，”與Erds和Hajnal合作的布達佩斯仁愛數學學院的賈諾斯·帕赫

János Pach

說。

Hajnal等人懷疑這一猜想最終將被證明是錯誤的。當他第一次開始這個專案時，西摩

Seymour也

同意。他認為，特別是在五點圈的情況下，會是證明的反例。然而發生了相反的情況：他和他的合著者表明，嚴格按照Erds-Hajnal猜想所規定的那樣，從圖中禁止該特定的誘導子圖將始終產生較大的團或穩定集。

西摩說：“事實證明這是真的，這讓我感到非常驚訝。” “似乎沒有任何理由使它成為現實。”

追求結果

為了達到他們意想不到的結果，團隊依靠經典的“反證法”技術。他們認為這是一個猜想的反例-一個圖，該圖在任何地方都不包含五點圈，但沒有足夠大的團或穩定集，而無視Erds-Hajnal的要求。西摩說：“然後，我們試圖證明它有太多性質，使它不可能存在。” 如果反例不存在，那意味著猜想一定是正確的。

當然，實際的爭論更多。Spirkl說，該團隊對任何反例都不感興趣-他們尋求的是最小的反例，這是圖論中的一種常見策略。數學家通常會發現更容易使用最少的反例，因為他們可以專注於圖中與手頭問題相關的部分，而暫時忽略其餘部分。

“最小的反例具有這樣的特性，如果我刪除單個頂點，則突然不再是反例，” Spirkl說。剩下的圖形已從

減少到

– 1個頂點，現在有一個團或穩定集，它太大了，不再符合作為反例的資格。

五點圈的證明還建立在2020年

Pach和István Tomon

所發現的查詢一個圖當中特定“梳子”結構的方法。

為了解這些梳子的外觀，請想象一個圖，其中包含類似於簡單的寬齒梳子且梳齒朝上的圖。我們還假設在梳子的正上方有一個頂點，以及將其連線到所有梳齒尖端的邊。在數學意義上，我們剛剛描述的物件類似於梳子：在每個梳齒的底部，存在一串頂點，這些頂點之間可能有邊。

如果我們更仔細地觀察兩個這樣的頂點之間的邊，我們可以沿著該路徑從底部穿過兩個平行的齒（每個路徑構成一個邊）。從那裡，我們將梳齒的尖端透過分開的邊連線到梳子上方的單個頂點，而我們剛剛找到的形狀實際上是一個五邊多邊形。

在他們的新論文中，Chudnovsky和她的同事完善了Pach和Tomon的方法，以表明每個最小的反例都在其中的某個地方包含一個大梳子。這意味著它必須有五點圈，而這是不應該的。當然，這完全不是一個反例。透過顯示找不到該猜想的反例，這四個合作者證明了在這種情況下該猜想必須是正確的。

通往頂峰的路線？

既然已經回答了五點圈的問題，那麼是否可以像Erds和Hajnal所預期的那樣，證明完整猜想呢？西摩說：“很長一段時間以來，五點圈似乎和一般問題一樣困難。” “我們希望，如果能做到這一點，就能解決一般性的問題。但是這種希望已經消失了。”

“這個證據幾乎無法將我們帶到那裡，” Spirkl坦白說。“目前看來，我們需要一些重要的新想法。” 她補充說，但是有希望。“這可能是一系列步驟中的第一步。”

Graham

說：“解決五點圈的情況使更多的人認為總的猜想必須是正確的。” “儘管還沒有人找到證明這一點的方法，但取得這樣的成功有助於傳播這一資訊。”

即使單看這個證明，也仍然被認為是一項重大成就，這是十多年來與這一猜想有關的最大進展，而且其結果並不僅僅侷限於五點圈情況。Chvátal說：“他們被迫發展的解決該問題的技術可以應用於其他問題，這是我們在數學上取得進步的方式。”

四位合著者已經開始了這一過程，並在同一篇論文中證明了Erds-Hajnal猜想在其他特殊情況下的適用性，包括所謂的帶有“帽子”的五點圈-帶有額外邊的六點圈，其中兩個頂點連線，形成一個五邊形，並且頂部為一個三角形（或帽子）。

但是，尤其是其中有一個誘導子圖，許多數學家都留意到了。西摩說：“下一個（要解決的）必須是五點路徑。” “如果做不到，那你仍將無果而終。”

“從五點圈證明中肯定有一些想法對五點路徑很有用，”Spirkl說，“但它們並不能一路帶給我們全部所需。”

鑑於目前還沒有人知道如何對整個猜想進行攻克，Chudnovsky說，唯一可用的選擇是“一次解決一個問題”。我們盡我們所能。”

當然，這種零星的方法總是有可能產生巨大的回報。

Seymour

說：“我們分這些特殊情況的原因之一是，它們可能帶領我們找到反例。”從而表明該猜想是錯誤的。

Pach說，自首次發表32年後，Erds-Hajnal猜想變成“一個令人難以置信的高峰”。“

Chudnovsky， Scott， Seymour和Spirkl

解決了這一特殊情況，但我們仍然不知道自己所處何地。從我們現在的位置，我們看不到山頂。也許我們快到了。也許我們還不到一半。我們必須等待大霧消散。”