5. 紧致性的应用

我们现在将使用 $(W_{0}, δ_{□})$ 的紧致性来证明几个结论, 分别是 graphon 的强正则性引理, 图同态密度和切割范数定义的收敛之间的等价性, 以及任意图同态密度收敛的 graphon 序列都存在极限.

作为热身, 我们将对于证明任意的 graphon, 存在图在切割距离意义下一致收敛到该 graphon. 下面的引理证明无需用到紧致性:

引理 5.1. 对于任意 $ϵ > 0$ 和任意 graphon $W$ , 存在满足 $δ_{□} (G, W) < ϵ$ 的图 $G$ .

证明. 根据测度论的知识, 存在一个阶跃函数 $U$ 满足 $∥ W - U ∥_{1} < ϵ /2$ . 对于任何常值 graphon $p$ , 存在一个图 $G$ 使得 $∥ G - p ∥_{□} < ϵ /2$ . 实际上, 对于足够大的 $n$ , 随机图 $G (n, p)$ 满足这个上界的概率很大. 因为阶跃函数由许多常值函数构成, 所以我们可以通过拼凑各种密度的随机图来找到一个满足 $∥ G - U ∥_{□} < ϵ /2$ 的图 $G$ . 所以 $δ_{□} (G, W) \leq ∥ W - U ∥_{1} + ∥ U - G ∥_{□} < ϵ$ 这是我们想要的.

$□$

然而, 在上述引理中, 图的大小可能取决于 $W$ . 这一点可以通过紧致性来完善.

命题 5.2. 对于任意 $ϵ > 0$ , 存在 $N \in N$ 使得对于任意 graphon $W$ , 存在一个满足 $δ_{□} (G, W) < ϵ$ 的 $N$ 顶点图 $G$ .

证明. 对于一个图 $G$ , 定义开球 $B_{ϵ} (G) = {W \in W_{0} : δ_{□} (G, W) < ϵ}$ , 用来表示 $G$ 的 $ϵ$ 邻域.

令 $G$ 取遍所有的图, 根据引理 5.1, $G$ 对应的 $B_{ϵ} (G)$ 构成了 $W_{0}$ 的一个开覆盖. 根据紧致性, 这个开覆盖有一个有限子覆盖. 所以存在一组数量有限的图 $G_{1}, \dots, G_{k}$ , 满足 $B_{ϵ} (G_{1}), \dots, B_{ϵ} (G_{k})$ 覆盖 $W_{0}$ . 令 $N$ 是 $G_{1}, \dots, G_{k}$ 顶点数量的最小公倍数. 所以对于每个 $G_{i}$ , 存在 $N$ 顶点图 $G_{i}^{'}$ 满足 $δ_{□} (G_{i}, G_{i}^{'}) = 0$ . (通过将 $G_{i}$ 的每个顶点替换成用 $N / ∣ V (G_{i}) ∣$ 个顶点得到 $G^{'}$ , 见图 ??) . 所以 $W$ 包含在某个 $N$ 顶点图 $G$ 的 $ϵ$ 开球内, 这就是我们想要的.

(...)

K_{3}

及其 2-blow up

$□$

笔记 5.3. 不幸的是, 上述证明没有提供关于 $N$ 如何依赖于 $ϵ$ 的信息. 这是应用紧致性的副作用. 我们可以使用正则性找到给出界限的替代证明.

直观上, 紧致性与正则性引理具有相似性: 两者都表明图空间在某种意义上非常小. 事实上, 他们之间有着更明确的联系: 我们在紧致性证明中使用了弱正则性引理, 而强正则性引理则可以直接从紧致性推导出来.

定理 5.4 (graphon 的强正则性引理 Lovász and Szegedy 2007). 令 $ϵ = (ϵ_{1}, ϵ_{2}, \dots)$ 是一个正实数序列. 存在 $M = M (ϵ)$ 使得每个 graphon $W$ 都可以写成 $W = W_{s t r} + W_{p sr} + W_{s m l}$ 其中

•	$W_{str}$ 是一个由 $k$ 个部分组成的阶跃函数, 其中 $k < M$ .
•	$∥ W_{p sr} ∥_{□} \leq ϵ_{k}$ .
•	$∥ W_{s m l} ∥_{1} \leq ϵ_{1}$ .

笔记 5.5. 如果 $ϵ_{k} = ϵ / k^{2}$ , 该定理近似等价于 Szemerédi 正则性引理. 如果 $ϵ_{k} = ϵ$ , 那么它近似等价于弱正则性引理.

证明. 熟悉测度论的读者应该知道, 任何可测函数都可以通过阶跃函数很好的近似. 因此, 对于每个 graphon $W$ 都存在阶跃函数 $U$ 使得 $∥ W - U ∥_{1} \leq ϵ_{1}$ . 不幸的是, 阶跃函数的阶数可能取决于 $W$ ; 我们将在这个地方使用紧致性.

对于 graphon $W$ , 令 $k (W)$ 是满足 $∥ W - U ∥_{1} \leq ϵ_{1}$ ( $U$ 是步数为 $k$ 的阶跃函数) 条件下最小的 $k$ . 则 ${B_{ϵ_{k (W)}}}_{W \in W_{0}}$ 显然是 $W_{0}$ 的开覆盖, 根据紧致性, 存在一组有限的 graphon $S \subset W_{0}$ 使得 ${B_{ϵ_{k (W)}} (W)}_{W \in S}$ 覆盖 $W_{0}$ .

令

M = max_{W \in S} k (W)

. 根据禁致性, 对于任意 graphon

W

, 存在

W^{'} \in S

满足

δ_{□} (W, W^{'}) \leq ϵ_{k (W^{'})}

. 此外, 存在一个 graphon

U

(

U

是阶数为

k

的阶跃函数, 且

k = k (W^{'}) \leq M

) 使得

∥ W^{'} - U ∥_{1} \leq ϵ_{1}

. 因此,

W = U + (W - W^{'}) + (W^{'} - U)

所以我们得到了想要的分解, 其中

W_{str} = U, W_{psr} = W - W^{'}

和

W_{sml} = W^{'} - U

.

$□$

之前我们通过 $F$ 密度的序列定义了 graphon 序列的收敛性. 然而, 直到现在我们还不知道收敛的 graphon 序列的极限的 $F$ 密度是否可以通过单个 graphon 来实现. 如果包含 graphon 的图空间不是完备的, 这是不正确的, 正如我们在拟随机图的中看到的那样. 但在 graphon 空间中, 该结果是正确的, 通过紧致性我们可以快速验证这一点.

定理 5.6 (极限存在定理).

设 graphon 序列 $W_{1}, W_{2}, \dots$ 满足: 对应 $F$ 密度的序列 ${t (F, W_{n})}_{n}$ 对所有图 $F$ 收敛. 则 graphon 的序列收敛到某一 graphon $W$ . 也就是说, 存在一个 graphon $W$ 满足: 对于每个 $F$ , $t (F, W_{n}) \to t (F, W)$ 都成立.

证明.

根据序列紧致性, 存在一个子序列 $(n_{i})_{i = 1}^{\infty}$ 和一个 graphon $W$ 使得当 $i \to \infty$ 时, $δ_{□} (W_{n_{i}}, W) \to 0$ . 固定一个图 $F$ , 由定理 3.0.1 我们知道 $t (F, W_{n_{i}}) \to t (F, W)$ . 回顾条件, 序列 ${t (F, W_{n})}_{n}$ 收敛, 所以所有子序列都有相同的极限. 因此 $t (F, W_{n}) \to t (F, W)$ .

$□$

图极限的最后一个重要结论是我们之前定义的两个收敛概念的等价性.

定理 5.7 (收敛的等价性 Borgs, Chayes, Lovász, Sós, and Veszter-gombi 2008). $F$ 密度的收敛等价于切割范数意义下的收敛. 也就是说, 对于一个 graphon 序列 $W_{1}, W_{2}, \dots$ , 以下是等价的:

•	对于所有图 $F$ , $F$ 密度的序列 ${t (F, W_{n})}_{n}$ 收敛.
•	序列 ${W_{n}}_{n}$ 是 $δ_{□}$ 意义下的柯西列.

证明. 一个方向通过定理 3.0.1 可以立即得到. 回顾计数引理, 如果序列 ${W_{n}}_{n}$ 是 $δ_{□}$ 意义下的柯西列, 那么计数引理意味着对于每个图 $F$ , $F$ 密度的序列是柯西列, 因此是收敛的.

对于反方向, 假设对所有图 $F$ , $F$ 密度的序列收敛. 设 $W$ 和 $U$ 为 ${W_{n}}_{n}$ 的极限点 (即收敛子序列的极限) . 我们想要证明 $W = U$ .

令 $(n_{i})_{i = 1}^{\infty}$ 是满足 $W_{n_{i}} \to W$ 的子序列. 根据计数引理, 对于所有的图 $F$ , $t (F, W_{n_{i}}) \to t (F, W)$ 成立. 由于 $F$ 密度的序列收敛, 对于所有的图 $F$ 我们有 $t (F, W_{n}) \to t (F, W)$ . 类似地, 对于所有的 $F$ 我们有 $t (F, W_{n}) \to t (F, U)$ . 因此, 对于所有的 $F$ 我们有 $t (F, U) = t (F, W)$ .

根据随后将介绍的引理 5.8, 我们最终得到 $U = W$ .

$□$

引理 5.8 (矩引理).

如果 graphon $U$ 和 $W$ 满足: 对于所有的图 $F$ , $t (F, W) = t (F, U)$ , 则 $δ_{□} (U, W) = 0$

概要.

令 $G (k, W)$ 表示 $k$ 顶点上的 $W$ 随机图 (见定义 2.0.1) . 可以证明, 对于任任意 $k$ 顶点图 $F$ , $Pr [G (k, W) ≅ F as labelld graph] = F^{'} \supseteq F \sum (- 1)^{E (F^{'}) - E (F)} t (F^{'}, W)$ 这意味着 $W$ 随机图的分布完全由 $F$ 密度决定. 所以 $G (k, W)$ 和 $G (k, U)$ 具有相同的分布.

令 $H (k, W)$ 是一个顶点集为 $[k]$ 的边加权的 $W$ 随机图. 边权重设置如下. 设 $x_{1}, \dots, x_{k} \sim$ 是 $[0, 1]$ 上的独立均匀随机变量. 设置 $(i, j)$ 的边权重为 $W (x_{i}, x_{j})$ .

我们不加证明的给出如下两个结论:

•	当 $k \to \infty$ , $δ_{□} (H (k, W), G (k, W)) \to 0$ (以概率 1 收敛) .
•	当 $k \to \infty$ 时 $δ_{1} (H (k, W), W) \to 0$ (以概率 1 收敛) .

由于 $G (k, W)$ 和 $G (k, U)$ 具有相同的分布, 所以从上述结论和三角不等式可以得出 $δ_{□} (W, U) = 0$ .

$□$

紧致性和矩引理的一个结论是 graphon 计数引理的 “逆” 也成立: $F$ 密度的界限暗含了着切割距离的上界. 证明留作练习.

推论 5.9 (逆计数引理). 对于任意 $ϵ > 0$ , 存在 $η > 0$ 和整数 $k > 0$ 满足: 如果 $U$ 和 $W$ 对于任意最多 $k$ 顶点图 $F$ 有 $∣ t (F, U) - t (F, W) ∣ \leq η$ 则 $δ_{□} (U, W) \leq ϵ$ .

笔记 5.10. 矩引理意味着可以通过其 $F$ 密度复原 graphon. 我们可能会问是否所有的 $F$ 密度都是必要的, 或者是否可以从有限多个密度中恢复一个 graphon? 例如, 我们已经看到, 如果 $W$ 是密度为 $p$ 的伪随机 graphon, 则 $t (K_{2}, W) = p$ , $t (C_{4}, W) = p^{4}$ ; 并且该 graphon 是由这些 $F$ 密度唯一确定的. 所以如果这两个等式成立, 则 $δ_{□} (W, p) = 0$ .

以这种方式从有限多个 $F$ 密度中恢复的 graphon 称为 “finitely forcible graphon”. 已知任意的阶跃函数和 half graphon $W (x, y) = 1_{x + y \geq 1}$ 是 finitely forcible graphon (Lovász and Sós 2008) . 更一般地说, 对于任何在 $[0, 1]$ 上单调递减的对称多项式 $p \in R [x, y]$ , $W (x, y) = 1_{p (x, y) \geq 0}$ 是 finitely forcible graphon (Lovász and Szegedy 2011) .

名字空间

视图

5. 紧致性的应用