﻿

Expander mixing lemma

The expander mixing lemma states that, for any two subsets $S, T$ of a regular expander graph $G$, the number of edges between $S$ and $T$ is approximately what you would expect in a random "d"-regular graph, i.e. $d |S| cdot |T| / n$.

tatement

Let $G = \left(V, E\right)$ be a d-regular graph with (un-)normalized second-largest eigenvalue $lambda$. Then for any two subsets $S, T subseteq V$, let $E\left(S, T\right)$ denote the number of edges between S and T. We have

:$|E\left(S, T\right) - frac\left\{d |S| cdot |T\left\{n\right\}| leq lambda sqrt$

For a proof, see link in references.

Converse

Recently, Bilu and Linial showed that the converse holds as well: if a graph satisfies the conclusion of the expander mixing lemma, that is, for any two subsets $S, T subseteq V$,

:$|E\left(S, T\right) - frac\left\{d |S| cdot |T\left\{n\right\}| leq alpha sqrt$

then its second-largest eigenvalue is $O\left(alpha\left(1+log\left(d/alpha\right)\right)\right)$.

References

*Notes proving the expander mixing lemma. [http://algo.epfl.ch/handouts/en/algoM_lect24.pdf]
*Expander mixing lemma converse. [http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf]

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Expander graph — In combinatorics, an expander graph is a sparse graph which has high connectivity properties, quantified using vertex or edge expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several …   Wikipedia

• List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

• List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia