2026-08-17 · 把有限图压成可测函数

0. 导读与元结构 (Orientation & Meta-structure)

原始问题

一列图 $G_1,G_2,\dots$ 的顶点数不断增大，而且各图甚至没有共同的顶点集。此时，“逐点收敛”无从谈起：$G_n$ 的第 $17$ 个顶点与 $G_{n+1}$ 的第 $17$ 个顶点没有内在对应。真正稳定的可观测量，应当不依赖顶点名称，并且只询问有限复杂度的问题。

稠密图极限 (dense graph limits) 选择如下观测方式：固定一个有限简单图 $F$，随机把 $V(F)$ 映入 $V(G_n)$，询问该映射保边的概率。这个概率就是同态密度 (homomorphism density) $t(F,G_n)$。

对象层与量词层

• 变动对象层：有限简单图 $G_n$，并假定 $|V(G_n)|\to \mathrm{\infty }$。
• 固定测试层：任取一个有限简单图 $F$；先固定 $F$，再令 $n\to \mathrm{\infty }$。
• 极限对象层：对称可测函数 $W:[0,1{]}^2\to [0,1]$，称为 graphon。
• 左收敛 (left convergence) 的完整量词：对每个有限简单图 $F$，存在实数 ${\ell }_F$，使得对每个 $\epsilon >0$，存在 $N=N(F,\epsilon )$，满足对所有 $n\ge N$，
  $$|t(F,G_n)-{\ell }_F|<\epsilon .$$
  次序是 $\mathrm{\forall }F\mathrm{\exists }{\ell }_F\mathrm{\forall }\epsilon \mathrm{\exists }N(F,\epsilon )\mathrm{\forall }n\ge N$；不能把“固定 $F$”误读成同时控制任意增大的测试图。

前置、去向与证明引擎

前置知识只有有限图同态、概率的乘法法则和多重积分。今日对象将通向截割距离 (cut distance)、Szemerédi/Frieze–Kannan 正则性、拟随机图、图性质测试，以及更高阶的可交换随机图与大偏差理论。

支配本题的证明引擎有四个：

1. 用有限测试图的密度充当“矩”；
2. 用弱正则性把巨大邻接矩阵压缩成低复杂度阶梯函数；
3. 用紧致性与对角抽取制造极限；
4. 用 counting lemma 把截割范数中的逼近转回子图统计。

这是三日 anchor micro-arc 的第 1 日：今天回答“极限对象是什么、为何存在”；第 2 日将处理重标号、截割范数和 counting lemma；第 3 日再连接拟随机性、抽样与随机图模型。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 从“数副本”改成“测概率”

设 $F,G$ 是有限简单图。图同态 (graph homomorphism) 是映射

$$\phi :V(F)\to V(G)$$

使得对每条 $uv\in E(F)$，都有 $\phi (u)\phi (v)\in E(G)$。记同态数为 $\mathrm{hom}(F,G)$，定义

$$t(F,G)=\frac{\mathrm{hom}(F,G)}{|V(G){|}^{|V(F)|}}.$$

若从所有映射 $V(F)\to V(G)$ 中均匀随机选取 $\phi$，那么 $t(F,G)$ 正是“$\phi$ 保持每条边”的概率。因此 $0\le t(F,G)\le 1$，且它不依赖 $G$ 的顶点标号。

这里允许不同顶点被映到同一点。若 $|V(F)|=k$、$|V(G)|=n$，随机映射不是单射的概率至多为

$$(\genfrac{}{}{0ex}{}{k}{2})\frac{1}{n}.$$

所以当 $F$ 固定而 $n\to \mathrm{\infty }$ 时，同态密度与通常的嵌入密度只差 $O_F(n^{-1})$。允许非单射不是偷换问题，而是用一个代数上更稳定、极限上等价的计数替代。

1.2 把邻接矩阵变成函数

定义（graphon）：graphon 是一个 Lebesgue 可测函数

$$W:[0,1{]}^2\to [0,1]$$

满足 $W(x,y)=W(y,x)$ 几乎处处。相差零测集的函数不作区分。

若 $F$ 的顶点集为 $[k]=\{1,\dots ,k\}$，定义 $F$ 在 $W$ 中的同态密度为

$$t(F,W)={\int }_{[0,1{]}^k}\prod _{ij\in E(F)}W(x_i,x_j)d{x}_1\cdots d{x}_k.$$

其概率解释很直接：独立均匀抽取 $X_1,\dots ,X_k\in [0,1]$，在给定这些潜变量后，以 $W(X_i,X_j)$ 为边 $ij$ 出现的概率；上式就是测试图 $F$ 的所有边都出现的概率。

每个 $n$ 顶点图 $G$ 都能嵌入这个语言。把 $[0,1]$ 等分成 $I_1,\dots ,I_n$，并令

$$W_G(x,y)=\{\begin{array}{ll}1,& (x,y)\in I_i\times I_j\text{ 且 }ij\in E(G),\\ 0,& \text{其他情形}.\end{array}$$

逐格展开积分即可得到

$$t(F,W_G)=t(F,G).$$

因此 graphon 不是凭空添加的连续对象；它先把有限邻接矩阵写成阶梯函数，再允许阶梯越来越细。

1.3 Lovász–Szegedy 表示定理

定理（稠密图列的 graphon 表示）：设 $(G_n{)}_{n\ge 1}$ 是有限简单图列，$|V(G_n)|\to \mathrm{\infty }$，并且对每个有限简单图 $F$，极限

$${\ell }_F=\underset{n\to \mathrm{\infty }}{lim}t(F,G_n)$$

存在。则存在 graphon $W$，使得对每个有限简单图 $F$，

$${\ell }_F=t(F,W).$$

反之，对每个 graphon $W$，都存在有限简单图列 $(G_n)$，使得对每个有限简单图 $F$，

$$\underset{n\to \mathrm{\infty }}{lim}t(F,G_n)=t(F,W).$$

这是一个表示定理，而不是说 $W_G$ 在通常的逐点意义下收敛。顶点可任意重标号；两个看起来完全不同的像素图可能代表同一个有限图。正确的距离必须先消去这种坐标任意性，明日将以截割距离处理。

1.4 证明架构：每个假设为何出现

存在方向的骨架如下。

1. 低复杂度逼近：对每个精度 $\eta >0$，Frieze–Kannan 弱正则性把 $W_{G_n}$ 在截割范数中逼近为块数只依赖 $\eta$ 的阶梯函数。这里需要稠密归一化，因为截割误差按 $|V(G_n){|}^2$ 缩放。
2. 对角抽取：依次取精度 $1,1/2,1/3,\dots$，在每个有限复杂度层上抽取收敛子列，并令各层逼近相容。所得有界阶梯函数序列可生成一个可测极限 $W$；现代证明常把这一步组织成鞅收敛。
3. 把函数距离还原成图统计：对任意有限简单图 $F$ 和 $[0,1]$ 值 graphon $U,W$，counting lemma 给出
   $$|t(F,U)-t(F,W)|\le |E(F)|\parallel U-W{\parallel }_{◻}.$$
   证明把两个乘积逐边作 telescoping expansion；每一项只剩一个 $U-W$ 因子，其余因子都在 $[0,1]$ 内，故由截割范数控制。
4. 回到原序列：抽出的子列对每个 $F$ 仍收敛到原先已经存在的 ${\ell }_F$，所以构造出的 $W$ 同时表示全部 ${\ell }_F$。假设“每个固定 $F$ 的极限存在”正是在此把子列结论提升为给定图列的统一矩数据。

反方向可由 $W$-随机图完成：独立取 $X_1,\dots ,X_n\sim \mathrm{Unif}[0,1]$，并在给定 $(X_i)$ 后独立地以概率 $W(X_i,X_j)$ 连边。对每个固定 $F$，其同态密度的期望趋于 $t(F,W)$，浓缩不等式给出指数小的偏差概率；再对可数多个有限图使用 Borel–Cantelli，即得几乎处处同时收敛。

1.5 直接后果与现代延伸

• 常值 graphon $W\equiv p$ 满足 $t(F,W)=p^{|E(F)|}$，它编码边密度为 $p$ 的拟随机极限。
• 有限块阶梯 graphon 编码 stochastic block model：块的长度是类型比例，块间函数值是连边概率。
• Graduate extension：把截割距离为零的 graphon 识别后，graphon 空间在截割度量下是紧致的；左收敛等价于截割距离下的 Cauchy 性。于是 graphon 空间可视为稠密有限图空间的一种完备化。
• graphon 的点值表示一般不唯一：零测集修改、测度保持重标号，乃至更一般的弱同构，都不改变全部 $t(F,W)$。真正的极限对象是等价类，不是一张带绝对坐标的图片。

2. 固定模板习题 (Template Exercise)

题目

设 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ 为概率空间，$X_n,X$ 为实值随机变量。假设存在常数 $M<\mathrm{\infty }$，使得对每个 $n$，

$$|X_n|\le M\text{a.s.},|X|\le M\text{a.s.},$$

并且 $X_n\to X$ 依概率收敛 (convergence in probability)。证明

$$\mathbb{E}|X_n-X|\to 0.$$

模板识别

题目同时给出“依概率收敛”和“统一有界”。前者只能控制坏事件的概率，后者能控制坏事件上损失的最大幅度；信号指向 好事件／坏事件截分 (good-event/bad-event split)，而不是直接套用几乎处处版本的 dominated convergence theorem。

分级提示

1. 固定阈值 $\delta >0$，按事件 $\{|X_n-X|\le \delta \}$ 与其补集拆开期望。
2. 好事件上的积分至多是多少？坏事件上由 $|X_n-X|\le 2M$ 可得什么？
3. 证明
   $$\mathbb{E}|X_n-X|\le \delta +2M\mathbb{P}(|X_n-X|>\delta ).$$
4. 给定目标误差 $\epsilon >0$，先选 $\delta$，再用依概率收敛选择 $n_0=n_0(\delta ,\epsilon ,M)$；注意选择次序。

3. 大家之言 (Mathematician in Their Own Words)

语境：理论计算机科学家 Luca Trevisan 在个人博客 in theory 的文章 “Online Optimization Post 4: Regularity Lemmas”（2019 年 5 月 16 日）中，把若干正则性引理统一解释为低复杂度逼近的迭代构造。文章不是事后口号，而是直接给出“逼近器—检查者—反例—势函数”的证明机制。

原文（已核对）：

“All these results are proved with a similar strategy: one starts from a trivial approximator, for example the empty graph, and then repeats the following iteration: if the current approximator achieves the required approximation, then we are done; otherwise take a counterexample, and modify the approximator using the counterexample.”

中译：

“这些结果都用相似的策略证明：从一个平凡逼近器（例如空图）开始，反复执行如下迭代：若当前逼近器已达到所需精度，便结束；否则取一个反例，并用该反例修正逼近器。”

评注：这段话揭示的不是“复杂对象可以近似”这一静态事实，而是一个可执行的证明循环：当前模型若在某个测试上失败，失败见证就成为下一次修正方向；势函数则证明循环不能无限进行。弱正则性把所有 cut tests 压缩到有限复杂度，graphon 紧致性再把逐级逼近组织成极限对象。换言之，极限理论的连续语言并未抹掉组合构造，反而保存了反例驱动的离散更新机制。

4. 反例与边界 (Counterexample & Boundary)

稀疏图在稠密标度下全部塌缩

令 $C_n$ 为 $n$ 个顶点的圈图，$n\ge 3$；令 $E_n$ 为同样顶点数的空图。我们逐项核对它们的稠密 graphon 极限。

固定任意含至少一条边的有限简单图 $F$，并在 $F$ 中选一条边 $uv$。若随机映射 $\phi :V(F)\to V(C_n)$ 是图同态，那么必有 $\phi (u)\phi (v)\in E(C_n)$。因此

$$\begin{array}{rl}t(F,C_n)& =\mathbb{P}(\phi \text{ 是图同态})\\ & \le \mathbb{P}(\phi (u)\phi (v)\in E(C_n))\\ & =\frac{2|E(C_n)|}{n^2}=\frac{2}{n}⟶0.\end{array}$$

若 $F$ 无边，则每个映射都是同态，故 $t(F,C_n)=1$。这与零 graphon $W\equiv 0$ 完全一致：含边 $F$ 的积分为 $0$，无边 $F$ 的空乘积积分为 $1$。所以

$$C_n⟶W\equiv 0.$$

空图列 $E_n$ 显然也收敛到同一个零 graphon。

然而，对每个 $n\ge 3$：

• $C_n$ 连通，而 $E_n$ 有 $n$ 个连通分量；
• $C_n$ 的每个顶点度数为 $2$，而 $E_n$ 的每个顶点度数为 $0$；
• 两者的局部邻域结构完全不同。

因此 graphon 理论没有错误；它精确记录的是 $n^2$ 标度上的边与有限模式密度。对只有 $O(n)$ 条边的稀疏图，这些密度必然消失。要保存有界度局部几何，需要 Benjamini–Schramm 型局部弱收敛；要处理更一般稀疏网络，则需 graphex、$L^p$ graphon 或其他重新归一化框架。边界在“归一化尺度”，不在“函数表示”本身。

5. 今日一问与数学地图 (Question & Map)

今日一问

设 $0<p<1$，$(G_n)$ 是顶点数趋于无穷的有限简单图列，并满足

$$t(K_2,G_n)\to p,t(C_4,G_n)\to p^4.$$

仅凭“边密度正确”和“长度四闭路密度正确”，是否足以推出对每个有限简单图 $F$，

$$t(F,G_n)\to p^{|E(F)|}?$$

换言之，这两个测试能否强迫极限 graphon 为常值 $W\equiv p$（按弱同构计）？

方向提示，不给完整答案：把 $W-p$ 看成积分算子的核；$C_4$ 密度会出现一个可由反复 Cauchy–Schwarz 控制的四次量。关键不是一般地“矩决定分布”，而是辨认等号情形是否迫使所有非常值方向消失。

数学地图

$$\text{有限图同态}⟶\text{同态密度 }t(F,G)⟶\text{graphon }W⟶\{\begin{array}{l}\text{截割度量与重标号商},\\ \text{弱正则性与性质测试},\\ \text{拟随机图与极值图论},\\ \text{可交换随机图与 Aldous--Hoover 表示},\\ \text{随机图大偏差与变分问题}.\end{array}$$

今日的表示定理解决“极限存在于何处”；明日的截割距离解决“何谓同一个极限”；后日的拟随机性将回答“少量统计量何时锁定整个极限”。

附录 A：习题完整解答 (Full Solution)

展开完整解答

模板名称：好事件／坏事件截分 (good-event/bad-event split)。

若 $M=0$，则 $X_n=X=0$ 几乎处处，结论显然。以下设 $M>0$。

任给目标误差 $\epsilon >0$，先取

$$\delta =\frac{\epsilon }{2}.$$

对每个 $n$，把期望按事件

$$A_n=\{|X_n-X|\le \delta \}$$

及其补集拆开：

$$\begin{array}{rl}\mathbb{E}|X_n-X|& =\mathbb{E}(|X_n-X|{\mathbf{1}}_{A_n})+\mathbb{E}(|X_n-X|{\mathbf{1}}_{A_n^c})\\ & \le \delta +2M\mathbb{P}(A_n^c)\\ & =\delta +2M\mathbb{P}(|X_n-X|>\delta ).\end{array}$$

第一项使用 $A_n$ 上的 $|X_n-X|\le \delta$；第二项使用全局的

$$|X_n-X|\le |X_n|+|X|\le 2M$$

几乎处处成立。

因为 $X_n\to X$ 依概率收敛，所以对已固定的 $\delta =\epsilon /2$，存在

$$n_0=n_0(\delta ,\epsilon ,M)$$

使得对所有 $n\ge n_0$，

$$\mathbb{P}(|X_n-X|>\delta )<\frac{\epsilon }{4M}.$$

于是对所有 $n\ge n_0$，

$$\mathbb{E}|X_n-X|<\frac{\epsilon }{2}+2M\frac{\epsilon }{4M}=\epsilon .$$

因此 $\mathbb{E}|X_n-X|\to 0$。

该模板的可复用核心是：依概率收敛只让坏集的概率趋零；一致有界把坏集上的损失压到固定常数。二者相乘，坏集贡献才趋于零。

资料与来源 (Sources)

1. László Lovász and Balázs Szegedy, Limits of dense graph sequences, Microsoft Research Technical Report TR-2004-79, arXiv:math/0408173v2, 22 September 2004. 原论文给出同态密度、对称可测极限对象、表示定理、$W$-随机图与稀疏标度退化的原始论述。
   https://arxiv.org/pdf/math/0408173

2. Yufei Zhao, Graph Theory and Additive Combinatorics, Chapter 4, “Graph Limits.” 该章系统陈述 graphon、截割距离、紧致性、同态密度、counting lemma 与两种收敛的等价性。
   https://yufeizhao.com/gtacbook/4.pdf

3. László Lovász, Large Networks and Graph Limits, AMS Colloquium Publications, Vol. 60, 2012，AMS 数字内容页。用于核对该理论与正则性、性质测试、概率论和极值图论的现代联系。
   https://www.ams.org/books/coll/060/

4. Luca Trevisan, “Online Optimization Post 4: Regularity Lemmas,” in theory, 16 May 2019. 本期“大家之言”的逐字引文及其迭代逼近语境。
   https://lucatrevisan.wordpress.com/2019/05/16/online-optimization-post-4-regularity-lemmas/