Expander mixing lemma
Let be a d-regular graph with (un-)normalized second-largest eigenvalue . Then for any two subsets , let denote the number of edges between S and T. We have
For a proof, see link in references.
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 ,
then its second-largest eigenvalue is .
*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