Opening Spectral Graph Theory: The Quadratic Form
Spectral Graph Theory: The Quadratic Form
- Length
- 22 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Spectral graph theory starts from a single quadratic form attached to every undirected graph. O'Donnell sets up finite undirected graphs, allowing parallel edges and self-loops but no isolated vertices. He treats vertex labelings as real functions forming an -dimensional vector space, then defines the quadratic form as the expected value of over a uniformly random edge . He shows that scaling by multiplies the form by , while adding a constant leaves it unchanged. Evaluated on the 0-1 indicator of a vertex subset, the form measures that subset's edge boundary, linking it to graph cuts. The material assumes basic linear algebra, expectations and graph vocabulary, and Spielman's Spectral and Algebraic Graph Theory serves as the reference.

Your comment is kept while you sign up.Sign in
Defines a graph's quadratic form as an expected squared difference over a random edge, then reads off cuts.
Spectral graph theory starts from a single quadratic form attached to every undirected graph. O'Donnell sets up finite undirected graphs, allowing parallel edges and self-loops but no isolated vertices. He treats vertex labelings as real functions forming an -dimensional vector space, then defines the quadratic form as the expected value of (f(u)-f(v))² over a uniformly random edge . He shows that scaling by multiplies the form by , while adding a constant leaves it unchanged. Evaluated on the 0-1 indicator of a vertex subset, the form measures that subset's edge boundary, linking it to graph cuts. The material assumes basic linear algebra, expectations and graph vocabulary, and Spielman's Spectral and Algebraic Graph Theory serves as the reference.
Spectral and Algebraic Graph Theory
This lecture
Lecture 39 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.