Spectral and Combinatorial Theory of the Graph Laplacian

Before downloading, note that the notes are put together using LLMs, and I am still in the early process of checking and polishing the content. I will update the notes as I go, and I welcome any feedback or suggestions.

Download link: Graph Laplacian Notes

These notes were developed as a careful, self-contained tour of the spectral and combinatorial theory of the graph Laplacian $L = D - W$. The nine chapters proceed roughly from the foundational to the modern, followed by six appendices.

1. The graph Laplacian: the incidence factorization $L = B W_e B^\top$, positive semidefiniteness, the kernel and connected components, Courant–Fischer, the Fiedler vector.
2. The matrix-tree theorem and effective resistance: Kirchhoff’s theorem via Cauchy–Binet, the eigenvalue-product formulation, the all-minors generalization, effective resistance, Foster’s identity.
3. Directed graphs and the BEST theorem: Tutte’s directed matrix-tree theorem, Eulerian circuits, DAG spectra, the Markov-chain tree theorem.
4. Signed and magnetic Laplacians: the balance theorem (Cartwright–Harary, Hou), switching equivalence, the magnetic Laplacian and gauge invariance, ranking applications.
5. The Cheeger inequality, expanders, and mixing: the discrete Cheeger inequality, the expander mixing lemma, and the connection between $\lambda_2$ and random-walk mixing time.
6. Random spanning trees: the weighted uniform spanning tree measure, edge inclusion via effective resistance, the transfer current theorem, the Aldous–Broder and Wilson sampling algorithms, and the fast-forwarded acceleration of Aldous–Broder.
7. Hypergraph Laplacians: clique expansion, star expansion, Zhou’s normalized Laplacian, the Chan–Louis–Tang–Zhang nonlinear Laplacian, with explicit attention to information loss and competing conventions.
8. Laplacians of random graphs: the spectrum of $\mathbb{E}[L]$ for Erdős–Rényi and SBM, Oliveira’s concentration theorem, Le–Levina–Vershynin regularization, semicircle laws, phase transitions.
9. Laplacian solvers and spectral sparsification: spectral approximation order, Spielman–Srivastava sparsification by effective resistance, nearly-linear-time Laplacian solvers.