1. 主要结论的介绍和说明

图极限关注的是图的极限分析. 考虑以下两个示例, 它们展现了有理数集和图之间的潜在平行关系:

例 1.1. 对于 $x\in [0,1]$, $x^3-x$ 的最小值点为 $x=$ $1/\sqrt{3}$. 但是如果我们将范围限制在 $\mathbb{Q}$ (假装我们不知道实数) , 一种表达这个最小值点的方法是找到一个收敛到 $1/\sqrt{3}$ 的有理数序列 $x_1,x_2,\dots$.

例 1.2. 给定 $p\in (0,1)$, 在所有边密度为 $p$ 的图中我们希望最小化 $C_4$ 的密度. 根据定理 1.0.1 我们知道, $C_4$ 密度最小值是 $p^4$. (可以通过一系列拟随机图达到, 而单个有限图无法达到这个最小值. )

我们可以将所有图的集合视为一组离散对象 (类似于 $\mathbb{Q}$) , 并寻求他的 “完备空间” (类似于 $\mathbb{R}$) .

定义 1.3. 一个 graphon (“graph function”) 是一个对称 ¹的可测函数 $W:[0,1{]}^2\to [0,1]$.

笔记 1.4. 定义 1.3 可以推广到 $\Omega \times \Omega \to [0,1]$, 其中 $\Omega$ 是任何可测概率空间. 但简单起见, 我们通常令 $\Omega =[0,1]$ (实际上, 大多数 “好” 的可测概率空间都可以用 $[0,1]$ 表示) . 函数的值域也可以推广到 $\mathbb{R}$, 在这种情况下, 我们将把函数称为核 (kernel) . 请注意这种命名在文献中并不总是一致的.

graphon 可以看作是一种广义类型的图. 事实上, 我们可以将任何图转换为 graphon, 转换后我们可以试着想象一些图序列的极限应该是什么样子.

例 1.5. 考虑一个半图 $G_n$, 这是一个二分图, 其中一个部分标记为 $1,2,\dots ,n$, 另一个部分标记为 $n+1,\dots ,2n$ , 顶点 $i$ 和 $n+j$ 连通当且仅当 $i\le j$. 如果我们将邻接矩阵 $\mathrm{Adj}\left(G_n\right)$ 视为 $0/1$ 位图, 我们可以定义 graphon $W_{G_n}:[0,1{]}^2\to [0,1]$ (由 $(2n{)}^2$ 个大小为 $1/(2n)\times 1/(2n)$ 的 “像素” 组成) . 当 $n$ 趋于无穷大时, graphon (逐点) 收敛到一个函数, 如图 ?? 所示.

(...) $W_{G_n}$ 的图 (n = 4) 和 $n$ 趋于无穷大

我们可以很容易的概括这种将图转换为 graphon 的过程.

定义 1.6. 给定一个有 $n$ 个顶点 (标记为 $1,\dots ,n$) 的图 $G$, 我们将其对应的 graphon 定义为 $W_G:[0,1{]}^2\to [0,1]$. 该 graphon 将 $[0,1]=I_1\cup I_2\cup \cdots I_n$ 等分并且 $\lambda \left(I_i\right)=1/n$ , 满足对于 $(x,y)\in I_i\times I_j$, 如果 $i$ 和 $j$ 在 $G$ 中连接则 $W(x,y)=1$ , 否则为 0 . ( $\lambda (I)$ 是 $I$ 的勒贝格测度. )

但是, 随着我们分析更多的示例, 我们发现使用示例 1.5 中逐点的极限通常不足以满足我们的目的.

例 1.7. 考虑任何边密度为 $1/2$ (顶点数接近无穷大) 的随机 (或伪随机) 图序列, 那么极限 (应该) 接近常值函数 $W=$ $1/2$.

例 1.8. 考虑一个完全二部图 $K_{n,n}$, 其中两部分分别是奇数标号顶点和偶数标号顶点. 由于邻接矩阵看起来像棋盘格, 我们可能希望其极限看起来也是常值函数 $1/2$ , 但事实并非如此: 如果我们将两部分标号改为 $1,\dots ,n$ 和 $n+1,\dots ,2n$, 则我们看到 graphon 实际上应该收敛到 $2\times 2$ 的棋盘.

(...)$W_{K_{n,n}}$ 和 $W_{K_{n,n}}$ 的两个可能的图极限, $n$ 趋于无穷大

上面的例子表明我们需要在我们的 graphon 定义中注意重新标记顶点.

定义 1.9. 从 $H$ 到 $G$ 的图同态是一个映射 $\varphi :V(H)\to V(G)$ , 满足 $uv\in E(H)$ 当且仅当 $\varphi (u)\varphi (v)\in E(G)$. 令 $\mathrm{Hom}(H,G)$ 是所有此类同态的集合, 并令 $\mathrm{hom}(H,G)=|\mathrm{Hom}(H,G)|$. 定义同态密度为$$t(H,G)=\frac{\mathrm{hom}(H,G)}{|V(G){|}^{|V(H)|}}$$同态密度等于一个均匀随机映射是图同态的概率.

例 1.10.

•	$\mathrm{hom}\left(K_1,G\right)=|V(G)|$
•	$\mathrm{hom}\left(K_2,G\right)=2|E(G)|$
•	$\mathrm{hom}\left(K_3,G\right)$ 是 $G$ 中三角形个数的 6 倍.
•	$\mathrm{hom}\left(G,K_3\right)$ 是对 $G$ 顶点 3 着色的方案数 (要保证相邻顶点的颜色不同) .

笔记 1.11. 请注意, 因为同态可以是非单射的, 所以从 $H$ 到 $G$ 的同态并不完全对应于 $G$ 内的子图 $H$ 的副本. 由于非单射同态的数量最多贡献 $O_H\left({|V(G)|}^{|V(H)-1|}\right)$ , 当 $H$ 固定且 $n\to \infty$ 时, 非单射同态数量是相对少的.

定义 1.12. 给定对称可测函数 $W:[0,1{]}^2\to \mathbb{R}$, 定义$$t(H,W)={\int }_{[0,1{]}^{|V(H)|}}\prod _{ij\in E(H)}W\left(x_i,x_j\right)\prod _{i\in V(H)}d{x}_i$$注意, 对于每个 $G$ 和 $H$, $t(H,G)=t\left(H,W_G\right)$.

例 1.13. 当 $H=K_3$ 时, 我们有$$t\left(K_3,W\right)={\int }_{[0,1{]}^3}W(x,y)W(y,z)W(z,x)dxdydz$$这可以看作是 $W$ 的 “三角形密度”.

我们现在可以定义图收敛以及图极限.

定义 1.14. 我们说一图序列 $G_n$ (或一个 graphon 序列 $W_n$) 收敛如果对每个图 $H$, $t\left(H,G_n\right)$ (或 $t\left(H,W_n\right)$) 随 $n$ 趋于无穷大收敛. 如果对于每个图 $H$, $t\left(H,G_n\right)$ (或 $t\left(H,W_n\right)$) 收敛, 则序列收敛到 $W(H,W)$ .

一个自然的问题是图的收敛序列是否有 “极限”. (剧透一下, 确实存在. ) 我们还应该考虑我们以这种方式定义的 “极限” 是否与我们期望的一致. 为此, 我们需要定义图之间 “距离” 的概念.

我们尝试将 $G$ 和 $G^{\prime }$ 之间的距离定义为 ${\sum }_k{2}^{-k}\left|t\left(H_k,G\right)-t\left(H_k,G^{\prime }\right)\right|$, 其中 $H_1,H_2,\dots$ 是所有可能的图. (之所以添加了 $2^{-k}$ 是为了确保总和收敛到 0 和 1 之间的数字. ) 这在与定义 1.14 中的收敛概念是同胚的, 所以这种定义没什么用.

另一种可能的想法是考虑两个图之间的编辑距离 (需要边的编辑次数) , 通过因子 $1/|V(G){|}^2$ 进行归一化. 但这种方法也不是很有用, 因为任意两个 $G(n,1/2)$ 之间的距离约为 $1/4$, 但我们希望它们之间有 $o(1)$ 的距离.

尽管上面两种定义都行不通, 但这激励我们回顾之前对随机图的讨论, 我们考虑图接近常数 $p$ (即与 $G(n,p)$ 相似) 的情况. 回忆定理! ! 4.1 中的 DISC , 我们希望图足够随机时 $\left|e(X,Y)-p|X||Y|\right|$ 很小. 借助这个想法, 我们可以这样比较两个图之间的距离: 直观地说, $\left|e_G(X,Y)-e_{G^{\prime }}(X,Y)\right|/n^2$ 是否对于所有子集 $X$ 和 $Y$ 来说都很小. 为了说清楚这一点, 我们需要更多的定义.

定义 1.15. $W:[0,1{]}^2\to \mathbb{R}$ 的切割范数定义为$$\Vert W{\Vert }_{\square }=\underset{S,T\subseteq [0,1]}{\sup }\left|{\int }_{S\times T}W\right|$$其中 $S$ 和 $T$ 是可测集.

我们还定义了一些相关的范数.

定义 1.16. 对于 $W:[0,1{]}^2\to \mathbb{R}$, 将 $L^p$ 范数定义为 $\Vert W{\Vert }_p={\left(\int |W{|}^p\right)}^{1/p}$. 定义 $L^{\infty }$ 范数作为 $m$ 的下界, 其中 $m$ 满足: 集合 $\{(x,y):W(x,y)>m\}$ 的测度为零. (这也称为 $W$ 的本质上确界) .

定义 1.17. 如果 $\lambda (A)=\lambda \left({\varphi }^{-1}(A)\right)$ 对于所有可测集 $A\subseteq [0,1]$ 成立, 我们说 $\varphi :[0,1]\to [0,1]$ 是保测 (measure-preserving) 的.

例 1.18. 函数 $f(x)=x+1/2\mathrm{mod}1$ 显然是保测的. $f(x)=2x\mathrm{mod}1$ 也是保测的 (可能不太明显) . 虽然每个区间通过 $f$ 被扩大了 2 倍, 但每个点都有两个原像, 所以这两种效果相互抵消. (...)$f(x)=2x\mathrm{mod}1$

定义 1.19. 记 $W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))$ (直观地说, 相当于重新标记顶点) . 我们定义切割距离$${\delta }_{\square }(U,W)=\underset{\varphi }{\inf }{\Vert U-W^{\varphi }\Vert }_{\square }$$其中 $\varphi$ 是一个保测的双射.

对于图 $G,G^{\prime }$, 定义切割距离 ${\delta }_{\square }\left(G,G^{\prime }\right)={\delta }_{\square }\left(W_G,W_{G^{\prime }}\right)$ 我们将图和 graphon 之间的切割距离定义为 ${\delta }_{\square }(G,U)={\delta }_{\square }\left(W_G,U\right)$

请注意, $\varphi$ 与顶点置换并不完全相同: 它也允许拆分顶点或覆盖不同的顶点. 相比于直接考虑图同构, 这种做法使我们能更好地优化最小差异/切割范数.

笔记 1.20. 定义中的 inf 不一定总能取到. 假设 $U(x,y)=xy$ 且 $W=U^{\varphi }$, 其中 $\varphi (x)=2x\mathrm{mod}1$. 因为 $\varphi$ 不是双射的, 对于任何 ${\varphi }^{\prime }$, 我们不能保证 ${\Vert U-W^{{\varphi }^{\prime }}\Vert }_{\square }=0$ (尽管切割距离为 0 ) .

现在我们介绍图极限理论中的主要定理, 我们将在后面给出证明. 首先, 人们可能会怀疑使用切割 (距离) 度量存在收敛的替代定义, 但事实证明该定义等价于定义 1.14.

定理 1.21 (收敛等价定理 Borgs, Chayes, Lovász, Sós, and Veszter- gombi 2008). graphon 序列或图序列收敛当且仅当它是关于切割 (距离) 度量的柯西序列.

关于度量 $d$ 的柯西序列是满足如下要求的序列: 当 $n\to \infty$ 时, ${\sup }_{m\ge 0}d\left(x_n,x_{n+m}\right)\to 0$ .

定理 1.22 (极限存在定理 Lovász and Szegedy 2006). 每个 graphon 或图的收敛序列都有一个极限 graphon.

将 ${\tilde{\mathcal{W}}}_0$ 表示为 graphon 的空间, 其中切割距离为 0 的 graphon 视为同一个 graphon.

定理 1.23 (graphons 空间的紧致性). 集合 ${\tilde{\mathcal{W}}}_0$ 是切割度量下的紧致度量空间.

笔记 1.24. 直观地说, 这意味着 “本质上不同” 的图组成的空间不是很大. 紧致性类似于正则性引理, 其中每个图都有一个大小固定的描述, 可以很好地近似该图. 事实上, 我们可以将这个紧致性定理视为正则性引理的定性分析版本.

1.	^ 一个包含 $n$ 个变量的函数是对称的, 如果它的值与自变量的顺序无关.