Opening Expander Graphs Overview
Expander Graphs Overview
- Length
- 28 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Core properties of expander graphs
Expander graphs are sparse graphs, with a linear number of edges, in which every vertex set still communicates strongly with the rest. O'Donnell formalizes sparsity through -regular graphs and connectivity through minimum conductance, the bottleneck fraction of boundary edges, alongside edge and vertex expansion. He contrasts the probabilistic-method proof that random regular graphs expand with high probability, credited to Pinsker in 1973, with explicit constructions computable in polynomial time, which deterministic algorithms need. The last part turns to bipartite expanders and their uses in error-correcting codes and derandomization. The session belongs to CMU's graduate course A Theorist's Toolkit and assumes basic spectral graph theory, asymptotic notation and familiarity with randomized methods.

Your comment is kept while you sign up.Sign in
Contrasts Pinsker's 1973 random-graph proof of expansion with polynomial-time explicit expanders.
Expander graphs are sparse graphs, with a linear number of edges, in which every vertex set still communicates strongly with the rest. O'Donnell formalizes sparsity through -regular graphs and connectivity through minimum conductance, the bottleneck fraction of boundary edges, alongside edge and vertex expansion. He contrasts the probabilistic-method proof that random regular graphs expand with high probability, credited to Pinsker in 1973, with explicit constructions computable in polynomial time, which deterministic algorithms need. The last part turns to bipartite expanders and their uses in error-correcting codes and derandomization. The session belongs to CMU's graduate course A Theorist's Toolkit and assumes basic spectral graph theory, asymptotic notation and familiarity with randomized methods.
Expander graphs and their applications
Pinsker's 1973 Paper
This lecture
Lecture 49 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.