Spectral graph theory

Summary

Spectral graph theory studies a graph through the eigenvalues and eigenvectors of matrices attached to it, mainly the adjacency matrix and the Laplacian matrix. These eigenvalues are invariants of the graph up to isomorphism, and many of them have combinatorial meaning. For example, a finite graph is bipartite if and only if the spectrum of its adjacency matrix is symmetric about $0$. Its number of connected components equals the multiplicity of the Laplacian eigenvalue $0$. The Cheeger constant is controlled by the second Laplacian eigenvalue, which links the subject to expander graphs.