量子雜志：新數(shù)學(xué)證明顯示圖的結(jié)構(gòu)何時涌現(xiàn)
大數(shù)據(jù)文摘授權(quán)轉(zhuǎn)載自zzllrr小樂
作者：Leila Sloman
譯者：zzllrr小樂
想象一下散落在你面前的 100 個點，在一個連點游戲的隨意變化中，開始在點之間畫線。你可以畫多少條線并保持不產(chǎn)生三角形？正方形？11角星？
這些類型的問題在數(shù)學(xué)中有著悠久的歷史。在4 月 26 日發(fā)表的一篇論文中，瑞士蘇黎世聯(lián)邦理工學(xué)院的Oliver Janzer和Benny Sudakov回答了這個問題具有47年歷史的版本。他們考慮點和線的排列（被數(shù)學(xué)家稱為圖graph）。他們正在尋找的結(jié)構(gòu)是一種特殊類型的圖，稱為正則圖（regular graph）。在正則圖中，每個點（或“節(jié)點”）都有相同數(shù)量的線（或“邊”）與之相連。在 2-正則圖中，每個節(jié)點恰好位于兩條邊上；它有“2度”（degree 2）。在 600-正則圖中，每個節(jié)點的度數(shù)為 600。
如果你從 100 個點重新開始并不斷添加邊，則部分點和邊最終將形成正則圖。在某個閾值上，它們的存在變得不可避免，就像當(dāng)你嘗試在四個節(jié)點之間放置五條邊時不可避免地會出現(xiàn)三角形一樣。Janzer 和 Sudakov 弄清楚了這個閾值是什么，并回答了Paul Erd?s（保羅·厄爾多斯，已故著名匈牙利數(shù)學(xué)家，zzllrr小樂譯注） 和 Norbert Sauer 在 1975 年首次提出的問題。
“這個問題真正吸引我的是這個性質(zhì)，它說起來非常簡單，它有著非常古老的歷史，并且會產(chǎn)生大量直接的后續(xù)成果，”Janzer 說。
對于 1- 或 2 -正則圖，早在 1975 年之前就已經(jīng)確定了 Erd?s 和 Sauer 問題的答案。那是因為這些對象非常簡單。1-正則圖可以由兩個節(jié)點和一條邊組成，因此任何非空圖都符合條件。一個 2-正則圖只需要一個閉環(huán)——思考一下多邊形的輪廓。但是 3-正則圖和度數(shù)更高的正則圖在結(jié)構(gòu)上更加復(fù)雜和多樣?！斑@種感覺是，一旦你解決了 [3-正則] 情況，你將能夠解決更一般的情況，”賴希曼大學(xué)和耶路撒冷希伯來大學(xué)的教授Gil Kalai說。
Erd?s 和 Sauer 在他們第一次發(fā)布他們的問題時已經(jīng)對 3-正則 情況有了一些想法。他們知道具有n 個節(jié)點和大約 3n條邊的圖沒有任何 3-正則子結(jié)構(gòu)。而且他們還知道，具有超過n^{8/5}條邊的圖內(nèi)部必須具有 3-正則結(jié)構(gòu)。因此，正確的閾值必須介于n和n^{8/5}階之間，其中“n階”僅表示n乘以某個常數(shù)。但這仍然留下了很多可能性。
László Pyber在 1985 年大大縮小了選擇范圍，當(dāng)時他表明答案必須小于n log(n) 階，這大大低于n^{8/5}。（這里值得一提的是，數(shù)學(xué)家關(guān)心的是當(dāng)一個圖有大量點時會發(fā)生什么。如果n真的很大——比如說，101??——那么n^{8/5}大約是n log(n) 的 10??倍。)
不久之后，Pyber、Vojtěch R?dl 和 Endre Szemerédi構(gòu)建了一個n log(log(n)) 階的圖，其中不包含 3度或更高度的正則圖。因此，Erd?s 和 Sauer 問題的可能答案范圍從低端的n log(log(n)) 階到高端的n log(n) 階。
然后這個問題停滯了將近四年，直到今年 3月 Janzer 和 Sudakov 決定嘗試這個問題?！斑@是高風(fēng)險、高回報的問題之一，”Janzer 說?！叭绻唤鉀Q它，你不會難過，但有時候你需要嘗試?！?/span>
兩人首先深入研究了 Pyber、R?dl 和 Szemerédi 的論文，希望弄清楚這三個人是如何設(shè)法避免生成正則圖的。在他們的圖上，一些節(jié)點有大量的邊連接，而其他節(jié)點只被少數(shù)邊連接。這些不同類型的節(jié)點緊密相連，無法提取更加正則的子結(jié)構(gòu)。
與 Sudakov 合作的加州大學(xué)圣地亞哥分校的數(shù)學(xué)家Jacques Verstraete說：“這種結(jié)構(gòu)是一種靈感，因為它告訴你，好吧，這就是障礙所在?！?/span>
Janzer 和 Sudakov 發(fā)現(xiàn)，如果你添加更多的邊——比n log(log(n)) 高階——以創(chuàng)建 Pyber、R?dl 和 Szemerédi 的圖的更密集版本，整個情況都會發(fā)生變化。突然，正則圖開始出現(xiàn)。該特性使兩位作者能夠從所有類型的圖中挖掘出正則圖：任何具有足夠邊數(shù)的圖都包含一個模仿這些超級密集的 Pyber-R?dl-Szemerédi 結(jié)構(gòu)之一的圖，而后者又包含一個正則圖。
該結(jié)果使他們能夠證明，在一個n節(jié)點圖上，n log(log(n))階的邊肯定會包含一個度數(shù)為 3（或更多）的正則圖。無論你要尋找 3-正則圖還是 1,000,000-正則圖，解的階都是相同的，盡管后者可能需要多倍的邊。Pyber、R?dl 和 Szemerédi 很久以前的結(jié)果意味著階不能再小了 — 最終解決了 Erd?s 和 Sauer 的問題?！爸档米⒁獾氖牵@不僅僅是他們所做的漸進(jìn)式改進(jìn)，他們還解決了這個持續(xù)了 30 多年的問題，”Verstraete 說。
Janzer 和 Sudakov 已經(jīng)找到了將他們的見解應(yīng)用于其他問題的方法。例如，1983 年，數(shù)學(xué)家 Carsten Thomassen發(fā)表了他自己關(guān)于圖的問題。Thomassen 想要獲取一個圖并提取一個子結(jié)構(gòu)，除其他要求外，該子結(jié)構(gòu)在確保每個節(jié)點連接到一定數(shù)量的邊的同時避免短的邊循環(huán)。人們已知知道如果原始圖有足夠多的邊開始，則該嘗試是可能的；Janzer 和 Sudakov 已經(jīng)降低了這個上限。他們還利用他們的工作為1970 年的一個問題做出了貢獻(xiàn)，該問題早于 Erd?s-Sauer 問題。
對于Sudakov來說，這篇論文為很久以前開始的數(shù)學(xué)交響樂提供了一個尾聲。“它利用了以前從事它的人的所有這些成果，”他說?！傲钊梭@訝的是，每個思考過這個問題的人都朝著正確的方向思考?！?/span>
