随机算法 (Fall 2011)/Expander Mixing Lemma

Given a [math]\displaystyle{ d }[/math]-regular graph [math]\displaystyle{ G }[/math] on [math]\displaystyle{ n }[/math] vertices with the spectrum [math]\displaystyle{ d=\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n }[/math], we denote [math]\displaystyle{ \lambda_\max = \max(|\lambda_2|,|\lambda_n|)\, }[/math], which is the largest absolute value of an eigenvalue other than [math]\displaystyle{ \lambda_1=d }[/math]. Sometimes, the value of [math]\displaystyle{ (d-\lambda_\max) }[/math] is also referred as the spectral gap, because it is the gap between the largest and the second largest absolute values of eigenvalues.

The next lemma is the so-called expander mixing lemma, which states a fundamental fact about expander graphs.

Lemma (expander mixing lemma)

Let [math]\displaystyle{ G }[/math] be a [math]\displaystyle{ d }[/math]-regular graph with [math]\displaystyle{ n }[/math] vertices. Then for all [math]\displaystyle{ S, T \subseteq V }[/math], [math]\displaystyle{ \left||E(S,T)|-\frac{d|S||T|}{n}\right|\le\lambda_\max\sqrt{|S||T|} }[/math]

The left-hand side measures the deviation between two quantities: one is [math]\displaystyle{ |E(S,T)| }[/math], the number of edges between the two sets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math]; the other is the expected number of edges between [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] in a random graph of edge density [math]\displaystyle{ d/n }[/math], namely [math]\displaystyle{ d|S||T|/n }[/math]. A small [math]\displaystyle{ \lambda_\max }[/math] (or large spectral gap) implies that this deviation (or discrepancy as it is sometimes called) is small, so the graph looks random everywhere although it is deterministic.

Proof. Assume that [math]\displaystyle{ A }[/math] is the adjacency matrix of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ v_1,v_2,\ldots,v_n }[/math] are the orthogonal eigen basis corresponding to [math]\displaystyle{ \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n }[/math]. Let [math]\displaystyle{ \chi_S }[/math] and [math]\displaystyle{ \chi_T }[/math] be characteristic vectors of vertex sets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math], i.e. [math]\displaystyle{ \chi_S(i)=\begin{cases} 1 & \text{if }i\in S,\\ 0 & \text{otherwise.} \end{cases} }[/math] Then it is easy to verify that [math]\displaystyle{ |E(S,T)|=\sum_{i\in S}\sum_{j\in T}A(i,j)=\sum_{i,j}\chi_S(i)A(i,j)\chi_T(j)=\chi^T_SA\chi_T }[/math]. Expand [math]\displaystyle{ \chi_S }[/math] and [math]\displaystyle{ \chi_T }[/math] in orthogonal basis of eigen vectors [math]\displaystyle{ v_1,v_2,\ldots,v_n }[/math] as [math]\displaystyle{ \chi_S=\sum_{i=1}^n\alpha_iv_i }[/math] and [math]\displaystyle{ \chi_T=\sum_{i=1}^n\beta_iv_i }[/math]. [math]\displaystyle{ |E(S,T)|=\chi^T_SA\chi_T=\left(\sum_{i=1}^n\alpha_iv_i\right)A\left(\sum_{i=1}^n\beta_iv_i\right)=\left(\sum_{i=1}^n\alpha_iv_i\right)\left(\sum_{i=1}^n\lambda_i\beta_iv_i\right)=\sum_{i=1}^n\lambda_i\alpha_i\beta_i, }[/math] where the last equation is due to the orthogonality of [math]\displaystyle{ v_1,\ldots,v_n }[/math]. Recall that [math]\displaystyle{ \lambda_1=d }[/math] and [math]\displaystyle{ v_1=\frac{\boldsymbol{1}}{\sqrt{n}}=\left(1/\sqrt{n},\ldots,1/\sqrt{n}\right) }[/math]. We can conclude that [math]\displaystyle{ \alpha_1=\langle\chi_S,\frac{\boldsymbol{1}}{\sqrt{n}}\rangle=\frac{|S|}{\sqrt{n}} }[/math] and [math]\displaystyle{ \beta_1=\langle\chi_T,\frac{\boldsymbol{1}}{\sqrt{n}}\rangle=\frac{|T|}{\sqrt{n}} }[/math], where [math]\displaystyle{ \langle\cdot,\cdot\rangle }[/math] stands for the inner-product. Therefore, [math]\displaystyle{ |E(S,T)|=\sum_{i=1}^n\lambda_i\alpha_i\beta_i=d\frac{|S||T|}{n}+\sum_{i=2}^n\lambda_i\alpha_i\beta_i. }[/math] By the definition of [math]\displaystyle{ \lambda_\max }[/math], [math]\displaystyle{ \left||E(S,T)|-d\frac{|S||T|}{n}\right|=\left|\sum_{i=2}^n\lambda_i\alpha_i\beta_i\right|\le\sum_{i=2}^n\left|\lambda_i\alpha_i\beta_i\right|\le\lambda_\max\sum_{i=2}^n\left|\alpha_i||\beta_i\right|. }[/math] Due to Cauchy-Schwartz inequality, [math]\displaystyle{ |\alpha_1||\beta_1|+|\alpha_2||\beta_2|+\cdots+|\alpha_n||\beta_n|\le\sqrt{\alpha_1^2+\alpha_2^2+\cdots+\alpha_n^2}\sqrt{\beta_1^2+\beta_2^2+\cdots+\beta_n^2}. }[/math] We can treat [math]\displaystyle{ \alpha }[/math] and [math]\displaystyle{ \beta }[/math] as two vectors, and conclude that [math]\displaystyle{ \left||E(S,T)|-d\frac{|S||T|}{n}\right|\le\lambda_\max\|\alpha\|_2\|\beta\|_2=\lambda_\max\|\chi_S\|_2\|\chi_T\|_2=\lambda_\max\sqrt{|S||T|}. }[/math] [math]\displaystyle{ \square }[/math]