• Overview
• Details
• Exercises

Expander graphs are sparse graphs that are nonetheless highly connected. Their expansion properties can be characterized spectrally via eigenvalues of the adjacency matrix or Laplacian. Expanders power derandomization, error-correcting codes, network design, and rapid mixing of random walks.

• Vertex/edge expansion and conductance. Cheeger-type bounds link conductance to the spectral gap.
• Spectral expansion: for d-regular graphs, gap d - \lambda_2(A) or equivalently \lambda_2(L) for Laplacian. Alon–Boppana lower bound.
• Random walks and mixing time: relation to second eigenvalue; applications to sampling and approximate counting (overview).
• Construction ideas: random regular graphs (w.h.p. expanders), zig-zag product (high level), Ramanujan graphs (concept).
• Applications: derandomization (extractors/PRGs at a high level), LDPC/expander codes, network design and fault tolerance.

1. For a d-regular graph, show that the lazy random walk mixes in time O\big((1/(1-\lambda)) \log(1/\pi_{min})\big), where \lambda is the second-largest eigenvalue in magnitude.
2. Relate conductance \Phi and spectral gap 1-\lambda using Cheeger inequalities, and derive a bound on mixing time from \Phi.
3. Outline how expander codes achieve linear-time encoding/decoding and distance proportional to n.