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

From EtoneWiki
Jump to: navigation, search

Given a -regular graph on vertices with the spectrum , we denote , which is the largest absolute value of an eigenvalue other than . Sometimes, the value of 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 be a -regular graph with vertices. Then for all ,

The left-hand side measures the deviation between two quantities: one is , the number of edges between the two sets and ; the other is the expected number of edges between and in a random graph of edge density , namely . A small (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 is the adjacency matrix of and are the orthogonal eigen basis corresponding to .

Let and be characteristic vectors of vertex sets and , i.e.

Then it is easy to verify that

.

Expand and in orthogonal basis of eigen vectors as and .

where the last equation is due to the orthogonality of .

Recall that and . We can conclude that and , where stands for the inner-product. Therefore,

By the definition of ,

Due to Cauchy-Schwartz inequality,

We can treat and as two vectors, and conclude that