Lectures on Spectral Graph Theory

Eigenvalues and the Laplacian of a graph. The Laplacian and eigenvalues. Basic facts about the spectrum of a graph. Eigenvalues of weighted graphs. Eigenvalues and random walks. Isoperimetric problems. History. The Cheeger constant of a graph. The edge expansion of a graph. The vertex expansion of a graph. A characterization of the Cheeger constant. Isoperimetric inequalities for cartesian products. Diameters and eigenvalues. The diameter of a graph. Eigenvalues and distances between two subsets. Eigenvalues and distances among many subsets. Eigenvalue upper bounds for manifolds. Paths, flows, and routing. Paths and sets of paths. Flows and Cheeger constants. Eigenvalues and routes with small congestion. Routing in graphs. Comparison theorems. Eigenvalues and quasi-randomness. Quasi-randomness. The discrepancy property. The deviation of a graph. Quasi-random graphs. Bibliography