​

• 标题：

  Large networks and graph limits

• 作者：

  Laszlo Lovasz

• 原文链接：

  https://web.cs.elte.hu/~lovasz/kurzusok/hombook-almost-final.pdf

  
  

译者：近日重读Lovasz的《large networks and graph limits》,又一次惊叹这本书的神奇，那么多看似无关的问题居然奇妙的联系到了一起！翻译了前言，希望把这本书推荐给相关学者和其他感兴趣的朋友。

前言

2003年，在华盛顿雷德蒙德微软研究院理论组，几个月间三个同事问了我三个问题。Michael Freedman（译者注：即Mike Freedman,数学家，菲尔茨奖获得者）正在研究如何设计基于代数拓扑方法的量子计算机，想知道哪些图参数（有限图上的函数）可以表示为统计物理学中的模型的配分函数（partition funtions）。Jennifer Chayes（译者注：现任UCLA信息学院院长）正在研究互联网模型，问图序列（区别于数字序列）是否存在“极限分布”的概念。Vera T. Sos，来自布达佩斯的访问教授（译者注：数论和组合学家，数学家Turan的妻子）对拟随机性（quasirandomness）及其与正则定理的联系感兴趣。她建议推广关于拟随机图的结果到多类型拟随机图（multitype quasirandom graph）。原来，这些问题非常紧密相关，为回答这些问题，我们开发出了一些新的想法，并且我接下来几年的大部分研究都是基于这些新想法。

Jennifer的问题使我回想起了我以前的一些结果: 通过同态数来刻画图，以及我与Paul Erdos和Joel Spencer的另一篇论文，在那篇论文中我们研究了同态数和他们的极限。使用同态数，Mike Freedman，Lex Schrijver和我在几个月后找到了Mike的问题的答案。解决的方法是图代数（graph algebras）方法。同时，图代数提供了回答Vera的问题的工具。我与Christian BorgsJen nifer Chayes，Lex Schrijver，Vera Sos，Balazs Szegedy和Kati Vesztergombi一起，开始研究图同态的代数理论和图序列的收敛性及其极限的分析理论。这本书将尝试阐述我们的工作。

找到上述三个问题之间意想不到的联系是有趣的，令人兴奋。但很快我们发现这些方法和结果与数学分支中许多其他研究相关。几年前，Itai Benjamini和Oded Schramm定义了度有界图的序列的收敛性，并为其构造了极限对象（至少在研究初期，我们的主要兴趣对象是稠密图的收敛理论）（译者注：区别于稠密图，度有界的图是稀疏图）。类似的想法David Aldous甚至更早就提出了。稠密图和度有界图的极限理论引发了许多类似的问题和结果，每一个新的问题和结果的出现都让我们更好的理解了这一系列问题。

统计物理学处理的是规模非常大的图及其局部和全局性质，事实证明，在我们这个主要由图论学家组成的（非正式）研究小组中拥有两名统计物理学家（Jennifer和Christian）是极其富有成果的。这样虽然加重了我们理解其他人的目标和方法的难度，但最后却是获得丰富结果的关键。

不久后发现的另一个重要联系是计算机科学中的性质测试理论（property testing），该理论多年前由Goldreich，Goldwasser和Ron提出。可以将其视为对图（而不是对数字）的统计，概率和统计成为我们的主要工具。

这些结果最重要的应用领域之一是极值图论。Szemeredi的正则引理是研究稠密图的极值理论的基本工具，这个引理对我们的研究也至关重要。我们希望图的极限理论为正则引理提供最短且最一般表述（graphon空间的紧性），作为正则引理为我们提供基本工具的回报。新理论最令人兴奋的结果可能是它给出涉及大图算法和极值图论的一般问题的精确表述，并且通常还对这些问题给出了确切的答案。与我们同时，Razborov独立开发了紧密相关的旗代数（flag algebras）理论，它解决了极值图论中几个长期的公开问题。

A realization of an exchangeable random graph defined by a graphon

谈论极限当然意味着分析，对于我们图论学者中的一些人来说，这意味着努力学习必要的分析工具（主要是测度论和泛函分析，甚至还有一些微分方程)。即使对于某些可以纯粹用图论语言来陈述和证明的结果，涉及分析也具有优势的：许多定义和证明用分析语言陈述起来都更短和更显然。当然，组合困难也没有消失：有时它们会被分析难题所取代。其中有几个问题在技术上是自然的：我们考虑的集合是Lebesgue / Borel可测的吗？在一个涉及下确界(infimun)的定义中，是否可以达到（attained）？通常这些问题并不是为了开发相关理论的提出的。恰恰相反，可测性通常具有组合意义，这使得这种关系真正令人兴奋。

这些问题与代数也有一些有趣的联系。Balazs Szegedy解决了一个关于刻画同态函数的对偶的问题，通过证明，他建立了其与代数表示论的深厚联系。Schrijver和其他人后来进一步发展了这种联系。对此理论的另一个推广催生了范畴的组合理论，除了一些零星的结果外，范畴的组合理论以前从未被研究过。度有界图的极限理论也与代数有非常紧密的联系：有限生成无限群（finitely generated infinite groups）通过它们的Cayley图表示为度有界无限图，并且将它们表示为有限图的极限此前已在群论中研究（称为sofic groups）。

这些与数学不同的部分之间的联系使得把这本书写的易读变得非常困难。一种可能的选择是专注于图论，而不谈论来自图论以外的动机，并简述或忽略依赖于大量其他数学工具的证明。我觉得这样的方法会隐藏我认为该理论的最令人兴奋的特征，即它与数学其他部分（经典和非经典）的丰富联系。所以我决定尽我所能解释这些联系。读者可能会跳过几个他们不喜欢或没有适当的背景的部分，但也许这些部分中的特殊意味(flavor)是可以留下印象的。

这本书由五个主要部分构成。首先，非正式介绍大型网络的数学挑战。我们提出上面提到的“一般性问题”，并尝试使用相对初等的数学方法给出非正式答案，读了这部分，读者会发现在本书的其余部分中开发的那些更高等方法是必要的。

第二部分包含同态函数的代数处理和其他图参数。两个主要的代数构造（连接矩阵和图代数(connection matrices and graph algebras））也将在后面部分发挥重要作用，它们还给看似完全混杂的“图参数”集“点亮了一盏灯”。

在最长的也许是自身最完整的第三部分中，我们发展了稠密图的收敛序列理论，并且给出了极值图论和图算法的应用。

第四部分包含度有界图的收敛序列的类似理论。这个理论比密集的情况更难，目前研究有限，但它具有更重要的应用，不仅因为现实生活中出现的大多数网络是稀疏的，还因为其与有限生成群理论的联系。关于这个课题的研究在我最近几个月里可能一直是最活跃的，所以这个话题是一个“正在进行的目标”，而在这里，我最难描绘我们会在理解和解释新结果的哪个地方停下来。

第五部分涉及推广。我们可以尝试发展适用于几乎所有类型的有限结构的极限理论。在非常任意的选择下，我们只讨论边着色模型和范畴的推广，并在III and IV部分中对关于超图的理论进行了比较浅层的，深度远小于图的讨论。

我在附录中加入了多个不同数学主题的标准内容，但是由于本书材料在数学中的联系广泛，因此很少有读者会熟悉所有这些主题。

导致本书可能太长的因素之一是我尝试举出许多图参数、图序列、极限对象等的例子。其中一些例子对于某些读者可能是显然的，而对于其他一些读者可能太难， 这取决于读者的背景。由于本书关于此主题的第一本专著，我觉得这些的例子将帮助读者消化这些非常多样化的材料。

此外，我还在本书中加入了许多习题。通常一个的投机取巧的方式是把很多材料通过习题的形式挤入书中。但是（老实说）我确实尝试寻找一些我希望数学系研究生能够在不需要没有太大的努立下解决的问题。

致谢

我的一些论文是构成本书的基础，我非常感激我的这些论文的合著者Christian Borgs, Jennifer Chayes, Michael Freedman,Lex Schrijver，Vera Sos，Balazs Szegedy和Kati Vesztergombi在我们共同工作期间分享了他们想法、知识和热情、建议和极为有用的批评。微软研究院的的创意氛围和合作精神使这一研究项目的成功开始成为可能。很高兴在最后完成润色这本书时再次来到雷德蒙德。作者感谢ERC基金（编号227701），OTKA 基金(编号CNK 77780）的支持和在撰写本书大部分内容时普林斯顿高等研究所的热情招待。

我的妻子Kati Vesztergombi不仅为内容做出了贡献，而且始终提供宝贵的专业，技术和个人帮助。在研究的各个阶段以及撰写本书时，许多其他同事非常无私地提供了他们的专业知识和建议。我特别感谢Miklos Abert，Noga Alon，Endre Csoka，Gabor Elek，Guus Regts，Svante Janson，David Kunszenti-Kovacs，Gabor Lippner，Russell Lyons，Jarik Nesetril, Yuval Peres，Oleg Pikhurko，已故的Oded Schramm，Miki Simonovits，Vera Sos，Kevin Walker, and Dominic Welsh。没有他们的兴趣、鼓励和帮助，我将无法完成我的工作。

译者感谢西北工业大学的张胜贵老师和西北农林科技大学的林开亮老师为译文提的宝贵建议！