Spectral Graph Theory
Spectral Graph Theory
Spectral graph theory studies graphs through the eigenvalues of their associated matrices (adjacency matrix $A$, Laplacian $L=D-A$, normalized Laplacian). Eigenvalues encode deep structural properties: the number of connected components (zero eigenvalues of $L$), expansion (Cheeger's inequality), random walk mixing times, and graph isomorphism invariants. The Fiedler value $\lambda_2(L)$ is the algebraic connectivity — a measure of how hard it is to cut the graph.
Adjacency & Laplacian Spectra
The adjacency matrix $A\in\{0,1\}^{n\times n}$: $A_{ij}=1$ iff $(i,j)\in E$. Degree matrix $D=\text{diag}(d_1,\ldots,d_n)$. Laplacian $L=D-A$: symmetric, positive semi-definite; $\mathbf{1}^\top L=0$ so 0 is always an eigenvalue ($L\mathbf{1}=0$). Multiplicity of eigenvalue 0 = number of connected components. For $k$-regular $G$: $\lambda_i(A)=k-\lambda_{n-i}(L)$; $\lambda_1(A)=k$. $\text{tr}(A^k)=\sum_{ij}(A^k)_{ii}=$ number of closed walks of length $k$.
Cheeger's Inequality
The edge expansion (Cheeger constant) $h(G)=\min_{S:|S|\leq n/2}\frac{e(S,\bar{S})}{|S|}$ measures the worst-case cut ratio. Cheeger's inequality relates $h$ to the Fiedler value $\lambda_2$ of the normalized Laplacian $\mathcal{L}=D^{-1/2}LD^{-1/2}$: $$\frac{\lambda_2}{2}\leq h(G)\leq\sqrt{2\lambda_2}.$$ Upper bound: constructive cut from the Fiedler vector. Lower bound: expander graphs have $\lambda_2\geq\Omega(1)$ (e.g., random regular graphs); expanders have logarithmic diameter and fast random walk mixing.
Example 1
Compute the spectrum of $C_4$ (cycle on 4 vertices).
Solution: $A$ of $C_4$ with vertices $1,2,3,4$ in cycle: $A=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}$. Eigenvalues of $C_n$: $\lambda_k=2\cos(2\pi k/n)$ for $k=0,\ldots,n-1$. For $C_4$: $\lambda_0=2$, $\lambda_1=0$, $\lambda_2=-2$, $\lambda_3=0$. Spectrum $\{-2,0,0,2\}$. Laplacian eigenvalues: $\lambda_k(L)=2-2\cos(2\pi k/4)$: $\{0,2,4,2\}$. Fiedler value $\lambda_2=2$.
Example 2
Use $\text{tr}(A^3)$ to count triangles in $K_4$.
Solution: $\text{tr}(A^3)=6\cdot$(number of triangles) (each triangle contributes 6 closed walks of length 3). For $K_4$: $A$ is all-ones minus identity, eigenvalues $\{3,-1,-1,-1\}$ (from $K_n$ with $\lambda_1=n-1$, other $=−1$). $\text{tr}(A^3)=3^3+(-1)^3+(-1)^3+(-1)^3=27-3=24$. Triangles: $24/6=4=\binom{4}{3}$. ✓
Practice
- Prove the Perron-Frobenius theorem for non-negative matrices and apply it to show $\lambda_1(A)\leq\Delta$.
- Show that bipartite graphs have symmetric spectra (if $\lambda$ is an eigenvalue, so is $-\lambda$).
- Describe the random walk on a $k$-regular graph and show the mixing time is $O(k/(k-\lambda_2)\cdot\log n)$.
- Prove the interlacing theorem: for a graph $G$ and a subgraph induced by removing one vertex, eigenvalues interlace.
Show Answer Key
1. Perron-Frobenius: for a connected graph with adjacency matrix $A\ge0$, the largest eigenvalue $\lambda_1$ is simple, has a positive eigenvector, and $\lambda_1\le\max_i\sum_j A_{ij}=\Delta$ (max degree).
2. If $G$ is bipartite with parts $X,Y$: the matrix $J=\begin{pmatrix}I&0\\0&-I\end{pmatrix}$ satisfies $JAJ=-A$ (edges only cross parts). So if $Av=\lambda v$, then $A(Jv)=-\lambda(Jv)$. Hence spectrum is symmetric about 0.
3. The transition matrix is $P=A/k$ ($k$-regular). Eigenvalues of $P$ are $\lambda_i/k$. The spectral gap $1-\lambda_2/k$ controls mixing: $\|p_t-\pi\|_{TV}\le\sqrt{n}(\lambda_2/k)^t$. Setting this $<\epsilon$: $t=O(\frac{k}{k-\lambda_2}\log(n/\epsilon))$.
4. Let $G$ have eigenvalues $\lambda_1\ge\cdots\ge\lambda_n$ and $G-v$ have eigenvalues $\mu_1\ge\cdots\ge\mu_{n-1}$. Interlacing: $\lambda_i\ge\mu_i\ge\lambda_{i+1}$ for $i=1,\ldots,n-1$. Proof via the Courant-Fischer minimax characterization of eigenvalues.