Spectral Methods in Combinatorics

Spectral graph theory uses eigenvalues of matrices associated with graphs to derive combinatorial properties. The adjacency matrix, Laplacian, and normalized Laplacian encode structural information that can be extracted through linear algebra.

Adjacency and Laplacian Eigenvalues

Definition6.4Graph Spectrum

For a graph $G$ on $n$ vertices, the adjacency matrix $A(G)$ has eigenvalues $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ , called the spectrum of $G$ . The Laplacian $L(G) = D(G) - A(G)$ , where $D(G)$ is the diagonal degree matrix, has eigenvalues $0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$ .

Definition6.5Expander Mixing Lemma

For a $d$ -regular graph $G$ with second eigenvalue $\lambda = \lambda_2(A)$ and vertex sets $S, T \subseteq V(G)$ : $\left| e(S, T) - \frac{d|S||T|}{n} \right| \leq \lambda \sqrt{|S||T|},$ where $e(S, T)$ counts edges between $S$ and $T$ . Small $\lambda$ implies that the edge distribution is close to that of a random graph.

ExamplePaley Graph Spectrum

The Paley graph on $\mathbb{F}_p$ (where $p \equiv 1 \pmod{4}$ ) has vertices $\mathbb{F}_p$ and edges $\{a, b\}$ when $a - b$ is a quadratic residue. It is $(p-1)/2$ -regular with second eigenvalue $\lambda_2 = \frac{1 + \sqrt{p}}{2}$ . The expander mixing lemma then guarantees that this graph is a strong expander.

Hoffman's Bound

Definition6.6Hoffman Bound for Independence

For a $d$ -regular graph $G$ on $n$ vertices with smallest eigenvalue $\lambda_n$ , the independence number satisfies: $\alpha(G) \leq \frac{n \cdot (-\lambda_n)}{d - \lambda_n}.$

ExampleKneser Graph Eigenvalues

The Kneser graph $K(n, k)$ has vertices $\binom{[n]}{k}$ and edges between disjoint sets. It is regular with degree $\binom{n-k}{k}$ and eigenvalues $(-1)^j \binom{n-k-j}{k-j}$ for $j = 0, 1, \ldots, k$ . Hoffman's bound applied to $K(n,k)$ gives $\alpha(K(n,k)) \leq \binom{n-1}{k-1}$ , matching the Erdos-Ko-Rado bound.

RemarkSpectral Gap and Expansion

The spectral gap $d - \lambda_2$ of a $d$ -regular graph controls its expansion properties. The Alon-Boppana bound states that $\lambda_2 \geq 2\sqrt{d-1} - o(1)$ for any family of $d$ -regular graphs with $n \to \infty$ . Graphs achieving $\lambda_2 \leq 2\sqrt{d-1}$ are called Ramanujan graphs and have optimal expansion properties.

Applications to Chromatic Number

Definition6.7Hoffman Chromatic Bound

For a graph $G$ with largest eigenvalue $\lambda_1$ and smallest eigenvalue $\lambda_n$ : $\chi(G) \geq 1 - \frac{\lambda_1}{\lambda_n}.$ This spectral lower bound for the chromatic number is tight for Kneser graphs and many other structured graphs.