斯隆獎得主趙宇飛：大圖世界里的數(shù)學(xué)利器 | 欲善其事，先利其器

baoyisheng143 2021-07-19

展開全文

編者按：數(shù)學(xué)的理論往往先行于實際應(yīng)用，在時機成熟的時候迅速成為實際應(yīng)用的有力工具。

作者 | 趙宇飛

編譯 | 廖璐，賈偉

例如微分幾何，在1854年便有相對成熟的理論，但直到1915年愛因斯坦提出廣義相對論后，人們發(fā)現(xiàn)物理世界竟然是4維黎曼流形，才得到物理和數(shù)學(xué)兩界的廣泛關(guān)注，逐漸成為物理學(xué)家理解世界的必備工具。

組合數(shù)學(xué)中的「圖正則引理」，或許亦是如此。

這一引理是阿貝爾獎（Abel Prize）得主安德烈·塞邁雷迪（Endre Szemerédi）在上世紀70年代的工作，討論了當(dāng)圖（Graph）足夠大時所呈現(xiàn)出的規(guī)律，在組合數(shù)學(xué)中具有重要的影響力。簡單來講，即一個充分大的圖，一定存在我們想要的子結(jié)構(gòu)；從哲學(xué)意義上講，即一個系統(tǒng)不可能是完全紊亂，沒有規(guī)律的。

這一引理，是理解大圖（Large Graph）的重要工具。當(dāng)下，伴隨著數(shù)據(jù)的迅猛增加，圖數(shù)據(jù)和圖網(wǎng)絡(luò)變得越來越具規(guī)模。這種情況，恰好完全屬于「圖正則引理」的應(yīng)用范疇。如何能夠更好地理解和使用這些大圖數(shù)據(jù)，「圖正則引理」或許正是計算機科學(xué)家一個可能趁手的利器。

來自MIT 的數(shù)學(xué)家趙宇飛，所從事的正是這樣的工作，盡可能地讓「圖正則引理」這把利器變得更加實用。

趙宇飛目前擔(dān)任MIT數(shù)學(xué)系的助理教授。

正是基于他在這方面的研究，趙宇飛在2018年獲得了組合學(xué)界每兩年頒發(fā)一名的柯尼希獎(K?nig Prize)，MIT未來科學(xué)家獎，隨后獲得了2019年斯隆獎(Sloan Research Fellowship)，2021年美國國家科學(xué)基金會青年學(xué)者獎(NSF CAREER Award)。趙宇飛帶領(lǐng)的學(xué)生Ashwin Sah對拉姆齊數(shù)問題的突破，在2020年受到媒體廣泛關(guān)注。

他認為，在圖數(shù)據(jù)越來越龐大的當(dāng)下，「大圖」的世界是無限的，而圖正則原理、圖極限等數(shù)學(xué)方法，正是解決圖數(shù)據(jù)問題的重要工具，值得相關(guān)的計算機科學(xué)家們著重關(guān)注。

趙宇飛，麻省理工學(xué)院數(shù)學(xué)系助理教授，SIAM Dénes K?nig 獎（2018 年）、麻省理工學(xué)院科學(xué)未來獎（2018 年）和斯隆獎（2019 年），美國國家科學(xué)基金會青年學(xué)者獎（2021年）。

圖（Graphs）和網(wǎng)絡(luò)（Networks），是許多科學(xué)和數(shù)學(xué)研究的語言和基礎(chǔ)，從生物網(wǎng)絡(luò)到算法，再到機器學(xué)習(xí)應(yīng)用程序，再到純數(shù)學(xué)。隨著圖和網(wǎng)絡(luò)變得越來越大，開發(fā)分析大規(guī)模圖（Large Graphs）的數(shù)學(xué)工具，并對這些工具進行理解，變得越發(fā)重要。

1
圖正則引理

我在大圖（Large Graphs）領(lǐng)域的研究，源于安德烈·塞邁雷迪（Endre Szemerédi）在20世紀 70 年代的工作，塞邁雷迪也正是因為在這方面的工作獲得了阿貝爾獎（Abel Prize）。該獎項是數(shù)學(xué)界的終身獎，等同于諾貝爾獎。塞邁雷迪是組合數(shù)學(xué)的巨人，他的想法至今仍然在整個領(lǐng)域有著深刻影響。

Fig1：2012年榮獲阿貝爾獎的安德烈·塞邁雷迪

塞邁雷迪對 20世紀30年代保羅·埃爾德什（Paul Erd?s）和圖帕爾·圖蘭（Pál Turán）的一個古老等差數(shù)列猜想很感興趣：

如果你取自然數(shù)的一個無限子集，只要這個集足夠大，具體說它占有所有自然數(shù)的一定比例，那么你在這個集合中總能找到任意長的等差數(shù)列。

例如，如果我們在大概每百萬個自然數(shù)中取一個，構(gòu)成一個集合，那么可以推測，我們在這個集合里能夠找到長度為 k 的等差序列（包含k個間距相等的數(shù)字），不管這個 k 是多大。

但實際發(fā)現(xiàn)，證明這個猜想并不是一件容易的事情。

在塞邁雷迪的工作之前，只有20世紀50年代克勞斯·羅斯（Klaus Roth，菲爾茲獎獲得者）在這一問題上做出了部分進展，即人們可以找到長為3的等差數(shù)列。

在塞邁雷迪破解整個問題、解決“埃爾德什-圖蘭”猜想之前，哪怕能找到長度為4的等差數(shù)列都很難。

如今他對這一問題的結(jié)果，被稱為塞邁雷迪定理 [1]。他的這一結(jié)論深刻且復(fù)雜。通過這項工作，塞邁雷迪在數(shù)學(xué)上引入了一些重要的思想，其中之一便是圖正則性引理[2]。

Fig2：塞邁雷迪定理（維基百科）

塞邁雷迪的圖正則引理是一個強大的結(jié)構(gòu)性工具幫助我們分析非常大的圖。粗略地說，正則引理就是，

如果給我們一個大圖，且不管這張圖是什么樣子，我們總可以將圖的頂點分成幾個集合，使圖的邊看起來在兩兩集合間按照概率隨機的連接。而在不同的兩個頂點集之間，邊的概率（密度）可能不同。

Fig3：圖正則引理中對邊密度的定義（維基百科）

例如，有五個互斥的頂點集合 A、B、C、D、E；在 A 和 B 之間，圖看起來像一個概率為 0.2 的隨機圖；在 A 和 C 之間，圖看起來像邊概率為 0.5 的隨機圖，依此類推。

Fig4：圖正則引理下關(guān)于的頂點劃分的圖示

需要強調(diào)的一點是，只要容錯度（error tolerance）固定，劃分產(chǎn)生的頂點集合的數(shù)量不會隨著圖的大小而增加。這個性質(zhì)使得圖正則引理對于非常大的圖特別有用。

塞邁雷迪的圖正則引理為我們提供了一個圖的劃分，這在許多應(yīng)用中都非常有用。這個工具如今已成為現(xiàn)代組合學(xué)研究的核心技術(shù)。

一個類比是信號處理中的信噪比分解。圖的「信號」是它頂點劃分以及它們之間邊密度這些數(shù)據(jù)；「噪聲」則是類隨機分布的邊的偏移。

塞邁雷迪通過這種分解的視角來看待圖論的想法，對數(shù)學(xué)產(chǎn)生了深遠的影響。這種分解現(xiàn)在被稱為「結(jié)構(gòu)與偽隨機」(菲爾茲獎得主陶哲軒推廣的術(shù)語)。它已經(jīng)遠遠超出了圖理論的范疇。

菲爾茲獎得主蒂莫西·高爾斯（Timothy Gowers）將這一方法擴展到了數(shù)論中的「高階傅里葉分析」。

正則性方法后來被擴展到了超圖理論。

2
圖極限

洛瓦茲·拉茲洛（László Lovász）最近獲得了2021年的阿貝爾獎，在過去的幾十年里，他和他的合作者一直致力于發(fā)展一個圖極限理論（Theory of Graph Limits）[3]。

Fig5：洛瓦茲·拉茲洛（László Lovász）

洛瓦茲的圖極限為我們提供了強大的工具，從數(shù)學(xué)分析的角度來描述大型圖，其應(yīng)用范圍很廣，從組合學(xué)到概率，到機器學(xué)習(xí)，都有相應(yīng)的應(yīng)用。

Fig6：洛瓦茲·拉茲洛關(guān)于圖極限的書

圖也會有極限嗎？我們來和數(shù)字集合做個類比。假設(shè)我們對數(shù)的了解僅限于有理數(shù)，我們也可以研究許多數(shù)學(xué)問題：事實上，我們可以通過將每一個無理數(shù)表達為一串有理數(shù)數(shù)列的極限。但是如果每次我們想對無理數(shù)都使用這種方式表達的話，將會很麻煩。幸運的是，實數(shù)的發(fā)明填補了數(shù)軸上的空白并解決了這個問題。在這里，實數(shù)其實就是有理數(shù)的極限。

同樣，圖是類似于有理數(shù)的離散對象。一連串的圖也可以收斂為一個極限對象（“一連串圖的收斂意味著什么？”這是一個引人入勝的話題，本文不作詳述）。這些極限對象稱為“圖極限”，也稱為“graphons”。

圖極限實際上是分析上的簡單對象，它可以描繪成正方形內(nèi)的灰度（grayscale）矩陣，或表示為從單位方塊映射到單位區(qū)間的函數(shù)（“graphon”這個詞是“graph”和“function”兩個詞的合并）。給定一個圖序列，我們可以將每個圖按照點與點的連接關(guān)系表示為一個鄰接矩陣，并將該矩陣畫成像素為黑或白的圖像，如下圖所示。

隨著圖變得越來越大，這個圖序列看起來越來越接近一張圖像，而且這圖片可以具有各種灰度而非只有純黑與純白。這個最終的圖像就是圖極限的示例。（實際上，這里我忽略了一些微小之處，例如在取極限之前可以置換頂點的順序。）

Fig7：一個圖，其鄰接矩陣的像素圖像，及其圖極限

Fig8：左圖為右邊的圖極限所取樣的圖（鄰接矩陣的像素圖像）

(圖7& 圖8源自洛瓦茲的書)

反過來，給定圖極限，我們可以將其用作隨機圖的生成模型。當(dāng)頂點數(shù)量增加時，這種隨機圖會收斂到給定的圖極限。這種隨機圖模型推廣了隨機塊模型(stochastic block model)。

在機器學(xué)習(xí)和統(tǒng)計學(xué)中有一個的問題是，給定由這一隨機圖模型中得到的一序列樣本時，如何反過來找到其原始的圖極限。關(guān)于這個問題有許多活躍的研究（盡管這不是本人主要的研究課題）。

圖極限理論背后的數(shù)學(xué)基礎(chǔ)，特別是它們存在性的證明，關(guān)鍵點就在于塞邁雷迪的圖正則引理。所以這兩個主題是相互交織在一起的。

3
稀疏圖

圖正則引理和圖極限都有一個重大的局限：它們只能處理稠密圖（dense graphs），即邊數(shù)為點數(shù)二次方量階的圖，換句話說，即邊密度要大于某個常數(shù)才行。

這種局限影響了它在純數(shù)學(xué)以及應(yīng)用數(shù)學(xué)中的使用，因為現(xiàn)實生活中的網(wǎng)絡(luò)通常都是稀疏的。因此，人們希望能開發(fā)出一些能更好適用于稀疏圖的圖論工具，但稀疏圖具有更大的可變空間，這也導(dǎo)致了其數(shù)學(xué)上的復(fù)雜性。

我的一個核心研究課題正是，解決如何將大圖上的數(shù)學(xué)工具從稠密情形擴展到稀疏情形這一問題。

例如，我的一項工作是，將塞邁雷迪的圖正則方法從稠密圖擴展到稀疏圖；我還發(fā)展了稀疏圖極限的新理論。這些結(jié)果讓我們更好的了解了稀疏圖的世界以及它們的復(fù)雜性。

我在將圖正則引理擴展到稀疏圖方面做了大量工作。

與戴維·康倫（David Conlon）和雅各布·?？怂梗↗acob Fox）[4] 一起，我們通過新的圖論視角，簡化了本·格林（Ben Green）和陶哲軒著名定理的證明，即素數(shù)包含任意長的等差數(shù)列 [5]。事實證明，盡管這是一個數(shù)論的結(jié)果，但其證明的核心部分涉及稀疏圖和超圖的組合。運用新的工具，我們可以在比“格林-陶”的原始工作更簡單一個設(shè)定中計算稀疏圖中的圖樣（pattern）。

在另一個方面，我們最近與本尼·蘇達科夫（Benny Sudakov）一起，在不包含4環(huán)（4-cycles）的圖中開發(fā)了稀疏正則性方法，而這些圖必然是稀疏的[6]。

在稀疏圖極限方面的工作我與克里斯蒂安·博格斯（Christian Borgs）、亨利·科恩（Henry Cohn）以及詹妮弗·圖爾·查耶斯（Jennifer Chayes） [7] 一起，開發(fā)了一種新的稀疏圖極限 Lp 理論。我們受具有冪律度分布（power low degree distributions）的稀疏圖模型的啟發(fā)，這些模型在網(wǎng)絡(luò)理論中很受歡迎，因為它們在現(xiàn)實世界中普遍存在。我們的工作其實是以貝拉·波羅巴斯(Bela Bollobás) 和奧利弗·里奧丹（Oliver Riordan）[8] 的思想為基礎(chǔ)，他們最先對稀疏圖極限進行了系統(tǒng)研究。波羅巴斯和里奧丹在他們的論文中提出了許多猜想。不過，我和我的博士生 Ashwin Sah、Mehtaab Sawhney 和 Jonathan Tidor 發(fā)現(xiàn)了一個反例，證明這些猜想都是錯的[9]。

這些結(jié)果說明了稀疏圖極限的世界是豐富多彩的。

4
圖論和加性組合

我研究的另一個核心主題是，找到一個橋梁將圖論和加性組合兩個領(lǐng)域連接起來，這樣便可以讓一個領(lǐng)域的想法和技術(shù)遷移到另一個領(lǐng)域。

加性組合是一門涉及組合學(xué)和數(shù)論的交叉方向，塞邁雷迪定理和 “格林-陶”定理都是屬于這一方向，它們都是在數(shù)集中尋找圖樣（pattern）。

2017年，我開始在 MIT 任教。當(dāng)時我開設(shè)了一門面向研究生的數(shù)學(xué)課程，叫做“圖論和加性組合”，向?qū)W生介紹了這兩個美妙的科目，并著重介紹怎樣將這兩個領(lǐng)域連接起來。我很高興后來班上不少學(xué)生在這個方向做出了非常出色的研究（編者注：最為知名的是2020年趙宇飛帶領(lǐng)的本科生Ashwin Sah對拉姆齊數(shù)的研究）。

2019 年秋季，我和 MIT OpenCourseWare 合作，為這門課拍攝了講座視頻。這些視頻可以在 MIT OCW 和 YouTube （還包括Bilibili）上免費觀看。我還公開了我的課堂講義，并且正在將其編輯成教科書。

課程鏈接：

https://ocw./18-217F19

課程視頻：

-> MIT OCW：

https://ocw./courses/mathematics/18-217-graph-theory-and-additive-combinatorics-fall-2019/video-lectures/

-> YouTube：

https://www./playlist?list=PLUl4u3cNGP62qauV_CpT1zKaGG_Vj5igX

-> B站：

https://space.bilibili.com/556006423/channel/detail?cid=127140

在我的第一堂課中，我講述了圖論與加法組合之間的關(guān)聯(lián)。伊薩?！な鏍枺↖ssai Schur）在一百多年前首先觀察到了這一點。得益于過去這一世紀在這領(lǐng)域的大量研究，我們已經(jīng)看得更清楚，但仍有大量謎團尚未解決。

大圖世界，廣袤無限。

參考資料

[1] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245.

[2] Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401.

[3] László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012.

[4] David Conlon, Jacob Fox, and Yufei Zhao, Extremal results in sparse pseudorandom graphs, Adv. Math. 256 (2014), 206–290. And

David Conlon, Jacob Fox, and Yufei Zhao, A relative Szemerédi theorem, Geom. Funct. Anal. 25 (2015), 733–762. And

David Conlon, Jacob Fox, and Yufei Zhao, The Green-Tao theorem: an exposition, EMS Surv. Math. Sci. 1 (2014), 249–282.

[5] Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math.(2) 167 (2008), 481–547.

[6] David Conlon, Jacob Fox, Benny Sudakov, and Yufei Zhao, The regularity method for graphs with few 4-cycles, J. Lond. Math. Soc. (2), to appear. And

David Conlon, Jacob Fox, Benny Sudakov, and Yufei Zhao, Which graphs can be counted in C4-free graphs?, arXiv: 2106.03261.

[7] Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao, An Lp theory of sparse graph convergence II: LD convergence, quotients and right convergence, Ann. Probab. 46 (2018), 337–396.

[8] Béla Bollobás and Oliver Riordan, Metrics for sparse graphs, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge Univ. Press, Cambridge, 2009, pp. 211–287.

[9] Ashwin Sah, Mehtaab Sawhney, Jonathan Tidor, and Yufei Zhao, A counterexample to the Bollobás-Riordan conjectures on sparse graph limits, Combin. Probab. Comput., to appear.