Opening Cheeger's Inequality
Cheeger's Inequality
- Length
- 1 h 2 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 6: Recap of Cheeger's inequality
Cheeger's inequality bounds the minimum conductance of a graph by a constant times , the second-smallest eigenvalue of the Laplacian. O'Donnell proves this direction in Lecture 15d of CMU 15-750, A Theorist's Toolkit, a graduate course in theoretical computer science at Carnegie Mellon. He first reduces to a convenient function, non-negative and supported on at most half the vertices. A coarea formula for graphs then links boundary crossings of superlevel sets to absolute differences across edges. Applied to the squared function and combined with Cauchy–Schwarz, it yields the bound, credited to Alon for graphs and to Cheeger for manifolds.
Your comment is kept while you sign up.Sign in
O'Donnell proves the hard direction of Cheeger's inequality by rounding via level sets and a graph coarea formula.
Cheeger's inequality bounds the minimum conductance of a graph by a constant times , the second-smallest eigenvalue of the Laplacian. O'Donnell proves this direction in Lecture 15d of CMU 15-750, A Theorist's Toolkit, a graduate course in theoretical computer science at Carnegie Mellon. He first reduces to a convenient function, non-negative and supported on at most half the vertices. A coarea formula for graphs then links boundary crossings of superlevel sets to absolute differences across edges. Applied to the squared function and combined with Cauchy–Schwarz, it yields the bound, credited to Alon for graphs and to Cheeger for manifolds.
This lecture
Lecture 48 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.