3. 正则性和计数引理

我们现在介绍一系列用来证明定理 1.23 的工具.

定理 3.1 (记数引理). 对于 graphon $W,U$ 和图 $F$, 我们有$$|t(F,W)-t(F,U)|\le |E(F)|{\delta }_{\square }(W,U)$$

证明. 我们只需证明 $|t(F,W)-t(F,U)|\le |E(F)|\Vert W-U{\Vert }_{\square }$ 即可 (该不等式两边对 $\varphi$ 取 inf 即可得到引理中的不等式) .

回顾切割范数的定义 $\Vert W{\Vert }_{\square }={\sup }_{S,T\subseteq [0,1]}\left|{\int }_{S\times T}W\right|$ . 现在我们证明一个切割范数很有用的表述: 对于可测的函数 $u$ 和 $v$, $$\underset{S,T\subseteq [0,1]}{\sup }\left|{\int }_{S\times T}W\right|=\underset{u,v:[0,1]\to [0,1]}{\sup }\left|{\int }_{[0,1{]}^2}W(x,y)u(x)v(y)dxdy\right|$$该等式成立的原因如下: 我们取 $u=1_S$ 和 $v=1_T$ , 右边等于左边, 所以左边小于等于右边; 被积函数对于 $u,v$ 是双线性的, 所以极值在 $u,v$ 取 0 或 1 时取到, 所以右边小于等于左边. 现在我们考虑 $F=K_3$ 时的情形. $$\begin{array}{rl}t\left(K_3,W\right)-t\left(K_3,U\right)=& \int ((W(x,y)W(x,z)W(y,z)-U(x,y)U(x,z)U(y,z))dxdydz\\ =& \int (W-U)(x,y)W(x,z)W(y,z)dxdydz\\ +& \int U(x,y)(W-U)(x,z)W(y,z)dxdydz\\ +& \int U(x,y)U(x,z)(W-U)(y,z)dxdydz\end{array}$$以第一项为例, 对于固定的 $z$, $$\left|\int (W-U)(x,y)W(x,z)W(y,z)dxdydz\right|\le \Vert W-U{\Vert }_{\square }$$对于第二项第三项我们有同样的结果. 因此, 总上界为 $3\Vert W-U{\Vert }_{\square }$, 这是我们想要的.

推广 $F=K_3$ 的证明, 对于一般图 $F$, 我们有$$\begin{array}{rl}|t(F,W)-t(F,U)|& =\left|\int \left(\prod _{u_i{v}_i\in E}W\left(u_i,v_i\right)-\prod _{u_i{v}_i\in E}U\left(u_i,v_i\right)\right)\prod _{v\in V}dv\right|\\ & \le \sum _{i=1}^{|E|}\left|\int \left(\prod _{j=1}^{i-1}U\left(u_j,v_j\right)\left(W\left(u_i,v_i\right)-U\left(u_i,v_i\right)\right)\prod _{k=i+1}^{|E|}W\left(u_k,v_k\right)\right)\prod _{v\in V}dv\right|\end{array}$$如果我们固定所有其他无关变量 (除 $u_i$ 和 $v_i$ 之外的所有变量) , 我们发现求和中的每个绝对值项都以 $\Vert W-U{\Vert }_{\square }$ 为上界. 所以我们有切割函数 $|t(F,W)-$ $t(F,U)|\le |E(F)|{\delta }_{\square }(W,U)$.

$\square$

我们现在为 graphon $W$ 引入一个 “平均函数”.

定义 3.2. 对于 $[0,1]$ 的一个划分 $\mathcal{P}=\left\{S_1,\dots ,S_k\right\}$ (要求划分的子集是可测集) , 以及对称可测函数 $W:[0,1{]}^2\to \mathbb{R}$ , 定义 stepping 算子 $W_{\mathcal{P}}:[0,1{]}^2\to \mathbb{R}$, 该算子在 $S_i\times S_j$ 上的取值为常数, 满足: 如果 $(x,y)\in S_i\times S_j$, $W_{\mathcal{P}}(x,y)=\frac{1}{\lambda \left(S_i\right)\lambda \left(S_j\right)}{\int }_{S_i\times S_j}W$. (我们忽略分母为 0 时的定义, 因为此时集合的测度为零) .

实际上, 这是希尔伯特空间 $L^2\left([0,1{]}^2\right)$ 上对每一 $S_i\times S_j$ 到常值函数的投影. 也可以看作是关于由 $S_i\times S_j$ 生成的 $\sigma$ -代数的条件期望.

定理 3.3 (弱正则性引理). 对于任何 $ϵ>0$ 和任何 graphon $W:[0,1{]}^2\to \mathbb{R}$, 存在 $[0,1]$ 的划分 $\mathcal{P}$ (要求划分得到的可测子集测度不超过 $4^{1/{ϵ}^2}$) , 满足 ${\Vert W-W_{\mathcal{P}}\Vert }_{\square }\le ϵ$.

定义 3.4. 给定图 $G$, $V(G)$ 的划分 $\mathcal{P}=\left\{V_1,\dots ,V_k\right\}$ 被称为是弱 $ϵ$ -正则的, 如果对于所有的 $A,B\subset V(G)$ 有$$\left|e(A,B)-\sum _{i,j=1}^{k}d\left(V_i,V_j\right)|A\cap V_i||B\cap V_j|\right|\le ϵ|V(G){|}^2$$

这与我们在介绍定理 1.1.5 时看到的概念相似但不同.

定理 3.5 (图的弱正则性引理).

对于任意 $ϵ>0$ 和图 $G$, 存在 $V(G)$ 的弱 $ϵ$ -正则划分, 最多可分为 $4^{1/{ϵ}^2}$ 个块.

引理 3.6 ($L^2$ 能量递增引理). 令 $W$ 是一个 graphon, $\mathcal{P}$ 是 $[0,1]$ 的划分, 满足 ${\Vert W-W_{\mathcal{P}}\Vert }_{\square }>ϵ$. 存在 $\mathcal{P}$ 的加细 ${\mathcal{P}}^{\prime }$, ${\mathcal{P}}^{\prime }$ 将 $\mathcal{P}$ 中的每个块划分成不超过 4 个块, 并保证$${\Vert W_{{\mathcal{P}}^{\prime }}\Vert }_2^2>{\Vert W_{\mathcal{P}}\Vert }_2^2+{ϵ}^2$$

证明. 因为 ${\Vert W-W_{\mathcal{P}}\Vert }_{\square }>ϵ$, 所以存在子集 $S,T\subset [0,1]$ 使得 $\left|{\int }_{S\times T}\left(W-W_{\mathcal{P}}\right)\right|>ϵ$. 令 ${\mathcal{P}}^{\prime }$ 是 $\mathcal{P}$ 通过引入 $S$ 和 $T$ 的加细 (根据每个部分是否在 $S\backslash T$, $T\backslash S$, $S\cap T$ , $\bar{S}\cap \bar{T}$ 来再次划分) , 每个部分最多被分为 4 个子块.

定义 $⟨W,U⟩:=\int WU$. 查看 “平均函数”$W_{\mathcal{P}}$ 的定义, 可以轻松得到 $⟨W_{\mathcal{P}},W_{\mathcal{P}}⟩=⟨W_{{\mathcal{P}}^{\prime }},W_{\mathcal{P}}⟩$. 从而 $⟨W_{{\mathcal{P}}^{\prime }}-W_{\mathcal{P}},W_{\mathcal{P}}⟩=0$. 根据勾股定理, $${\Vert W_{{\mathcal{P}}^{\prime }}\Vert }_2^2={\Vert W_{{\mathcal{P}}^{\prime }}-W_{\mathcal{P}}\Vert }_2^2+{\Vert W_{\mathcal{P}}\Vert }_2^2>{\Vert W_{\mathcal{P}}\Vert }_2^2+{ϵ}^2$$其中后一个不等式来自 Cauchy-Schwarz 不等式, $${\Vert 1_{S\times T}\Vert }_2{\Vert W_{{\mathcal{P}}^{\prime }}-W_{\mathcal{P}}\Vert }_2\ge \left|⟨W_{{\mathcal{P}}^{\prime }}-W_{\mathcal{P}},1_{S\times T}⟩\right|=\left|⟨W-W_{\mathcal{P}},1_{S\times T}⟩\right|>ϵ$$

$\square$

命题 3.7. 对于任何 $ϵ>0$、graphon $W$ 和 $[0,1]$ 上的划分 ${\mathcal{P}}_0$ , 存在划分 ${\mathcal{P}}_0$ 的加细 $\mathcal{P}$ 将 $[0,1]$ 分成不超过 $4^{1/{ϵ}^2}$ 个块, 并保证 ${\Vert W-W_{\mathcal{P}}\Vert }_{\square }\le ϵ$.

这个命题告诉我们, 从任何给定的划分开始, 关于正则性的论证仍然有效.

证明. 我们反复应用引理 3.6 来得到 $[0,1]$ 上的划分 ${\mathcal{P}}_0,{\mathcal{P}}_1,\dots$ . 每一次加细操作, 我们要么有 ${\Vert W-W_{\mathcal{P}}\Vert }_{\square }\le ϵ$ 从而停止迭代, 要么有 ${\Vert W_{{\mathcal{P}}^{\prime }}\Vert }_2^2>{\Vert W_{\mathcal{P}}\Vert }_2^2+{ϵ}^2$.

因为 ${\Vert W_{P_i}\Vert }_2^2\le 1$, 我们保证在少于 ${ϵ}^{-2}$ 次加细操作后停止. 我们还知道每个块在每一次加细操作后最多分为 4 个部分, 因此最终最多分为 $4^{{ϵ}^{-2}}$ 个块.

$\square$

下面我们介绍一个计算机科学中的相关结论, MAXCUT 问题: 给定一个图 $G$, 我们想在所有顶点子集 $S\subset V(G)$ 中寻求 $\max e(S,\bar{S})$. Goemans 和 Williamson 给出了多项式时间近似算法, 该算法理论上能够做到最优值 $0.878$ 的近似. 唯一游戏猜想 (Unique games conjecture: Khot, Kindler, Mossel, and O’Donnell 2007) 如果成立, 我们将不可能获得比 G-W 算法更好的近似值. 事实上我们还知道, 近似超过 $\frac{16}{17}\approx 0.941$ 是 NP-hard 的 (Håstad 2001) .

另一方面, 对于稠密图, MAXCUT 问题变得很容易解决. 对于 $n$ 顶点图, 我们有绝对误差小于 $ϵn^2$ 的多项式时间算法, 其中 $ϵ>0$ 是一个固定的常数. 算法的思路是应用弱正则性引理, 通过对每一部分的所有可能的划分的大小进行暴力搜索. 这一应用正是研究弱正则性引理的原始动机之一.