谱图论中cheeger不等式刻画了图的扩展率(expanding ratio)$\phi(G)$和图的拉普拉斯矩阵的第二小特征值$\lambda_2$之间的关系:\[\lambda_2 /2 \leq \phi(G) \leq \sqrt{2 \lambda_2}\]

由于扩展图的应用在理论计算机中及其广泛和重要，cheeger不等式对扩展率的刻画是极为重要的。更令人惊讶的是使用图的拉普拉斯矩阵的第二小特征值这一线性代数的刻画和图的扩展率这一组合特征发生了如此有趣关系，下面来讨论这个有趣的关系。

一个d-regular图中某个节点集$S\subset V$的(边)扩展率定义为$\phi(S)=\frac{|E(S,\bar{S}|}{d|S|}$,即节点集$S$中顶点与节点集$S$之外的节点即$\bar{S}$中节点的边数$|E(S,\bar{S})|$，和节点集$S$中顶点的总边数$d|S|$之比，从概率的角度看，这正是随机选取一个节点集$S$中顶点的边，那么边的‘扩展’到节点集$S$外的概率。那么一个图的扩展率$\phi(G)$定义为：$min_{|S|\leq |V|/2}\phi(S)$

下面给出图的另一个特征sparsity,同样的定义$\sigma(S)=\frac{|E(S,\bar{S}|}{d|S||V-S|/|V|}$ ,很明显有$\sigma(S)=\frac{|E(S,\bar{S}|}{d|S||V-S|/|V|}=\phi(S)\frac{|V|}{|V-S|}$,由于对于$\phi(G),|S|\leq |V|/2$,$1<\frac{|V|}{|V-S|}\leq 2$,于是\[\phi(G)\leq \sigma(G) \leq 2 \phi(G)\]

现在可以证明cheeger不等式较容易的部分即$\lambda_2 /2 \leq \phi(G)$,事实上我们通过证明$\lambda_2 \leq \sigma(G)$来证实这一点。

让我们先回到图的拉普拉斯矩阵$L=I-\frac{1}{d}A$，定义一个向量$x$的Rayleigh Quotient $R(x)=\frac{x^* L x}{x^* x}$,第二小特征值$\lambda_2$为

\[\lambda_2 = {MIN}_{x \in \mathbb{R}^n-\{\mathbf{0,1}\}}\frac{x^* L x}{x^* x} \]

由Rayleigh Quotient的性质进一步得到

\[\lambda_2 = {MIN}_{x \in \mathbb{R}^n-\{\mathbf{0}\},x\perp\mathbf{1}} \frac{\sum_{ \{u,v\}\in E}|x_u-x_v|^2}{d \sum_u x_{u}^2 }\]

而对于$\sigma(G)$我们可以将其从新表述为向量形式，即一个sparse cut为一个向量$x$,若$v_i \in S，x_i =1$,否则$x_i =0$,即向量$x$为$\{0,1\}$向量，那么

\[\sigma(S)=\frac{|E(S,\bar{S}|}{d|S||V-S|/|V|}=\frac{\sum_{\{u,v\}\in E}|x_u-x_v|}{d/n \sum_{\{u,v\}}|x_u-x_v|} = \frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}\]

则$\sigma(G)$为\[\sigma(G)={MIN}_{x \in \{0,1\}^n-\{\mathbf{0,1}\}}\frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}\]

事实上，可以证明\[\lambda_2 = {MIN}_{x \in \mathbb{R}^n-\{\mathbf{0,1}\}} \frac{\sum_{ \{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}\]

这是因为首先$x \in \mathbb{R}^n-\{\mathbf{0}\}，x\perp 1$那么：\[\sum_{(u,v)}|x_u-x_v|^2=\sum_{(u,v)}x_u^2 +\sum_{(u,v)}x_v^2-2\sum_{(u,v)}x_u x_v=2 \sum_{(u,v)}x_v^2-2(\sum_v x_v)^2=\sum_{(u,v)}x_v^2=2n\sum_v x_v^2\]

此时有$\sum_{(u,v)}|x_u-x_v|^2=2n\sum_v x_v^2$,注意到有序对$(u,v)$和无序对$\{u,v\}$之间的数量关系$\sum_{\{u,v\}}|x_u-x_v|^2=n\sum_v x_v^2$,进一步得到:\[\lambda_2 = {MIN}_{x \in \mathbb{R}^n-\{\mathbf{0}\},x\perp\mathbf{1}} \frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}\]

而对于$x \in \mathbb{R}^n-\{\mathbf{0,1}\}$满足${MIN}_{x \in \mathbb{R}^n-\{\mathbf{0，1}\}} \frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}$,也可以满足${MIN}_{x \in \mathbb{R}^n-\{\mathbf{0}\},x\perp\mathbf{1}} \frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}$,这是由于$\frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}$分子分母中的$|x_u-x_v|$，$x$的任意线性变换$ax+b$也是解，假设$x$为解，$x'$满足$x^{'}_i =x_i-(\sum_v x_v)$也是解，而$\langle x',\mathbf{1}\rangle =0$即$x' \perp \mathbf{1}$。进一步有\[\lambda_2={MIN}_{x \in \mathbb{R}^n-\{\mathbf{0}\},x\perp\mathbf{1}} \frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}={MIN}_{x \in \mathbb{R}^n-\{\mathbf{0，1}\}} \frac{\sum_{\{u,v\}\in E}|x_u-x_v|^2}{d/n \sum_{\{u,v\}}|x_u-x_v|^2}\]

可见$\lambda_2$为$\sigma(G)$的线性放松，因此有$\lambda_2 \leq \sigma(G)\leq 2\phi(G)$。

本文参考了以下资源和文献  

[1]CS359G: Graph Partitioning and Expanders http://theory.stanford.edu/~trevisan/cs359g/ http://venture-lab.org/expanders

[2]Expander graphs and their applications. Authors: Shlomo Hoory, Nathan Linial and AviWigderson Journal: Bull. Amer. Math. Soc. 43 (2006), 439-561