1. 定理陈述和证明

定理陈述和证明

Szemerédi 正则性引理是图论中最重要的结果之一, 尤其是对比较大的图的研究非常重要. 引理指出, 对于所有大的稠密图 $G$, 我们可以将 $G$ 的顶点划分为有限数量的部分, 以便大多数不同部分之间的边表现出 “类似随机” (“random-like”) 的特征.

为了给出 “类似随机” 的概念, 我们首先陈述一些定义.

定义 1.1.

令 $X$ 和 $Y$ 是图 $G$ 中的顶点集. 令 $e_G(X,Y)$ 为 $X$ 和 $Y$ 之间的边数; 即, $$e_G(X,Y)=|\{(x,y)\in X\times Y\mid xy\in E(G)\}|$$由此, 我们可以定义 $X$ 和 $Y$ 之间的边密度为$$d_G(X,Y)=\frac{e_G(X,Y)}{|X||Y|}$$

如果上下文表述清楚, 我们将省略下标 $G$.

定义 1.2 ($ϵ$ -regular pair).

令 $G$ 是一个图并且 $X,Y\subseteq V(G)$ 我们称 $(X,Y)$ 为 $G$ 中的一个 $ϵ$ -正则对, 如果对于任意满足 $|A|\ge ϵ|X|,|B|\ge ϵ|Y|$ 的子集 $A\subset X,B\subset Y$ , 都有$$|d(A,B)-d(X,Y)|\le ϵ$$

(...)$ϵ$-正则对的子集对在边密度上与原对相似

笔记 1.3. 定义 1.2 中不同的 $ϵ$ 扮演着不同的角色, 但区分它们并不重要. 为了方便, 我们只使用一个 $ϵ$ 来表示.

如果满足 $A\ge ϵ|X|,|B|\ge ϵ|Y|$ 的子集 $A\subset X,B\subset Y$ 有 $|d(A,B)-d(X,Y)|>ϵ$, 则 $(X,Y)$ 不是 $ϵ$ -正则的. 我们把这样的子集 $A\subset X,B\subset Y$ 称为见证 $X,Y$ 非 $ϵ$ -正则的子集.

定义 1.4 ($ϵ$ -regular partition). $V(G)$ 的一个划分 ¹$\mathcal{P}=\left\{V_1,\dots ,V_k\right\}$ 是 $ϵ$ -正则划分, 如果$$\sum _{\genfrac{}{}{0ex}{}{(i,j)\in [k{]}^2}{(V_i,V_j)\mathrm{not}ϵ-\mathrm{regular}}}\left|V_i\right|\left|V_j\right|\le ϵ|V(G){|}^2$$

请注意, 此定义允许一些非正则的对, 只要它们的总大小不太大. 现在我们来陈述正则性引理.

定理 1.5 (Szemerédi 正则性引理 1978). 对于任意 $ϵ>0$, 存在一个常数 $M$, 使得每个图都有一个 $ϵ$ -正则划分, 最多可分为 $M$ 个区域.

更强版本的引理允许我们找到一个均衡的划分——也就是说, 划分的每个部分的大小都是 $\lfloor \frac{n}{k}\rfloor$ 或 $\lceil \frac{n}{k}\rceil$ , 其中 $n$ 是顶点数, $k$ 是划分的块数.

定理 1.6. [Szemerédi 正则性引理均衡版本 1978] 对于任意 $ϵ>0$ 和 $m_0$, 存在一个常数 $M$, 使得每个图都有一个 $ϵ$ -均衡正则划分, 顶点集被划分成 $k$ 部分, 其中 $m_0\le k\le M$.

我们先说下证明的主要思路. 我们将根据以下算法生成我们想要的划分:

•	从简单的划分开始 (1 个部分) .
•	如果划分不是 $ϵ$ - 正则的: ∘ 对于每个不是 $ϵ$ -正则的 $\left(V_i,V_j\right)$, 找到见证 $\left(V_i,V_j\right)$ 的非正则性的子集 $A^{i,j}\subset V_i$ 和 $A^{j,i}\subset V_j$ . ∘ 对划分加细 2, 消除所有见证非正则性的子集 $A^{i,j}$.

如果此过程在有限步后停止, 则将成功证明正则性引理. 为了表明我们将在有限的时间内停止, 我们将使用一种称作能量增量参数 (energy increment argument) 的技术.

定义 1.7 (Energy).

设 $U,W\subseteq V(G)$ , $n=|V(G)|$. 定义$$q(U,W)=\frac{|U||W|}{n^2}d(U,W{)}^2.$$对于 $U$ 的划分 ${\mathcal{P}}_U=\left\{U_1,\dots ,U_k\right\}$ 和 $W$ 的划分 ${\mathcal{P}}_W=\left\{W_1,\dots ,W_l\right\}$ 定义$$q\left({\mathcal{P}}_U,{\mathcal{P}}_W\right)=\sum _{i=1}^k\sum _{j=1}^{l}q\left(U_i,W_j\right).$$最后, 对于 $V(G)$ 的划分 $\mathcal{P}=\left\{V_1,\dots ,V_k\right\}$, 定义 $\mathcal{P}$ 的能量为 $q(\mathcal{P},\mathcal{P})$. 具体的, $$q(\mathcal{P})=\sum _{i=1}^k\sum _{j=1}^{k}q\left(V_i,V_j\right)=\sum _{i=1}^k\sum _{j=1}^k\frac{\left|V_i\right|\left|V_j\right|}{n^2}d{\left(V_i,V_j\right)}^2.$$

因为边密度以 1 为上界, 所以能量在 0 和 1 之间:

$$q(\mathcal{P})=\sum _{i=1}^k\sum _{j=1}^k\frac{\left|V_i\right|\left|V_j\right|}{n^2}d{\left(V_i,V_j\right)}^2\le \sum _{i=1}^k\sum _{j=1}^k\frac{\left|V_i\right|\left|V_j\right|}{n^2}=1$$

为了能够证明 Szemerédi 正则性引理, 我们将介绍证明一系列引理, 这些引理将表明能量不会在加细时减少. 如果我们加细的划分非正则, 则能量可以显著增加.

引理 1.8. 对于顶点集 $U$ 和 $\mathrm{W}$ 的任何划分 ${\mathcal{P}}_U$ 和 ${\mathcal{P}}_{\mathrm{W}}$,$$q\left({\mathcal{P}}_U,{\mathcal{P}}_W\right)\ge q(U,W)$$

证明. 设 ${\mathcal{P}}_U=\left\{U_1,\dots ,U_k\right\}$ 和 ${\mathcal{P}}_W=\left\{W_1,\dots ,W_l\right\}$.

在 $U$ 中均匀随机选择 $x$ , 在 $W$ 中均匀随机选择 $y$ . 令 $U_i$ 是包含 $x$ 的 ${\mathcal{P}}_U$ 中的一个块, 而 $W_j$ 是包含 $y$ 的 ${\mathcal{P}}_{\mathrm{W}}$ 中的一个块. 然后定义随机变量 $Z=d\left(U_i,W_j\right)$, 它的期望是$$\mathbb{E}[Z]=\sum _{i=1}^k\sum _{j=1}^l\frac{\left|U_i\right|}{|U|}\frac{\left|W_j\right|}{|W|}d\left(U_i,W_j\right)=\frac{e(U,W)}{|U||W|}=d(U,W)$$二阶矩为$$\mathbb{E}\left[Z^2\right]=\sum _{i=1}^k\sum _{j=1}^l\frac{\left|U_i\right|}{|U|}\frac{\left|W_j\right|}{|W|}d{\left(U_i,W_j\right)}^2=\frac{n^2}{|U||W|}q\left({\mathcal{P}}_U,{\mathcal{P}}_W\right)$$显然我们有 $\mathbb{E}\left[Z^2\right]\ge \mathbb{E}[Z{]}^2$, 这意味着引理成立.

$\square$

引理 1.9. 如果 ${\mathcal{P}}^{\prime }$ 是 $\mathcal{P}$ 的加细, 则 $q\left({\mathcal{P}}^{\prime }\right)\ge q(\mathcal{P})$.

证明. 令 $\mathcal{P}=\left\{V_1,\dots ,V_m\right\}$ 并将引理 1.8 应用到每个 $\left(V_i,V_j\right)$ 对.

$\square$

引理 1.10 (能量提升引理). 如果 $(U,W)$ 不是 $ϵ$ -正则的, 且反例是 $U_1\subset U$ 和 $W_1\subset W$ (也就是说 $|d(U_1,W_1)-d(U,W)|>ϵ$) , 那么$$q\left(\left\{U_1,U\backslash U_1\right\},\left\{W_1,W\backslash W_1\right\}\right)>q(U,W)+{ϵ}^4\frac{|U||W|}{n^2}$$

证明. 定义 $Z$ 和引理 1.8 证明中的相同. 然后$$\begin{array}{rl}\mathrm{Var}(Z)& =\mathbb{E}\left[Z^2\right]-\mathbb{E}[Z{]}^2\\ & =\frac{n^2}{|U||W|}\left(q\left(\left\{U_1,U\backslash U_1\right\},\left\{W_1,W\backslash W_1\right\}\right)-q(U,W)\right)\end{array}$$观察到 $|Z-\mathbb{E}[Z]|=\left|d\left(U_1,W_1\right)-d(U,W)\right|$ 的概率是 $\frac{|U_1|}{|U|}\frac{|W_1|}{|U|}$ (对应于 $x\in U_1$ 且 $y\in W_1$) , 所以$$\begin{array}{rl}\mathrm{Var}(Z)& =\mathbb{E}\left[(Z-\mathbb{E}[Z]{)}^2\right]\\ & \ge \frac{\left|U_1\right|}{|U|}\frac{\left|W_1\right|}{|W|}{\left(d\left(U_1,W_1\right)-d(U,W)\right)}^2\\ & >ϵ\cdot ϵ\cdot {ϵ}^2\end{array}$$证毕.

$\square$

引理 1.11. 如果 $V(G)$ 的划分 $\mathcal{P}=\left\{V_1,\dots ,V_k\right\}$ 不是 $ϵ$ -正则的, 则存在 $\mathcal{P}$ 的加细 $\mathcal{Q}$, 其中每个 $V_i$ 最多分为 $2^k$ 个部分, 且 $q(\mathcal{Q})\ge q(\mathcal{P})+{ϵ}^5$.

证明. 对于使得 $\left(V_i,V_j\right)$ 非 $ϵ$ -正则的所有 $(i,j)$ , 找到见证非正则性的子集 $A^{i,j}\subset V_i$ 和 $A^{j,i}\subset V_j$ (对所有非正则对同时进行) . 令 $\mathcal{Q}$ 是 $\mathcal{P}$ 根据这些 $A^{i,j}$ 形成的公共加细 ³. 每个 $V_i$ 根据需要最多分为 $2^k$ 个部分. 然后$$\begin{array}{rl}q(\mathcal{Q})& =\sum _{(i,j)\in [k{]}^2}q\left({\mathcal{Q}}_{V_i},{\mathcal{Q}}_{V_j}\right)\\ & =\sum _{\genfrac{}{}{0ex}{}{(i,j)\in [k{]}^2}{(V_i,V_j)ϵ\text{ -regular }}}q\left({\mathcal{Q}}_{V_i},{\mathcal{Q}}_{V_j}\right)+\sum _{\genfrac{}{}{0ex}{}{(i,j)\in [k{]}^2}{(V_i{V}_j)\text{ not }ϵ\text{ -regular }}}q\left({\mathcal{Q}}_{V_i},{\mathcal{Q}}_{V_j}\right)\end{array}$$其中 ${\mathcal{Q}}_{V_i}$ 是 $\mathcal{Q}$ 给出的 $V_i$ 的划分. 通过引理 1.8, 上面等式的值至少为$$\sum _{\genfrac{}{}{0ex}{}{(i,j)\in [k{]}^2}{(V_i{V}_j)ϵ\text{ -regular }}}q\left(V_i,V_j\right)+\sum _{\genfrac{}{}{0ex}{}{(i,j)\in [k{]}^2}{(V_i{V}_j)\text{ not }ϵ\text{ -regular }}}q\left(\left\{A^{i,j},V_i\backslash A^{i,j}\right\},\left\{A^{j,i},V_j\backslash A^{j,i}\right\}\right)$$由于在创建 $\mathcal{Q}$ 时 $V_i$ 被 $A^{i,j}$ 切分, 所以 ${\mathcal{Q}}_{V_i}$ 是 $\left\{A^{i,j},V_i\backslash A^{i,j}\right\}$ 的一个加细. 根据引理 1.10, 上述总和至少为$$\sum _{(i,j)\in [k{]}^2}q\left(V_i,V_j\right)+\sum _{\genfrac{}{}{0ex}{}{(i,j)\in [k{]}^2}{(V_i{V}_j)\text{ not }ϵ\text{ -regular }}}{ϵ}^4\frac{\left|V_i\right|\left|V_j\right|}{n^2}$$因为 $\mathcal{P}$ 不是 $ϵ$ -正则的, 所以第二个总和至少是 ${ϵ}^5$, 我们推导出所需的不等式.

$\square$

现在我们可以来证明 Szemerédi 正则性引理.

定理 1.5.

从一个简单的划分开始. 每当当前划分不是 $ϵ$ -正则时, 重复应用引理 1.11. 根据能量的定义, $0\le q(\mathcal{P})\le 1$. 然而, 根据引理 1.11, $q(\mathcal{P})$ 在每次迭代中至少增加 ${ϵ}^5$. 所以我们将在最多 ${ϵ}^{-5}$ 步后停止, 从而产生 $ϵ$ -正则划分.

$\square$

一个有趣的问题是这个算法给出划分的块的数量是多少? 如果 $\mathcal{P}$ 有 $k$ 个块, 引理 1.11 将 $\mathcal{P}$ 加细为最多 $k{2}^k\le 2^{2^k}$ 个块. 迭代 ${ϵ}^{-5}$ 次会产生 $\underset{2{ϵ}^{-5}{2}^{\prime }\mathrm{s}}{\underbrace{2^{2^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}}}$ 的上限. 因为在上述证明中我们没有力求加细的块数是最小的, 人们可能会认为更好的证明可以产生更好的上界. 令人惊讶的是, 这本质上就是最好的上界.

定理 1.12 (Gowers 1997). 存在一个常数 $c>0$ 使得对于所有足够小的 $ϵ>0$ , 存在一个图, 其所有 $ϵ$ -正则的划分至少需要 $\underset{\ge {ϵ}^{-c}{2}^{\prime }\mathrm{s}}{\underbrace{2^{2^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}}}$ 个块.

该证明的另一个问题是我们如何使分割均衡? 下面是对上述算法的修改, 它证明了定理 1.6:

•	首先将图形任意平均地划分为 $m_0$ 个部分.
•	如果划分不是 $ϵ$ -正则的: ∘ 使用见证非正则性的对来加细划分. ∘ 进一步加细并调整来使划分均衡. 为此, 我们将移动和合并具有少量顶点的集合.

与以前一样, 加细步骤至少增加了 ${ϵ}^5$ 的能量. 在调整步骤中, 能量可能会下降, 但事实证明, 这种下降不会影响最终结果. 最后, 能量增加的仍然是 $\Omega \left({ϵ}^5\right)$, 这使得进程在 $O\left({ϵ}^{-5}\right)$ 步骤后终止.