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 = (V, E) be a d-regular graph with (un-)normalized second-largest eigenvalue lambda. Then for any two subsets S, T subseteq V, let E(S, T) denote the number of edges between S and T. We have

:|E(S, T) - frac{d |S| cdot |T{n}| 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(S, T) - frac{d |S| cdot |T{n}| leq alpha sqrt

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

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.