2026-08-18 · 让大块误差决定距离

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

昨日把有限稠密图嵌入为阶梯 graphon，并用固定有限图 $F$ 的同态密度 $t(F,W)$ 描述极限。今天补上表示定理背后的度量层：两个 adjacency pictures 看起来逐像素很不同，何时仍应表示同一个无标号大图？

这里有两种失败需要同时修正：

1. 顶点没有天然标签。若只比较 $\Vert U-W\Vert$，同一个图的两种顶点排列可能显得很远。
2. $L^1$ 距离把每条边的微观差异都计入；两个独立的 $G(n,1/2)$ 几乎要改动一半像素才能重合，却具有相同的宏观子图统计。

对象层。 基本对象是 graphon $W:[0,1{]}^2\to [0,1]$、有限可测分割 $\mathcal{P}$、分块平均 $W_{\mathcal{P}}$，以及固定有限简单图 $F$ 的函数 $t(F,\cdot )$。

量词层。 截割范数检查所有可测矩形 $S\times T$；弱正则性说

$$\mathrm{\forall }\epsilon \in (0,1)\mathrm{\forall }W\mathrm{\exists }\mathcal{P}=\mathcal{P}(W,\epsilon ):|\mathcal{P}|\le 4^{1/{\epsilon }^2},\Vert W-W_{\mathcal{P}}{\Vert }_{◻}\le \epsilon ;$$

计数引理则对每个固定 $F$ 给出连续性估计。$F$ 固定不可删去：误差常数随 $|E(F)|$ 增长。

前置与去向。 前置只需多元积分、条件期望／$L^2$ 正交投影、有限图同态；去向是 graphon 商空间的紧致性、有限样本测试、拟随机性与极值图论中的变分问题。

主证明引擎。 一是逐边替换乘积的 telescoping argument（伸缩论证）；二是“发现大矩形误差，就按其见证集合细化分割”的 energy increment（能量增量）。本期是三日微弧的第 2 日：昨日解决“极限对象是什么”，今日解决“怎样比较并逼近它”，明日将问“边与四圈两个统计量何时已经锁定整个 graphon”。

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

1.1 从标签距离到截割距离

设 $K:[0,1{]}^2\to \mathbb{R}$ 可积。定义截割范数 (cut norm)

$$\Vert K{\Vert }_{◻}:=\underset{S,T\subseteq [0,1]\mathrm{measurable}}{sup}|{\int }_{S\times T}K(x,y)dxdy|.$$

它不问每个像素是否一致，只问：是否存在两个顶点群 $S,T$，使二者之间的总边密度出现宏观偏差。

若 $\varphi :[0,1]\to [0,1]$ 是可逆的测度保持映射，记

$$W^{\varphi }(x,y):=W(\varphi (x),\varphi (y)).$$

这是连续空间中的顶点重标号。无标号截割距离 (unlabeled cut distance) 定义为

$${\delta }_{◻}(U,W):=\underset{\varphi }{inf}\Vert U-W^{\varphi }{\Vert }_{◻},$$

其中下确界遍历所有可逆测度保持映射。它在 graphon 本身上只是伪度量：不同函数可能距离为零；把 ${\delta }_{◻}=0$ 的 graphon 识别后才得到真正的度量空间。

1.2 分块平均与弱正则性

给定有限可测分割 $\mathcal{P}=\{P_1,\dots ,P_k\}$，令 $W_{\mathcal{P}}$ 在每个 $P_i\times P_j$ 上等于 $W$ 的平均值。等价地，

$$W_{\mathcal{P}}=\mathbb{E}[W\mid \sigma (\mathcal{P})\otimes \sigma (\mathcal{P})].$$

因此 stepping operator（阶梯化算子）就是 $L^2([0,1{]}^2)$ 中到相应分块常值子空间的正交投影。

定理（Frieze–Kannan 弱正则引理的 graphon 形式）。 对每个 $0<\epsilon <1$ 和每个 graphon $W$，存在至多 $4^{1/{\epsilon }^2}$ 个部分的有限可测分割 $\mathcal{P}$，使

$$\Vert W-W_{\mathcal{P}}{\Vert }_{◻}\le \epsilon .$$

部分数只依赖 $\epsilon$，不依赖原图规模或 $W$ 的像素复杂度。

证明架构。 从平凡分割开始。若当前 $\mathcal{P}$ 尚不合格，则存在可测 $S,T$ 使

$$\left|⟨W-W_{\mathcal{P}},{\mathbf{1}}_{S\times T}⟩\right|>\epsilon .$$

把 $\mathcal{P}$ 的每一部分再按“属于／不属于 $S$”和“属于／不属于 $T$”细分，得到细化 ${\mathcal{P}}^{\prime }$；每个旧部分至多裂成四份。由于 ${\mathbf{1}}_{S\times T}$ 对新分割可测，条件期望与 Cauchy–Schwarz 给出

$$\Vert W_{{\mathcal{P}}^{\prime }}-W_{\mathcal{P}}{\Vert }_2>\epsilon .$$

嵌套正交投影满足 Pythagoras 恒等式

$$\Vert W_{{\mathcal{P}}^{\prime }}{\Vert }_2^2=\Vert W_{\mathcal{P}}{\Vert }_2^2+\Vert W_{{\mathcal{P}}^{\prime }}-W_{\mathcal{P}}{\Vert }_2^2,$$

故每次失败都会使能量 $\Vert W_{\mathcal{P}}{\Vert }_2^2$ 增加超过 ${\epsilon }^2$。又因 $0\le W\le 1$，

$$0\le \Vert W_{\mathcal{P}}{\Vert }_2^2\le \Vert W{\Vert }_2^2\le 1.$$

这样的失败少于 $1/{\epsilon }^2$ 次，最终部分数不超过 $4^{1/{\epsilon }^2}$。假设 $W\in [0,1]$ 在这里同时保证分块平均仍是 graphon，并给出统一能量上界。

谱系上，Frieze–Kannan 的矩阵逼近以算法问题为动力；Lovász–Szegedy 随后把正则性改写为分析、Hilbert 空间投影与 graphon 拓扑中的结构定理。弱正则性不保证每一对小块都像随机图；它只保证所有宏观矩形查询同时准确，故比 Szemerédi 强正则性弱，却足以控制固定图统计。

1.3 Counting lemma：距离为何控制有限模式

先记一个等价形式：对可积 $K$，

$$\Vert K{\Vert }_{◻}=\underset{f,g:[0,1]\to [0,1]}{sup}|{\int }_{[0,1{]}^2}K(x,y)f(x)g(y)dxdy|.$$

可由 layer-cake representation（层蛋糕表示）把 $f,g$ 写成水平集指标的积分而得。

定理（graphon counting lemma）。 若 $F$ 是有限简单图，$U,W$ 是 graphon，则

$$|t(F,U)-t(F,W)|\le |E(F)|{\delta }_{◻}(U,W).$$

逐边证明。 排列 $E(F)=\{e_1,\dots ,e_m\}$，把 $t(F,U)$ 的乘积因子逐个从 $U$ 换成 $W$。相邻两项只在某条边 $e_r=ab$ 上相差一个因子 $U(x_a,x_b)-W(x_a,x_b)$。固定其余顶点变量后，因为 $F$ 没有重边，其余因子可写为

$$cf(x_a)g(x_b),0\le c,f,g\le 1.$$

于是该一步的积分差绝对值至多 $\Vert U-W{\Vert }_{◻}$；再对其余变量积分，界仍不变。对 $m$ 步求和，

$$|t(F,U)-t(F,W)|\le m\Vert U-W{\Vert }_{◻}.$$

而 $t(F,W)=t(F,W^{\varphi })$ 对测度保持重标号不变；以 $W^{\varphi }$ 代入并对 $\varphi$ 取下确界，即得结论。

因此

$${\delta }_{◻}(W_n,W)\to 0⟹\mathrm{\forall }\text{ fixed }F,t(F,W_n)\to t(F,W).$$

昨日的“有限模式矩”由此成为商空间上的连续函数，而非一组偶然可收敛的数。

1.4 研究生／现代延伸：紧致性与逆计数

弱正则性给每个 graphon 一个复杂度只依赖精度的阶梯近似；再离散化各块大小和块值，可构造有限 $\epsilon$-net。由此发展的核心结论是：graphon 在 ${\delta }_{◻}=0$ 下取商后为紧致空间。

紧致性与“所有同态密度能区分商空间中的点”合在一起，还给出定性的 inverse counting lemma（逆计数引理）：

$$\mathrm{\forall }\epsilon >0\mathrm{\exists }k=k(\epsilon )\in \mathbb{N}\mathrm{\exists }\eta =\eta (\epsilon )>0\mathrm{\forall }U,W,$$

若对每个满足 $|V(F)|\le k$ 的有限简单图 $F$ 都有

$$|t(F,U)-t(F,W)|\le \eta ,$$

则 ${\delta }_{◻}(U,W)\le \epsilon$。正向 counting lemma 说“近则所有固定测试相近”；逆向结论说“达到给定精度，只需有限但随精度增长的一组测试”。这正是 property testing（性质测试）与有限强迫问题的入口。

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

题目

设 $(X_n{)}_{n\ge 1}$ 与 $X$ 是同一概率空间上的实值随机变量，并且 $X_n\to X$ 依概率收敛，即

$$\mathrm{\forall }\epsilon >0\mathrm{\forall }\eta >0\mathrm{\exists }{n}_0=n_0(\epsilon ,\eta )\mathrm{\forall }n\ge n_0:\mathbb{P}(|X_n-X|>\epsilon )<\eta .$$

证明：存在严格递增的正整数列 $(n_k{)}_{k\ge 1}$，使 $X_{n_k}\to X$ 几乎必然收敛。

模板识别

信号是“弱收敛模式要求抽取强收敛子列”。依概率收敛允许同时指定误差阈值与坏事件概率；应把二者选成趋零且概率可求和的序列，再调用第一 Borel–Cantelli 引理。这里不需要事件独立。

分级提示

1. 对第 $k$ 步，把误差阈值和目标坏事件概率都取成 $2^{-k}$。
2. 递归选择 $n_k>n_{k-1}$，使 $\mathbb{P}(|X_{n_k}-X|>2^{-k})<2^{-k}$。
3. 令 $A_k=\{|X_{n_k}-X|>2^{-k}\}$。先判断 $\sum _k\mathbb{P}(A_k)$ 是否有限。
4. 在只有有限多个 $A_k$ 发生的样本点上，把“最终不在 $A_k$”翻译成逐点收敛。

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

人物与语境。 组合数学家 Gil Kalai 在个人博客 Combinatorics and more 的 “Test Your Intuition” 系列第 59 题中提出一个强化投票模型，文章发表于 2026 年 8 月 15 日。第 $i+1$ 轮投给候选人 $k$ 的概率与上一轮票数 $(a_k^i{)}^{\alpha }$ 成正比；当某人获得至少三分之二票数时停止。Kalai 随后把问题按强化指数 $\alpha$ 相对临界值 $1$ 的位置拆开。

逐字引文（28 words）。

“Test your intuition: What is the expected number of steps until a pope is elected 1. When α = 1 2. When α < 1 3. When α > 1”

中译。 “测试你的直觉：选出教宗之前，预期需要多少步？（1）$\alpha =1$；（2）$\alpha <1$；（3）$\alpha >1$。”

这里值得保留的不是故事外壳，而是提问方式：先找出控制反馈强弱的无量纲参数，再围绕临界值作三分，而不是只计算一个孤立参数点。$\alpha =1$ 对应 Wright–Fisher／Kingman 已研究的中性复制机制；$\alpha <1$ 抑制领先者，$\alpha >1$ 放大领先者，故共识时间可能跨越不同的渐近区制。

这与今日 graphon 定理没有直接依赖关系，毋须强行类比；方法上的回声仅在于：面对巨大随机状态空间，先寻找少数能组织全局行为的参数或低复杂度投影，然后追问该压缩在何处失效。截割逼近压缩空间，$\alpha$ 则组织动力学。

来源直达：
https://gilkalai.wordpress.com/2026/08/15/test-your-intuition-59-the-conclave-process

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

4.1 若不对重标号取下确界，同一个无标号结构会有正距离

令

$$A=[0,1/2],U={\mathbf{1}}_{A\times A}+{\mathbf{1}}_{A^c\times A^c},$$

即两个等大的完全团。再令

$$B=[0,1/4]\cup [1/2,3/4],W={\mathbf{1}}_{B\times B}+{\mathbf{1}}_{B^c\times B^c}.$$

存在可逆测度保持映射 $\varphi$ 把 $B$ 搬到 $A$，故 $W=U^{\varphi }$（忽略零测集），于是

$${\delta }_{◻}(U,W)=0.$$

但在固定坐标中取

$$S=A\cap B=[0,1/4],T=A\cap B^c=[1/4,1/2].$$

对 $S\times T$，两点同属 $A$，所以 $U=1$；它们分属 $B$ 与 $B^c$，所以 $W=0$。逐项检查得

$$\Vert U-W{\Vert }_{◻}\ge {\int }_{S\times T}(U-W)=\lambda (S)\lambda (T)=\frac{1}{16}>0.$$

边界很精确：cut norm 比较已标号表示，cut distance 才比较无标号对象。

4.2 若把 cut norm 换成 $L^1$，随机微观噪声不会消失

取 $G_n\sim G(n,1/2)$，令 $W_{G_n}$ 为其 $n$ 阶阶梯 graphon。因为 $W_{G_n}$ 只取 $0,1$，逐点都有

$$|W_{G_n}-1/2|=1/2,$$

故对每个实现、每个 $n$，

$$\Vert W_{G_n}-1/2{\Vert }_1=1/2.$$

另一方面，对固定顶点子集 $S,T$，边数偏差是独立 Bernoulli 变量的和；bounded-difference／Hoeffding 界给出指数尾界。对至多 $4^n$ 对顶点子集作 union bound，可得以趋于 $1$ 的概率

$$\Vert W_{G_n}-1/2{\Vert }_{◻}=O(n^{-1/2})\to 0.$$

所以 $L^1$ 把“逐边是否相同”当作结构，而 cut norm 只保留能在大矩形上累积的偏差。前者适合 edit distance，后者才适合稠密图的宏观极限。

最后还有 counting lemma 自身的量词边界：

$$|t(F,U)-t(F,W)|\le |E(F)|{\delta }_{◻}(U,W)$$

只对固定 $F$ 给出随距离趋零的控制。若测试图 $F=F_n$ 的边数同时增长，右端未必趋零；不能把“所有固定有限模式收敛”偷换成“任意增长模式都一致收敛”。

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

设 $W:[0,1{]}^2\to [0,1]$ 是 graphon，且对某个 $p\in [0,1]$ 满足

$$t(K_2,W)=p,t(C_4,W)=p^4.$$

能否只用两次 Cauchy–Schwarz，证明 $W=p$ 几乎处处，从而说明这两个统计量已经把 $W$ 强迫为常值 graphon？

定向提示。 令

$$d(x)={\int }_0^{1}W(x,y)dy,K(x,z)={\int }_0^{1}W(x,y)W(y,z)dy.$$

把 $t(C_4,W)$ 分别写成 $\Vert K{\Vert }_2^2$，并把 $\int K$ 与 $\int d^2$ 联系起来。关键不是只写出不等式链，而是逐层追踪等号条件最终要求哪些函数为常数。

数学地图。

$$\{\begin{array}{l}\text{多元积分与 Cauchy--Schwarz}\\ \text{同态密度 }t(F,W)\end{array}⟹\text{cut norm 与 counting lemma}⟹\{\begin{array}{l}\text{quasirandomness（拟随机性）}\\ \text{finite forcibility（有限强迫）}\\ \text{graphon 变分与稳定性}\end{array}$$

明日将完成这条等号刚性链，并解释为什么“边密度正确”远远不够，而四圈恰好检测二阶邻域相关性。

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

展开完整解答

模板名称：可和坏事件抽取 (summable-bad-event subsequence extraction)。

由 $X_n\to X$ 依概率收敛，对每个 $k\ge 1$，存在整数

$$N_k=N_k(2^{-k},2^{-k})$$

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

$$\mathbb{P}(|X_n-X|>2^{-k})<2^{-k}.$$

递归选取

$$n_1\ge N_1,n_k\ge max\{N_k,n_{k-1}+1\}(k\ge 2).$$

于是 $(n_k)$ 严格递增，并且

$$\mathbb{P}(|X_{n_k}-X|>2^{-k})<2^{-k}.$$

令

$$A_k:=\{|X_{n_k}-X|>2^{-k}\}.$$

则

$$\sum _{k=1}^{\mathrm{\infty }}\mathbb{P}(A_k)\le \sum _{k=1}^{\mathrm{\infty }}{2}^{-k}=1<\mathrm{\infty }.$$

由第一 Borel–Cantelli 引理，

$$\mathbb{P}(A_k\text{发生无穷多次})=0.$$

注意这里不要求 $(A_k)$ 独立。

因此存在零测集 $N$，使每个 $\omega \notin N$ 都有某个

$$k_0=k_0(\omega )$$

满足对所有 $k\ge k_0$，$\omega \notin A_k$。也就是

$$|X_{n_k}(\omega )-X(\omega )|\le 2^{-k}⟶0.$$

故

$$X_{n_k}\to X\text{几乎必然}.$$

该模板的核心量词动作是：依概率收敛给每一对“误差阈值—概率阈值”一个足够大的指标；递归选择把这些分散的指标组织成一个子列；概率阈值的可和性再把每一级控制升级为样本点上的最终控制。

资料与来源 (Sources)

1. Yufei Zhao, Graph Theory and Additive Combinatorics, Chapter 4, “Graph Limits.” 其中 Definition 4.2.1–4.2.6 给出 cut norm、测度保持重标号与 cut metric；Theorem 4.5.1 给出 counting lemma；Theorem 4.6.7 给出 graphon 弱正则引理及 $4^{1/{\epsilon }^2}$ 界。
   https://yufeizhao.com/gtacbook/4.pdf

2. Svante Janson, Graphons, Cut Norm and Distance, Couplings and Rearrangements, New York Journal of Mathematics Monographs 4 (2013). 用于核对一般概率空间上的 graphon、cut norm 的等价形式、拉回／重排及 ${\delta }_{◻}=0$ 的等价问题。
   http://emis.muni.cz/journals/NYJM/m/2013/4v.pdf

3. Alan Frieze and Ravi Kannan, “Quick Approximation to Matrices and Applications,” Combinatorica 19 (1999), 175–220, DOI 10.1007/s004930050052. 原始矩阵逼近工作把矩形和误差压到 $\epsilon mn$，并导出稠密图算法与弱正则性。
   https://link.springer.com/article/10.1007/s004930050052

4. László Lovász and Balázs Szegedy, “Szemerédi’s Lemma for the Analyst,” Microsoft Research Technical Report MSR-TR-2005-90；后发表于 Geometric and Functional Analysis 17 (2007), 252–270. 用于核对把正则性解释为分析与 Hilbert 空间逼近的谱系。
   https://www.microsoft.com/en-us/research/publication/szemeredis-lemma-for-the-analyst

5. László Lovász and Balázs Szegedy, “Limits of Dense Graph Sequences,” Microsoft Research Technical Report MSR-TR-2004-79 (August 2004), later Journal of Combinatorial Theory, Series B 96 (2006), 933–957. 用于核对由固定子图密度到对称二元可测极限对象的原始表示框架。
   https://www.microsoft.com/en-us/research/publication/limits-of-dense-graph-sequences

6. Gil Kalai, “Test Your Intuition 59: The Conclave Process,” Combinatorics and more, 15 August 2026. 本期“大家之言”的模型、$\alpha$ 三分问题与逐字引文取自该第一人称原文；文章同时说明 $\alpha =1$ 与 Wright–Fisher、Kingman 工作的关系。
   https://gilkalai.wordpress.com/2026/08/15/test-your-intuition-59-the-conclave-process

7. László Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60, American Mathematical Society, 2012. 作为 graphon 的 cut distance、正则分割、sampling、counting lemma 与紧致性的权威专著入口。
   https://www.ams.org/books/coll/060/