# Spectral and Combinatorial Theory of the Graph Laplacian


<!--more-->

**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](https://github.com/YuZh98/YuZh98.github.io/releases/download/pdfs-v1/posts__Notes-for-GraphLaplacian__graph-laplacian-notes.pdf)**


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.