谱扩张与 Cheeger 不等式

形式陈述 ​

设 $G=(V,E,w)$ 是有限简单无向图，边权 $w_{uv}=w_{vu}\ge 0$，至少有两个顶点，且每个顶点的加权度数严格为正。令

并记 $w(S,\overline{S})=\sum _{u\in S,v\notin S}{w}_{uv}$。非平凡割的 conductance 定义为

使用归一化 Laplacian理路图 LaplacianGraph Laplacian · Laplacian matrix用度矩阵减邻接矩阵得到的算子，以二次型衡量相邻顶点取值的不一致。

令 ${\lambda }_2$ 为它的第二小特征值理路特征值与特征向量Eigenvalue and eigenvector满足 Tv=λv 且 v 非零的标量 λ 与向量 v。。图的 Cheeger 不等式是

度数缩放与割向量 ​

记 $L=D-A$。由实对称矩阵的谱定理理路有限维谱定理Finite-dimensional spectral theorem有限维复正规算子存在正交规范特征基；实数情形对应自伴算子。，在 $D^{1/2}\mathbf{1}$ 的正交补上取 Rayleigh 商，便有

这里参与归一化矩阵 Rayleigh 商的向量是 $z=D^{1/2}f$；分部常值的是顶点函数 $f$，两者在非正则图中不能混同。

对任意非平凡割 $S$，取 $f=1/\mathrm{vol}(S)$ 于 $S$、$f=-1/\mathrm{vol}(\overline{S})$ 于补集，便满足加权均值为零。代入得到

从而证明左侧界。

从特征向量扫出一个割 ​

取非零特征向量 $z$，满足 $\mathcal{L}z={\lambda }_{2}z$ 及 $z\perp D^{1/2}\mathbf{1}$，并令 $g=D^{-1/2}z$。它满足 $Lg={\lambda }_{2}Dg$。$g$ 的正、负支撑不交，至少一侧体积不超过总体积的一半；取这一侧对应的非零函数 $f=g_{+}$ 或 $f=(-g{)}_{+}$。逐边有

（负部情形把 $g$ 换为 $-g$）。与特征方程配对后，得到

令 $S_t=\{u:f(u{)}^2>t\}$。逐条边与逐个顶点积分可得离散 coarea 恒等式

这些非空阈值集体积都不超过总量一半。对差平方的因式分解使用Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。，再用 $(a+b{)}^2\le 2a^2+2b^2$，分子至多为

所以必有一个非空阈值集满足 $\varphi (S_t)\le \sqrt{2{\lambda }_2}$，证明右侧界。有限图只需检查按顶点值排序得到的有限多个不同阈值。