Opening Expander Graph Constructions
Expander Graph Constructions
- Length
- 49 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Bipartite graph conversions and expansion parameters
Explicit expander graph constructions yield constant-degree graphs with strong connectivity, and O'Donnell surveys three families of them at Carnegie Mellon University. He first converts regular graphs into bipartite expanders, contrasts edge with vertex expansion, and defines spectral expansion via the normalized Laplacian. The Margulis and Gabber-Galil construction then gives strongly explicit eight-regular expanders on integer grids. Ramanujan graphs from Lubotzky, Phillips, and Sarnak achieve the optimal spectral bound that Friedman's theorem establishes for random regular graphs. The final part sketches the replacement product, a variant of the Reingold–Vadhan–Wigderson zig-zag product, and uses graph powering to restore the eigenvalue gap. Lecture 16d of CS Theory Toolkit, it assumes spectral graph theory and Cheeger's inequality.
Your comment is kept while you sign up.Sign in
Constructs explicit expanders from Gabber-Galil grids, Ramanujan graphs, and iterated replacement products.
Explicit expander graph constructions yield constant-degree graphs with strong connectivity, and O'Donnell surveys three families of them at Carnegie Mellon University. He first converts regular graphs into bipartite expanders, contrasts edge with vertex expansion, and defines spectral expansion via the normalized Laplacian. The Margulis and Gabber-Galil construction then gives strongly explicit eight-regular expanders on integer grids. Ramanujan graphs from Lubotzky, Phillips, and Sarnak achieve the optimal spectral bound that Friedman's theorem establishes for random regular graphs. The final part sketches the replacement product, a variant of the Reingold–Vadhan–Wigderson zig-zag product, and uses graph powering to restore the eigenvalue gap. Lecture 16d of CS Theory Toolkit, it assumes spectral graph theory and Cheeger's inequality.
Gabber and Galil '81
Zig-zag product paper
Replacement product paper
This lecture
Lecture 52 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.