seminar
这是暑假读 Yufei Zhao *Graph Theory and Additive Combinatorics* 时写下的正则性引理笔记。下面把边密度、ε-正则对、能量增量与塔型上界按证明顺序整理一遍；TikZ 示意图请直接看文末 PDF。
定义
Definition (边密度).
设 $X,Y$ 为图 $G$ 的顶点子集。记 $e_G(X,Y)$ 为 $X$ 与 $Y$ 之间的边数，
定义 $X$ 与 $Y$ 在 $G$ 中的 边密度 为
不引起歧义时省略下标 $G$。允许 $X$ 与 $Y$ 相交。
Definition ($\varepsilon$-正则对).
设 $G$ 为图，$U,W\subseteq V(G)$。称 $(U,W)$ 是 $G$ 中的一个 $\varepsilon$-正则对，如果对所有满足 $|A|\ge\varepsilon|U|$、$|B|\ge\varepsilon|W|$ 的 $A\subseteq U$、$B\subseteq W$，都有
若 $(U,W)$ 不是 $\varepsilon$-正则的，则存在 $A\subseteq U$、$B\subseteq W$ 满足 $|A|\ge\varepsilon|U|$、$|B|\ge\varepsilon|W|$，且 $\bigl|d(A,B)-d(U,W)\bigr|>\varepsilon$。称这样的 $A,B$ 为 $(U,W)$ 非 $\varepsilon$-正则的见证集。
Remark.
条件 $|A|\ge\varepsilon|U|$、$|B|\ge\varepsilon|W|$ 中的 $\varepsilon$ 与 $|d(A,B)-d(U,W)|\le\varepsilon$ 中的 $\varepsilon$ 作用不同：前者排除过小的子集（否则取单点可使密度为 $0$ 或 $1$），后者控制密度偏差。以下仍用同一个 $\varepsilon$。
Definition ($\varepsilon$-正则剖分).
设 $G$ 为图，$\mathcal{P}=\{V_1,\ldots,V_k\}$ 为 $V(G)$ 的一个剖分。称 $\mathcal{P}$ 是 $\varepsilon$-正则剖分，如果
Remark.
若 $|V_1|=\cdots=|V_k|$，则 定义（ε-正则剖分） 等价于：至多 $\varepsilon k^2$ 个有序块对 $(V_i,V_j)$ 不是 $\varepsilon$-正则的。求和包含 $i=j$。若 $|V_i|\le\varepsilon n$ 对每个 $i$ 成立，则对角项
Definition (加细).
设 $\mathcal{P}$、$\mathcal{Q}$ 为同一集合的两个剖分。称 $\mathcal{Q}$ 加细 $\mathcal{P}$，如果 $\mathcal{Q}$ 的每一块都包含于 $\mathcal{P}$ 的某一块。
以下固定 $n$ 顶点图 $G$，并在记号中省略对 $G$ 的依赖。
Definition (能量).
对 $U,W\subseteq V(G)$，定义
若 $\mathcal{P}_U=\{U_1,\ldots,U_k\}$ 是 $U$ 的剖分，$\mathcal{P}_W=\{W_1,\ldots,W_\ell\}$ 是 $W$ 的剖分，定义
对 $V(G)$ 的剖分 $\mathcal{P}=\{V_1,\ldots,V_k\}$，定义其 能量 为
由 $0\le d(V_i,V_j)\le 1$，对任意剖分有
Definition (均衡剖分).
称剖分为 均衡的，如果各块基数彼此相差至多 $1$，即 $\bigl||V_i|-|V_j|\bigr|\le 1$。把 $n$ 元集分成 $k$ 块时，这等价于每块大小为 $\lfloor n/k\rfloor$ 或 $\lceil n/k\rceil$。
定理
Theorem (Szemer\'{e}di 图正则性引理).
对每个 $\varepsilon>0$，存在常数 $M=M(\varepsilon)$，使得每个图都有一个至多 $M$ 块的 $\varepsilon$-正则剖分。
Lemma.
设 $U,W\subseteq V(G)$，$\mathcal{P}_U$ 为 $U$ 的剖分，$\mathcal{P}_W$ 为 $W$ 的剖分。则
Lemma.
设 $\mathcal{P}$、$\mathcal{P}'$ 为同一图的两个顶点剖分。若 $\mathcal{P}'$ 加细 $\mathcal{P}$，则 $q(\mathcal{P})\le q(\mathcal{P}')$。
Lemma.
设 $G$ 为 $n$ 顶点图。若 $(U,W)$ 不是 $\varepsilon$-正则的，且由 $A\subseteq U$、$B\subseteq W$ 见证，则
Lemma.
若 $V(G)$ 的剖分 $\mathcal{P}=\{V_1,\ldots,V_k\}$ 不是 $\varepsilon$-正则的，则存在 $\mathcal{P}$ 的加细 $\mathcal{Q}$，使得每个 $V_i$ 至多被分成 $2^{k+1}$ 块，并且
Theorem (Gowers, 1997).
存在常数 $c>0$，使得对所有充分小的 $\varepsilon>0$，都存在一张图，它没有任何块数少于 $\mathrm{tower}(\lceil\varepsilon^{-c}\rceil)$ 的 $\varepsilon$-正则剖分，其中
Theorem.
对每个 $\varepsilon>0$ 与每个正整数 $k$，存在常数 $M$，使得：对每个图 $G$ 以及 $V(G)$ 的至多 $k$ 块剖分 $\mathcal{P}_0$，都存在 $\mathcal{P}_0$ 的 $\varepsilon$-正则加细 $\mathcal{P}$，并且 $\mathcal{P}_0$ 的每一块在 $\mathcal{P}$ 中至多被分成 $M$ 块。
Theorem (均衡正则性引理).
对所有 $\varepsilon>0$ 与 $m_0$，存在常数 $M$，使得每个图都有一份 $\varepsilon$-正则的均衡剖分，块数 $k$ 满足 $m_0\le k\le M$。
证明
主定理（正则性引理） 的证明.
先证 引理（能量对单调）。记 $n=v(G)$，$\mathcal{P}_U=\{U_1,\ldots,U_k\}$，$\mathcal{P}_W=\{W_1,\ldots,W_\ell\}$，并设各块非空（空块对 $q$ 的贡献为零，可事先删去）。于是 $\{U_i\}_{i=1}^k$ 两两不交、并集为 $U$，故 $\sum_{i=1}^k |U_i|=|U|$；同理 $\sum_{j=1}^\ell |W_j|=|W|$。
独立地、均匀随机地取 $x\in U$、$y\in W$。设 $U_i$ 为 $\mathcal{P}_U$ 中含 $x$ 的唯一一块，$W_j$ 为 $\mathcal{P}_W$ 中含 $y$ 的唯一一块，并令随机变量
因 $x,y$ 独立且均匀，
于是
对任意 $(x,y)\in U\times W$，存在唯一的 $(i,j)$ 使 $x\in U_i$、$y\in W_j$，且 $xy\in E(G)$ 当且仅当 $(x,y)$ 被计入 $e(U_i,W_j)$。因此
从而
同理，$Z^2$ 在事件 $\{x\in U_i,\, y\in W_j\}$ 上取值 $d(U_i,W_j)^2$，故
最后一步用了 定义（能量）。再由同一定义，$q(U,W)=\frac{|U|\,|W|}{n^2}d(U,W)^2$，故
方差非负：$\mathrm{Var}(Z)=\mathbb{E}[Z^2]-\mathbb{E}[Z]^2\ge 0$，即 $\mathbb{E}[Z^2]\ge\mathbb{E}[Z]^2$。代入上面两式，
两边同乘 $\frac{|U|\,|W|}{n^2}$（该量为正），得 $q(\mathcal{P}_U,\mathcal{P}_W)\ge q(U,W)$。
再证 引理（能量单调）。记 $\mathcal{P}=\{V_1,\ldots,V_m\}$。由 定义（加细），$\mathcal{P}'$ 的每一块都落在某个 $V_i$ 内。对每个 $i$，令
则 $\mathcal{P}'_{V_i}$ 是 $V_i$ 的剖分，且 $\mathcal{P}'=\mathcal{P}'_{V_1}\cup\cdots\cup\mathcal{P}'_{V_m}$ 为不交并。把 $\mathcal{P}'_{V_i}$ 的块记为 $V_{i1},\ldots,V_{i k_i}$。由 定义（能量），
中间一步是把 $\mathcal{P}'$ 的块对按它们所属的 $\mathcal{P}$-块对 $(V_i,V_j)$ 分组。对每一对 $(i,j)$ 把 引理（能量对单调） 用于 $U=V_i$、$W=V_j$ 及剖分 $\mathcal{P}'_{V_i}$、$\mathcal{P}'_{V_j}$，得
对 $(i,j)\in[m]^2$ 求和，即 $q(\mathcal{P}')\ge q(\mathcal{P})$。
再证 引理（不规则对能量提升）。取 $\mathcal{P}_U=\{A,\,U\setminus A\}$、$\mathcal{P}_W=\{B,\,W\setminus B\}$（若某块为空则略去）。这给出 $U\times W$ 的至多四个块对
由 定义（能量），
沿用 引理（能量对单调） 中的随机变量 $Z$：独立均匀取 $x\in U$、$y\in W$，若 $(x,y)$ 落入块对 $(U',W')$ 则 $Z=d(U',W')$。把已证的 引理（能量对单调） 用于这一对剖分，得 $\mathbb{E}[Z]=d(U,W)$ 以及
因此
另一方面，按四个块对展开方差。记 $\mathcal{C}$ 为上述块对之集，则
每一项都 $\ge 0$，故
由见证条件，$|A|\ge\varepsilon|U|$、$|B|\ge\varepsilon|W|$，且 $|d(A,B)-d(U,W)|>\varepsilon$。平方后 $(d(A,B)-d(U,W))^2>\varepsilon^2$，因此
与前面的恒等式合在一起，
再证 引理（剖分能量提升）。记
若 $\overline{R}=\varnothing$，则 定义（ε-正则剖分） 左端为零，从而 $\mathcal{P}$ 已是 $\varepsilon$-正则剖分，与假设矛盾。故 $\overline{R}$ 非空。对每个 $(i,j)\in\overline{R}$，由 定义（ε-正则对） 存在见证集 $A_{i,j}\subseteq V_i$、$B_{i,j}\subseteq V_j$，满足
当 $i\neq j$ 时，$e(V_i,V_j)=e(V_j,V_i)$，故 $d(V_i,V_j)=d(V_j,V_i)$；此时可取同一对见证集，并令 $A_{i,j}=B_{j,i}$。当 $i=j$ 时，$(V_i,V_i)$ 的两个见证集不必相同，允许 $A_{i,i}$ 与 $B_{i,i}$ 不同。
令 $\mathcal{Q}$ 为用全部 $A_{i,j}$、$B_{i,j}$ 对 $\mathcal{P}$ 所作的公共加细。具体地，对每个 $V_i$，令
则 $\mathcal{Q}$ 在 $V_i$ 上的块是由 $\mathcal{F}_i$ 生成的布尔代数的原子，即形如
的非空交。这些原子两两不交、并集为 $V_i$。见图~\ref{fig:common-refine}。
（公共加细的示意图见文末 PDF。）
对每个固定的 $i$，统计 $|\mathcal{F}_i|$。在对称约定 $A_{i,j}=B_{j,i}$（$i\neq j$）之下：对每个 $j\neq i$，无论 $(i,j)$ 是否属于 $\overline{R}$，对应的切集至多一个；对角项至多两个（$A_{i,i}$ 与 $B_{i,i}$）。因此 $|\mathcal{F}_i|\le (k-1)+2=k+1$。由 $\mathcal{F}_i$ 的 $r$ 个子集出发，每个原子由一组符号 $(\sigma_S)_{S\in\mathcal{F}_i}\in\{0,1\}^r$ 决定，故原子至多 $2^{r}\le 2^{k+1}$ 个。于是 $\mathcal{Q}$ 把每个 $V_i$ 至多分成 $2^{k+1}$ 块，从而 $|\mathcal{Q}|\le k\cdot 2^{k+1}$。
记 $\mathcal{Q}_i$ 为 $\mathcal{Q}$ 在 $V_i$ 上诱导的剖分，则 $\mathcal{Q}=\bigcup_{i=1}^k \mathcal{Q}_i$。设 $\mathcal{Q}_i=\{V_{i\alpha}\}_\alpha$。由 定义（能量），
对 $(i,j)\in R$，$\mathcal{Q}_i$ 是 $V_i$ 的剖分、$\mathcal{Q}_j$ 是 $V_j$ 的剖分，由 引理（能量对单调），
对 $(i,j)\in\overline{R}$，有 $A_{i,j}\in\mathcal{F}_i$。每个原子是与 $A_{i,j}$ 或与 $V_i\setminus A_{i,j}$ 的交，故每个原子整块落在 $A_{i,j}$ 内或整块落在其补集内。因此 $A_{i,j}$ 是 $\mathcal{Q}_i$ 中若干原子的并，$\mathcal{Q}_i$ 加细 $\{A_{i,j},\,V_i\setminus A_{i,j}\}$。同理 $\mathcal{Q}_j$ 加细 $\{B_{i,j},\,V_j\setminus B_{i,j}\}$。先用 引理（能量对单调），
再用 引理（不规则对能量提升）（取 $U=V_i$、$W=V_j$、$A=A_{i,j}$、$B=B_{i,j}$），
两式合起来，$q(\mathcal{Q}_i,\mathcal{Q}_j)>q(V_i,V_j)+\frac{\varepsilon^4 |V_i|\,|V_j|}{n^2}$。因此
因 $\mathcal{P}$ 不是 $\varepsilon$-正则的，由 定义（ε-正则剖分） 的否定，
故
于是 $q(\mathcal{Q})>q(\mathcal{P})+\varepsilon^5$。
加细必须对所有 $(i,j)\in\overline{R}$ 同时进行。若先取一对 $(i_0,j_0)\in\overline{R}$，用 $A_{i_0,j_0}$、$B_{i_0,j_0}$ 加细得到 $\mathcal{P}'$，则对另一对 $(i,j)\in\overline{R}\setminus\{(i_0,j_0)\}$，$\mathcal{P}'$ 把 $V_i$ 切成了若干子块 $V_i'$。原来的见证集限制到 $V_i'$ 上未必仍满足 $|A_{i,j}\cap V_i'|\ge\varepsilon|V_i'|$，且 $(V_i',V_j')$ 本身也可能已经是 $\varepsilon$-正则的。此时 引理（不规则对能量提升） 不能用于 $(V_i',V_j')$，无法把 $\overline{R}$ 上的 $\varepsilon^4 |V_i||V_j|/n^2$ 全部加起来。同时加细则对 $\overline{R}$ 中每一对都保留了见证集切出的两块，上述求和成立。
现在证明 主定理（正则性引理）。令 $\mathcal{P}^{(0)}=\{V(G)\}$。由 定义（能量），
若 $\mathcal{P}^{(0)}$ 已是 $\varepsilon$-正则的，则取 $M=1$ 即可，证明结束。以下设否则。对 $s\ge 0$，若 $\mathcal{P}^{(s)}$ 不是 $\varepsilon$-正则的，由 引理（剖分能量提升） 得到加细 $\mathcal{P}^{(s+1)}$，满足
归纳即得：对每个使 $\mathcal{P}^{(0)},\ldots,\mathcal{P}^{(s-1)}$ 均非 $\varepsilon$-正则的 $s$，
由 定义（能量） 又有 $q(\mathcal{P}^{(s)})\le 1$，故 $s\varepsilon^5<1$，即 $s<\varepsilon^{-5}$。因此必存在 $s_*<\varepsilon^{-5}$ 使 $\mathcal{P}^{(s_*)}$ 为 $\varepsilon$-正则剖分（否则可无限迭代，与 $s<\varepsilon^{-5}$ 矛盾）。由构造，一旦某步得到 $\varepsilon$-正则剖分，过程即停止。
记 $k_s=\lvert\mathcal{P}^{(s)}\rvert$。则 $k_0=1$，且由 引理（剖分能量提升），$k_{s+1}\le k_s\cdot 2^{k_s+1}$。先验证：对整数 $k\ge 1$ 有 $2k\le 2^{k}$。$k=1,2$ 时等号成立；若对 $k\ge 2$ 已有 $2k\le 2^{k}$，则
其中 $2\le 2^{k}$（$k\ge 1$）。因此对一切 $k\ge 1$，
从而 $k_{s+1}\le 2^{2k_s}$。
按 Gowers 定理 中的记号，$\mathrm{tower}(1)=2$，$\mathrm{tower}(m+1)=2^{\mathrm{tower}(m)}$。下证 $k_s\le \mathrm{tower}(2s)$ 对 $s\ge 1$ 成立。$s=1$ 时 $k_1\le 2^{2k_0}=2^{2}=4=\mathrm{tower}(2)$。设 $k_s\le\mathrm{tower}(2s)$。则
而 $\mathrm{tower}(2s+1)=2^{\mathrm{tower}(2s)}$，$\mathrm{tower}(2s+2)=2^{\mathrm{tower}(2s+1)}=2^{2^{\mathrm{tower}(2s)}}$。因 $\mathrm{tower}(2s)\ge 2$，有 $2\,\mathrm{tower}(2s)\le 2^{\mathrm{tower}(2s)}=\mathrm{tower}(2s+1)$，故
于是 $k_{s+1}\le\mathrm{tower}(2(s+1))$。由 $s_*<\varepsilon^{-5}$ 得 $2s_*<2\varepsilon^{-5}$，从而
取 $M(\varepsilon)=\mathrm{tower}(\lceil 2\varepsilon^{-5}\rceil)$ 即可。
∎
Remark.
Gowers 定理 表明上述塔型上界不能改成 $\varepsilon$ 的多项式（甚至不能改成固定高度的指数塔）。证明见 Gowers (1997) 或 Moshkovitz--Shapira (2016)，此处略去。
定义（ε-正则剖分） 允许少数块对不规则。半图给出反例，说明不规则对不能从定义中删去，见 GTAC Exercise~2.1.24。
加细版正则性引理 的证明与 主定理（正则性引理） 相同，只需把初始剖分换成给定的 $\mathcal{P}_0$。
均衡正则性引理 的证明对上述算法作两处修改：初始取任意 $m_0$ 块均衡剖分；每次用见证集加细后，再把各块切成大小约为 $|V(G)|/m$ 的均衡小块（$m=\bigl\lfloor 100\,|\mathcal{P}'|\,\varepsilon^{-5}\bigr\rfloor$ 即可）。加细步使能量增加至少 $\varepsilon^5$，均衡化步使能量下降 $o(\varepsilon^5)$，故每步净增 $\ge\varepsilon^5/2$，仍在 $O(\varepsilon^{-5})$ 步后终止。下界 $m_0$ 用于丢掉块内边：块内边至多 $n^2/k$ 条，取 $m_0\ge 1/\varepsilon$ 即可忽略。
Download the original write-up here.