Expander Graphs — Fundamentals

Corresponds to advanced course, Lectures 9 (partial) – 11. An expander is a sparse graph (few edges per vertex) that nonetheless mixes and connects like a dense random graph — the central object of the pseudo- randomness part of this course. Covers the several (combinatorial, vertex-, edge-, and spectral-) notions of expansion, which coincide up to polynomial factors, and Ramanujan graphs as the spectrally optimal case. The Expander Mixing Lemma formalizes “edges between any two vertex subsets behave as if the graph were random,” and fast mixing of random walks is the complementary statement that a short random walk on an expander lands almost uniformly — both consequences of a spectral gap between the largest and second-largest eigenvalues, analyzed via the adjacency matrix’s quadratic form, the Courant-Fischer min-max characterization of eigenvalues (extending the spectral theorem), and Cheeger’s inequality relating that spectral gap to the graph’s combinatorial bottleneck. Closes with a first explicit construction: a randomized Cayley graph over $\mathbb Z_2^n$, shown to be a good spectral expander via the Chernoff bound — a warm-up for the fully explicit constructions later in the course.

Outline (TODO — flesh out each)

• Expander graphs — notions of expansion, Ramanujan graphs
• The Expander Mixing Lemma
• Fast mixing of random walks on expanders
• Cayley graphs over abelian groups
• A randomized construction of spectral expanders over $\mathbb Z_2^n$
• The adjacency matrix, its quadratic form, and the spectral theorem
• Courant-Fischer variational characterization of eigenvalues
• Cheeger’s inequality (and higher-order versions)