随机算法 (Fall 2011)/Expander Mixing Lemma: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Created page with 'Given a <math>d</math>-regular graph <math>G</math> on <math>n</math> vertices with the spectrum <math>d=\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>, we denote <math>\lambd…'
 
imported>WikiSysop
No edit summary
 
Line 9: Line 9:


The left-hand side measures the deviation between two quantities: one is <math>|E(S,T)|</math>, the number of edges between the two sets <math>S</math> and <math>T</math>; the other is the expected number of edges between <math>S</math> and <math>T</math> in a random graph of edge density <math>d/n</math>, namely <math>d|S||T|/n</math>. A small <math>\lambda_\max</math> (or large spectral gap) implies that this deviation (or [http://en.wikipedia.org/wiki/Discrepancy_theory '''discrepancy'''] as it is sometimes called) is small, so the graph looks random everywhere although it is deterministic.
The left-hand side measures the deviation between two quantities: one is <math>|E(S,T)|</math>, the number of edges between the two sets <math>S</math> and <math>T</math>; the other is the expected number of edges between <math>S</math> and <math>T</math> in a random graph of edge density <math>d/n</math>, namely <math>d|S||T|/n</math>. A small <math>\lambda_\max</math> (or large spectral gap) implies that this deviation (or [http://en.wikipedia.org/wiki/Discrepancy_theory '''discrepancy'''] as it is sometimes called) is small, so the graph looks random everywhere although it is deterministic.
{{Proof|
Assume that <math>A</math> is the adjacency matrix of <math>G</math> and <math>v_1,v_2,\ldots,v_n</math> are the orthogonal eigen basis corresponding to <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>.
Let <math>\chi_S</math> and <math>\chi_T</math> be characteristic vectors of vertex sets <math>S</math> and <math>T</math>, i.e.
:<math>
\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>|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>\chi_S</math> and <math>\chi_T</math> in orthogonal basis of eigen vectors <math>v_1,v_2,\ldots,v_n</math> as <math>\chi_S=\sum_{i=1}^n\alpha_iv_i</math> and <math>\chi_T=\sum_{i=1}^n\beta_iv_i</math>.
:<math>
|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>v_1,\ldots,v_n</math>.
Recall that <math>\lambda_1=d</math> and <math>v_1=\frac{\boldsymbol{1}}{\sqrt{n}}=\left(1/\sqrt{n},\ldots,1/\sqrt{n}\right)</math>. We can conclude that <math>\alpha_1=\langle\chi_S,\frac{\boldsymbol{1}}{\sqrt{n}}\rangle=\frac{|S|}{\sqrt{n}}</math> and <math>\beta_1=\langle\chi_T,\frac{\boldsymbol{1}}{\sqrt{n}}\rangle=\frac{|T|}{\sqrt{n}}</math>, where <math>\langle\cdot,\cdot\rangle</math> stands for the inner-product. Therefore,
:<math>
|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>\lambda_\max</math>,
:<math>
\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>
|\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>\alpha</math> and <math>\beta</math> as two vectors, and conclude that
:<math>
\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>
}}

Latest revision as of 02:22, 25 July 2011

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]