Laplacian Matrix and Expansion

The Laplacian matrix $L = D - A$ captures the diffusive properties of a graph. Its second-smallest eigenvalue -- the algebraic connectivity -- measures how well-connected the graph is and controls random walk mixing.

Laplacian Spectrum

Definition8.3Laplacian Matrix

The Laplacian $L(G) = D - A$ where $D = \mathrm{diag}(\deg(v_1), \ldots, \deg(v_n))$ . Properties: $L$ is positive semidefinite; eigenvalues $0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$ ; the multiplicity of eigenvalue 0 equals the number of connected components; the algebraic connectivity $\mu_2 = a(G)$ (Fiedler, 1973) satisfies $a(G) > 0$ iff $G$ is connected.

Definition8.4Normalized Laplacian

The normalized Laplacian is $\mathcal{L} = D^{-1/2}LD^{-1/2} = I - D^{-1/2}AD^{-1/2}$ . Its eigenvalues $0 = \tilde{\mu}_1 \leq \cdots \leq \tilde{\mu}_n \leq 2$ . The normalized Laplacian is better suited for irregular graphs. The random walk matrix $P = D^{-1}A$ has eigenvalues $1 - \tilde{\mu}_i$ , connecting Laplacian spectrum to random walk behavior.

Cheeger's Inequality and Expansion

ExampleCheeger's Inequality

The conductance (Cheeger constant) of $G$ is $h(G) = \min_{S: 0 < |S| \leq n/2} \frac{|E(S, \bar{S})|}{|S|}$ (for $d$ -regular graphs, often normalized by $d$ ). Cheeger's inequality: $\frac{\mu_2}{2} \leq h(G) \leq \sqrt{2\mu_2}$ for $d$ -regular graphs (with $h$ normalized by $d$ ). This connects the algebraic and combinatorial notions of expansion: good expansion ( $h$ large) is equivalent to a spectral gap ( $\mu_2$ bounded away from 0).

RemarkExpander Graphs

An infinite family of $d$ -regular graphs $\{G_n\}$ with $|V(G_n)| \to \infty$ is an expander family if $\mu_2(G_n) \geq c > 0$ uniformly. Expanders exist for all $d \geq 3$ (probabilistic proof; explicit constructions by Margulis, Lubotzky-Phillips-Sarnak). The Alon-Boppana bound: $\lambda_2(G) \geq 2\sqrt{d-1} - o(1)$ for $d$ -regular graphs, so $\mu_2 \leq d - 2\sqrt{d-1} + o(1)$ . Ramanujan graphs achieve $\lambda_2 \leq 2\sqrt{d-1}$ , optimal expansion.

Applications

Definition8.5Random Walks and Mixing Time

A random walk on $G$ transitions from vertex $u$ to a random neighbor. For a connected non-bipartite $d$ -regular graph, the walk converges to the uniform distribution. The mixing time $t_{\text{mix}} = O(\log n / (1 - \lambda))$ where $\lambda = \max(|\lambda_2|, |\lambda_n|)/d$ . The spectral gap $1 - \lambda$ controls how fast mixing occurs. Expander graphs have $t_{\text{mix}} = O(\log n)$ , the fastest possible.