Math 2.0

Proposition

Expander mixing lemma

Statement

The expander mixing lemma intuitively states that the edges of certain dd-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets SS and TT is always close to the expected number of edges between them in a random dd-regular graph, namely dn∣S∣∣T∣\frac dn|S||T|.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first. The path takes the proof Proof of Expander mixing lemma.

Show the path as a graph
Proof of Expander mixing lemma, proof, no evidence levelProof of Expander mix…proofExpander mixing lemma, statement, no evidence levelExpander mixing lemmastatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Proof of Expander mixing lemma proof
  2. Expander mixing lemma statement

Further reading

  1. Wikipedia, page 6230931, revision 1354782268, Expander mixing lemma. adopted
About this page
Tag7235FH8REJ
URIm2://7235FH8REJ
Kindstatement, proposition
WritingW0 stub
StatusThis copy of the site has no build data. Run m2 status 7235FH8REJ.
Same as
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • edge uses out: each definition that the statement needs (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Proofs