• Overview
• Details
• Exercises

Spectral graph theory studies how eigenvalues and eigenvectors of matrices associated with a graph—especially the Laplacian—reveal combinatorial structure. The second-smallest Laplacian eigenvalue (algebraic connectivity) connects to expansion and conductance, with Cheeger-type inequalities linking spectrum to cuts and clustering.

• Graph Laplacians: unnormalized L = D − A; normalized L_norm = I − D^{-1/2} A D^{-1/2}. Properties: symmetric PSD, eigenvalues 0 = λ₁ ≤ λ₂ ≤ ...
• Algebraic connectivity: λ₂(L) > 0 iff the graph is connected. Fiedler vector provides an ordering for partitioning.
• Rayleigh quotient: x^T L x / x^T x equals sum of squared edge differences; eigenvalues minimize Rayleigh subject to orthogonality.
• Cheeger inequality (normalized version): for conductance Φ(G), (λ₂/2) ≤ Φ(G) ≤ √{2λ₂}. Implications for spectral partitioning.
• Random walks and mixing: transition P = D^{-1}A, relation to normalized Laplacian spectrum; spectral gap controls convergence rate.
• Applications: graph clustering, image segmentation, semi-supervised learning, sparsest cut approximations (overview).

1. Show that for any vector x, x^T L x = \sum_{(u,v)\in E} (x_u - x_v)^2. Interpret this as a smoothness measure on the graph.
2. For a d-regular graph, prove that eigenvalues of L and of I − (1/d)A differ by a scalar shift, and relate λ₂ to expansion.
3. Implement a simple spectral bisection: compute the Fiedler vector and sweep cut; discuss how the sweep achieves the Cheeger upper bound.