10. Szemerédi 正则性引理的谱证明

我们之前使用能量递增的思路证明了 Szemerédi 正则性引理. 我们现在解释另一种使用谱图论的证明方法. 就像上面关于超图正则性的讨论一样, 这个讨论将略过一些细节.

给定一个 $n$ 顶点图 $G$, 其邻接矩阵记为 $A_G$. 由于邻接矩阵始终是实对称矩阵, 因此, 它一定具有实数特征值, 并且可以找到一组特征向量的标准正交基. 假设 $A_G$ 具有特征值 ${\lambda }_i$ ($1\le i\le n$) , 其基于绝对值递减的排序为: $\left|{\lambda }_1\right|\ge \left|{\lambda }_2\right|\ge \cdots \ge \left|{\lambda }_n\right|$. 我们一个谱分解$$A_G=\sum _{i=1}^n{\lambda }_i{u}_i{u}_i^T$$其中 $u_i$ 是单位特征向量, 满足 $A_G{u}_i={\lambda }_i{u}_i$. 另外注意到$$\begin{array}{rl}\sum _{i=1}^n{\lambda }_i^2& =\mathrm{tr}\left(A^2\right)\\ & =\sum _{i=1}^n\sum _{j=1}^n{A}_G(i,j{)}^2\\ & =2e(G)\\ & \le n^2\end{array}$$其中第二个等号成立是因为 $A$ 是对称的, $\mathrm{tr}(AA)={\sum }_{i=1}^n(AA{)}_{ii}={\sum }_{i=1}^n{\sum }_{j=1}^m{A}_{ij}{A}_{ji}={\sum }_{i=1}^n{\sum }_{j=1}^m{A}_{ij}^2$.

引理 10.1. ${\lambda }_i$ 的定义如上, 我们有$$\left|{\lambda }_i\right|\le \frac{n}{\sqrt{i}}$$

证明. 如果 $\left|{\lambda }_k\right|>\frac{n}{\sqrt{k}}$ 对某些 $k$ 成立, 则 ${\sum }_{i=1}^k{\lambda }_i^2>n^2$, 矛盾.

$\square$

引理 10.2. 取 $ϵ>0$, $F:\mathbb{N}\to \mathbb{N}$ 是一个任意的 “增长函数”, 满足对所有的 $j$ , 有 $F(j)\ge j$. 则存在 $C=C(ϵ,F)$ 使得对于所有如前所述的 $G,A_G$ , 存在 $J<C$ 满足$$\sum _{J\le i<F(J)}{\lambda }_i^2\le ϵn^2$$

证明. 令 $J_1=1$ , $J_{i+1}=F\left(J_i\right)$ ($i\ge 1$) . 对所有的 $k\le \frac{1}{ϵ}$, ${\sum }_{J_k\le i<J_{k+1}}{\lambda }_i^2>ϵn^2$ 不总是成立, 否则总和将大于 $n^2$. 因此, 上述不等式一定对于对某 $J=J(k)$ 成立, 其中 $k\le \frac{1}{ϵ}$. 因此, $J$ 是有界的; 特别的, $J<F(F(\dots F(1)\dots ))$, 其中 $F$ 迭代 $\frac{1}{ϵ}$ 次.

$\square$

请将上述结论与 Szemerédi 正则性引理原始证明中的能量递增进行类比. 我们现在介绍由陶哲轩提出的正则分解的思想. 选择上面引理中的 $J$, 我们可以将 $A_G$ 分解为$$A_G=A_{\mathrm{str}}+A_{\mathrm{sml}}+A_{\mathrm{psr}}$$其中 “str” 代表 “structured”, “sml” 代表 “small”, “psr” 代表 “pseudorandom”. 他们各自的定义如下: $$\begin{array}{rl}{A}_{\mathrm{str}}& =\sum _{i<\mathrm{J}}{\lambda }_i{u}_i{u}_i^T\\ A_{\mathrm{sml}}& =\sum _{J\le i<F(J)}{\lambda }_i{u}_i{u}_i^T\\ A_{\mathrm{psr}}& =\sum _{i\ge F(J)}{\lambda }_i{u}_i{u}_i^T\end{array}$$其中, $A_{\text{str }}$ 大致对应有界的划分, $A_{\text{sml }}$ 大致对应非正则对, $A_{\mathrm{psr}}$ 大致对应对之间的伪随机性.

现在我们定义两个矩阵范数的概念. 矩阵 $A$ 的谱半径 (也称作谱范数) 定义为特征值绝对值中的最大值 $\max \left|{\lambda }_i(A)\right|$ . 另外, 算子范数定义为$$\Vert A\Vert =\underset{v\ne 0}{\max }\frac{|Av|}{|v|}=\underset{u,v\ne 0}{\max }\frac{\left|u^{T}Av\right|}{|u||v|}$$

注意到, 对于实对称矩阵, 谱半径和算子范数是相等的.

注意到 $A_{\mathrm{str}}$ 有特征向量 $u_1,\dots ,u_{J-1}$. 这些是 $A_G$ 的大特征值的特征向量. 我们假设 $u_i\in \{-1,1{\}}^n$ , $i=1,\dots ,J-1$. 尽管这一假设是错误的, 但为了说明起见, 让我们假设情况确实如此. 通过取这些坐标值, 我们看到 $u_1,\dots ,u_{J-1}$ 的水平集 ¹将 $V(G)$ 划分为 $P$ 个部分 $V_1,\dots ,V_P$ ($P=O_{ϵ,J}(1)$) , 使得每个 $A_{\text{str }}$ 在由该划分定义的矩阵的块上大致恒定. ($P$ 依赖 $ϵ$ 是因为坐标值的四舍五入; 实际操作中, 我们让特征向量有微小的抖动. ) 然后, 对于两个顶点子集 $U\subset V_k$ 和 $W\subset V_l$, 我们有: $$\begin{array}{rl}\left|1_U^T{A}_{\mathrm{psr}}{1}_{\mathrm{W}}\right|& \le \left|1_U\right|\left|1_W\right|\Vert A_{\mathrm{psr}}\Vert \\ & \le \sqrt{n}\cdot \sqrt{n}\cdot \frac{n}{\sqrt{F(J)}}\end{array}$$

通过选择比 $P$ 大的多的 $F(J)$, 我们可以保证上述值较小. 实际上, 我们可以证明它远小于 $ϵ{\left(\frac{n}{P}\right)}^2$. $1_U^T{A}_{\mathrm{psr}}{1}_W$ 的意义在于它等于 $e(U,W)-d_{kl}|U||W|$ , 其中 $d_{kl}$ 是 $A_{\mathrm{str}}$ 中 $V_k\times V_l$ 块中边数的平均值. 因此, 这个数量很小意味着正则性的成立.

我们还可以得到 $A_{\mathrm{sml}}$ 项的平方和 (称为 Frobenius 范数) 的上界. 对于实对称矩阵, 它等于 Hilbert-Schmidt 范数 (特征值的平方和) : $$\begin{array}{rl}{\Vert A_{\mathrm{sml}}\Vert }_{\mathrm{F}}& ={\Vert A_{\mathrm{sml}}\Vert }_{\mathrm{HS}}\\ & =\sum _{J\le i\le F(J)}{\lambda }_i^2\\ & \le ϵn^2\end{array}$$因此, $A_{\mathrm{sml}}$ 最多可能破坏 $ϵn^2$ 个对的 $ϵ$ -正则性. 所以划分仍然是正则的.

最后要说明的是, 有一些方法可以通过这种方式来得到 Szemerédi 正则性引理的其他修改版本, 例如使划分均衡. 我们不会在这里讨论相关内容.