Opening Spectral Graph Theory: Minimizing and Maximizing the Quadratic Form
Spectral Graph Theory: Minimizing and Maximizing the Quadratic Form
- Length
- 33 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Minimizing the quadratic form
Proves the graph quadratic form vanishes exactly on componentwise constant functions and peaks only on bipartite graphs.
The quadratic form of a graph, the starting point of spectral graph theory, measures how much a vertex function changes across edges. O'Donnell proves the form is zero exactly when the function is constant on each connected component. The number of linearly independent zero-form functions therefore equals the number of components. For maximization he fixes the variance or second moment, then views the function as an embedding of vertices into the real line. The form is at most twice , attained by assigning and to the sides of a bipartite graph, and equality holds only for bipartite graphs.
The quadratic form of a graph, the starting point of spectral graph theory, measures how much a vertex function changes across edges. O'Donnell proves the form is zero exactly when the function is constant on each connected component. The number of linearly independent zero-form functions therefore equals the number of components. For maximization he fixes the variance or second moment, then views the function as an embedding of vertices into the real line. The form is at most twice , attained by assigning and to the sides of a bipartite graph, and equality holds only for bipartite graphs.

This lecture
Lecture 42 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.
Your comment is kept while you sign up.Sign in