斯隆奖得主赵宇飞：大图世界里的数学利器 | 欲善其事，先利其器

编者按：数学的理论往往先行于实际应用，在时机成熟的时候迅速成为实际应用的有力工具。

作者 | 赵宇飞

编译 | 廖璐，贾伟

例如微分几何，在1854年便有相对成熟的理论，但直到1915年爱因斯坦提出广义相对论后，人们发现物理世界竟然是4维黎曼流形，才得到物理和数学两界的广泛关注，逐渐成为物理学家理解世界的必备工具。

组合数学中的「图正则引理」，或许亦是如此。

这一引理是阿贝尔奖（Abel Prize）得主安德烈·塞迈雷迪 （Endre Szemerédi）在上世纪70年代的工作，讨论了当图（Graph）足够大时所呈现出的规律，在组合数学中具有重要的影响力。简单来讲，即一个充分大的图，一定存在我们想要的子结构；从哲学意义上讲，即一个系统不可能是完全紊乱，没有规律的。

这一引理，是理解大图（Large Graph）的重要工具。当下，伴随着数据的迅猛增加，图数据和图网络变得越来越具规模。这种情况，恰好完全属于「图正则引理」的应用范畴。如何能够更好地理解和使用这些大图数据，「图正则引理」或许正是计算机科学家一个可能趁手的利器。

来自MIT 的数学家赵宇飞，所从事的正是这样的工作，尽可能地让「图正则引理」这把利器变得更加实用。

赵宇飞目前担任MIT数学系的助理教授。

正是基于他在这方面的研究，赵宇飞在2018年获得了组合学界每两年颁发一名的柯尼希奖(König Prize)，MIT未来科学家奖，随后获得了2019年斯隆奖(Sloan Research Fellowship)，2021年美国国家科学基金会青年学者奖(NSF CAREER Award)。赵宇飞带领的学生Ashwin Sah对拉姆齐数问题的突破，在2020年受到媒体广泛关注。

他认为，在图数据越来越庞大的当下，「大图」的世界是无限的，而图正则原理、图极限等数学方法，正是解决图数据问题的重要工具，值得相关的计算机科学家们着重关注。

赵宇飞，麻省理工学院数学系助理教授，SIAM Dénes Kőnig 奖（2018 年）、麻省理工学院科学未来奖（2018 年）和斯隆奖（2019 年），美国国家科学基金会青年学者奖（2021年）。

图（Graphs）和网络（Networks），是许多科学和数学研究的语言和基础，从生物网络到算法，再到机器学习应用程序，再到纯数学。随着图和网络变得越来越大，开发分析大规模图（Large Graphs）的数学工具，并对这些工具进行理解，变得越发重要。

1

图正则引理

我在大图（Large Graphs）领域的研究，源于安德烈·塞迈雷迪 （Endre Szemerédi） 在20世纪 70 年代的工作，塞迈雷迪也正是因为在这方面的工作获得了阿贝尔奖（Abel Prize）。该奖项是数学界的终身奖，等同于诺贝尔奖。塞迈雷迪是组合数学的巨人，他的想法至今仍然在整个领域有着深刻影响。

Fig1：2012年荣获阿贝尔奖的安德烈·塞迈雷迪

塞迈雷迪对 20世纪30年代 保罗·埃尔德什 （Paul Erdős） 和图帕尔·图兰（Pál Turán） 的一个古老等差数列猜想很感兴趣：

如果你取自然数的一个无限子集，只要这个集足够大，具体说它占有所有自然数的一定比例，那么你在这个集合中总能找到任意长的等差数列。

例如，如果我们在大概每百万个自然数中取一个，构成一个集合，那么可以推测，我们在这个集合里能够找到长度为 k 的等差序列（包含k个间距相等的数字），不管这个 k 是多大。

但实际发现，证明这个猜想并不是一件容易的事情。

在塞迈雷迪的工作之前，只有20世纪50年代克劳斯·罗斯（Klaus Roth，菲尔兹奖获得者）在这一问题上做出了部分进展，即人们可以找到长为3的等差数列。

在塞迈雷迪破解整个问题、解决“埃尔德什-图兰”猜想之前，哪怕能找到长度为4的等差数列都很难。

如今他对这一问题的结果，被称为塞迈雷迪定理 [1]。他的这一结论深刻且复杂。通过这项工作，塞迈雷迪在数学上引入了一些重要的思想，其中之一便是图正则性引理[2]。

Fig2：塞迈雷迪定理（维基百科）

塞迈雷迪的图正则引理是一个强大的结构性工具帮助我们分析非常大的图。粗略地说，正则引理就是，

如果给我们一个大图，且不管这张图是什么样子，我们总可以将图的顶点分成几个集合，使图的边看起来在两两集合间按照概率随机的连接。而在不同的两个顶点集之间，边的概率（密度）可能不同。

Fig3：图正则引理中对边密度的定义（维基百科）

例如，有五个互斥的顶点集合 A、B、C、D、E；在 A 和 B 之间，图看起来像一个概率为 0.2 的随机图；在 A 和 C 之间，图看起来像边概率为 0.5 的随机图，依此类推。

Fig4：图正则引理下关于的顶点划分的图示

需要强调的一点是，只要容错度（error tolerance）固定，划分产生的顶点集合的数量不会随着图的大小而增加。这个性质使得图正则引理对于非常大的图特别有用。

塞迈雷迪的图正则引理为我们提供了一个图的划分，这在许多应用中都非常有用。这个工具如今已成为现代组合学研究的核心技术。

一个类比是信号处理中的信噪比分解。图的「信号」是它顶点划分以及它们之间边密度这些数据；「噪声」则是类随机分布的边的偏移。

塞迈雷迪通过这种分解的视角来看待图论的想法，对数学产生了深远的影响。这种分解现在被称为「结构与伪随机」(菲尔兹奖得主陶哲轩推广的术语)。它已经远远超出了图理论的范畴。

菲尔兹奖得主蒂莫西·高尔斯（Timothy Gowers）将这一方法扩展到了数论中的「高阶傅里叶分析」。

正则性方法后来被扩展到了超图理论。

2

图极限

洛瓦兹·拉兹洛（László Lovász）最近获得了2021年的阿贝尔奖，在过去的几十年里，他和他的合作者一直致力于发展一个图极限理论（Theory of Graph Limits）[3]。

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

洛瓦兹的图极限为我们提供了强大的工具，从数学分析的角度来描述大型图，其应用范围很广，从组合学到概率，到机器学习，都有相应的应用。

Fig6：洛瓦兹·拉兹洛关于图极限的书

图也会有极限吗？我们来和数字集合做个类比。假设我们对数的了解仅限于有理数，我们也可以研究许多数学问题：事实上，我们可以通过将每一个无理数表达为一串有理数数列的极限。但是如果每次我们想对无理数都使用这种方式表达的话，将会很麻烦。幸运的是，实数的发明填补了数轴上的空白并解决了这个问题。在这里，实数其实就是有理数的极限。

同样，图是类似于有理数的离散对象。一连串的图也可以收敛为一个极限对象（“一连串图的收敛意味着什么？”这是一个引人入胜的话题，本文不作详述）。这些极限对象称为“图极限”，也称为“graphons”。

图极限实际上是分析上的简单对象，它可以描绘成正方形内的灰度（grayscale）矩阵，或表示为从单位方块映射到单位区间的函数（“graphon”这个词是“graph”和“function”两个词的合并）。给定一个图序列，我们可以将每个图按照点与点的连接关系表示为一个邻接矩阵，并将该矩阵画成像素为黑或白的图像，如下图所示。

随着图变得越来越大，这个图序列看起来越来越接近一张图像，而且这图片可以具有各种灰度而非只有纯黑与纯白。这个最终的图像就是图极限的示例。（实际上，这里我忽略了一些微小之处，例如在取极限之前可以置换顶点的顺序。）

Fig7：一个图，其邻接矩阵的像素图像，及其图极限

Fig8：左图为右边的图极限所取样的图（邻接矩阵的像素图像）

(图7& 图8源自洛瓦兹的书)

反过来，给定图极限，我们可以将其用作随机图的生成模型。当顶点数量增加时，这种随机图会收敛到给定的图极限。这种随机图模型推广了随机块模型(stochastic block model)。

在机器学习和统计学中有一个的问题是，给定由这一随机图模型中得到的一序列样本时，如何反过来找到其原始的图极限。关于这个问题有许多活跃的研究（尽管这不是本人主要的研究课题）。

图极限理论背后的数学基础，特别是它们存在性的证明，关键点就在于塞迈雷迪的图正则引理。所以这两个主题是相互交织在一起的。

3

稀疏图

图正则引理和图极限都有一个重大的局限：它们只能处理稠密图（dense graphs），即边数为点数二次方量阶的图，换句话说，即边密度要大于某个常数才行。

这种局限影响了它在纯数学以及应用数学中的使用，因为现实生活中的网络通常都是稀疏的。因此，人们希望能开发出一些能更好适用于稀疏图的图论工具，但稀疏图具有更大的可变空间，这也导致了其数学上的复杂性。

我的一个核心研究课题正是，解决如何将大图上的数学工具从稠密情形扩展到稀疏情形这一问题。

例如，我的一项工作是，将塞迈雷迪的图正则方法从稠密图扩展到稀疏图；我还发展了稀疏图极限的新理论。这些结果让我们更好的了解了稀疏图的世界以及它们的复杂性。

我在将图正则引理扩展到稀疏图方面做了大量工作。

与戴维·康伦（David Conlon）和 雅各布·福克斯（Jacob Fox）[4] 一起，我们通过新的图论视角，简化了本·格林（Ben Green）和陶哲轩著名定理的证明，即素数包含任意长的等差数列 [5]。事实证明，尽管这是一个数论的结果，但其证明的核心部分涉及稀疏图和超图的组合。运用新的工具，我们可以在比“格林-陶”的原始工作更简单一个设定中计算稀疏图中的图样（pattern）。

在另一个方面，我们最近与本尼·苏达科夫（Benny Sudakov） 一起，在不包含4环（4-cycles）的图中开发了稀疏正则性方法，而这些图必然是稀疏的[6]。

在稀疏图极限方面的工作我与克里斯蒂安·博格斯（Christian Borgs）、亨利·科恩（Henry Cohn）以及詹妮弗·图尔·查耶斯（Jennifer Chayes） [7] 一起，开发了一种新的稀疏图极限 Lp 理论。我们受具有幂律度分布（power low degree distributions）的稀疏图模型的启发，这些模型在网络理论中很受欢迎，因为它们在现实世界中普遍存在。我们的工作其实是以贝拉·波罗巴斯(Bela Bollobás) 和 奥利弗·里奥丹（Oliver Riordan）[8] 的思想为基础，他们最先对稀疏图极限进行了系统研究。波罗巴斯和里奥丹在他们的论文中提出了许多猜想。不过，我和我的博士生 Ashwin Sah、Mehtaab Sawhney 和 Jonathan Tidor 发现了一个反例，证明这些猜想都是错的[9]。

这些结果说明了稀疏图极限的世界是丰富多彩的。

4

图论和加性组合

我研究的另一个核心主题是，找到一个桥梁将图论和加性组合两个领域连接起来，这样便可以让一个领域的想法和技术迁移到另一个领域。

加性组合是一门涉及组合学和数论的交叉方向，塞迈雷迪定理和 “格林-陶”定理都是属于这一方向，它们都是在数集中寻找图样（pattern）。

2017年，我开始在 MIT 任教。当时我开设了一门面向研究生的数学课程，叫做“图论和加性组合”，向学生介绍了这两个美妙的科目，并着重介绍怎样将这两个领域连接起来。我很高兴后来班上不少学生在这个方向做出了非常出色的研究（编者注：最为知名的是2020年赵宇飞带领的本科生Ashwin Sah对拉姆齐数的研究）。

2019 年秋季，我和 MIT OpenCourseWare 合作，为这门课拍摄了讲座视频。这些视频可以在 MIT OCW 和 YouTube （还包括Bilibili）上免费观看。我还公开了我的课堂讲义，并且正在将其编辑成教科书。

课程链接：

https://ocw.mit.edu/18-217F19

课程视频：

-> MIT OCW：

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

-> YouTube：

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

-> B站：

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

在我的第一堂课中，我讲述了图论与加法组合之间的关联。伊萨海·舒尔（Issai Schur）在一百多年前首先观察到了这一点。得益于过去这一世纪在这领域的大量研究，我们已经看得更清楚，但仍有大量谜团尚未解决。

大图世界，广袤无限。

参考资料

[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.

AI科技评论

聚焦AI前沿研究，关注AI青年成长

1892篇原创内容

公众号