Spectral graph theory

Cheeger inequality

The famous Cheeger's inequality from Riemannian geometry has a discrete analogue involving the Laplacian matrix; this is perhaps the most important theorem in spectral graph theory and one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian.

Cheeger constant

The Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling, and low-dimensional topology (in particular, the study of hyperbolic 3-manifolds).

More formally, the Cheeger constant h(G) of a graph G on n vertices is defined as

${\displaystyle h(G)=\underset{0<|S|\le \frac{n}{2}}{min}\frac{|\mathrm{\partial }(S)|}{|S|},}$

where the minimum is over all nonempty sets S of at most n/2 vertices and ∂(S) is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.

Cheeger inequality

When the graph G is d-regular, there is a relationship between h(G) and the spectral gap d − λ₂ of G. An inequality due to Dodziuk and independently Alon and Milman states that

${\displaystyle \frac{1}{2}(d-{\lambda }_2)\le h(G)\le \sqrt{2d(d-{\lambda }_2)}.}$

This inequality is closely related to the Cheeger bound for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry.

For general connected graphs that are not necessarily regular, an alternative inequality is given by Chung

${\displaystyle \frac{1}{2}\lambda \le \mathbf{h}(G)\le \sqrt{2\lambda },}$

where ${\displaystyle \lambda }$ is the least nontrivial eigenvalue of the normalized Laplacian, and ${\displaystyle \mathbf{h}(G)}$ is the (normalized) Cheeger constant

${\displaystyle \mathbf{h}(G)=\underset{\mathrm{\varnothing }\ne S\subset V(G)}{min}\frac{|\mathrm{\partial }(S)|}{min(\mathrm{v}\mathrm{o}\mathrm{l}(S),\mathrm{v}\mathrm{o}\mathrm{l}(\overline{S}))}}$

where ${\displaystyle \mathrm{v}\mathrm{o}\mathrm{l}(Y)}$ is the sum of degrees of vertices in ${\displaystyle Y}$.

Hoffman–Delsarte inequality

There is an eigenvalue bound for independent sets in regular graphs, originally due to Alan J. Hoffman and Philippe Delsarte.

Suppose that ${\displaystyle G}$ is a ${\displaystyle k}$-regular graph on ${\displaystyle n}$ vertices with least eigenvalue ${\displaystyle {\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}}$. Then:$${\displaystyle \alpha (G)\le \frac{n}{1-\frac{k}{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}}}}$$where ${\displaystyle \alpha (G)}$ denotes its independence number.

This bound has been applied to establish e.g. algebraic proofs of the Erdős–Ko–Rado theorem and its analogue for intersecting families of subspaces over finite fields.

For general graphs which are not necessarily regular, a similar upper bound for the independence number can be derived by using the maximum eigenvalue ${\displaystyle {\lambda }_{max}^{\prime }}$ of the normalized Laplacian of ${\displaystyle G}$: $${\displaystyle \alpha (G)\le n(1-\frac{1}{{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\prime }})\frac{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{d}\mathrm{e}\mathrm{g}}{\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{g}}}$$ where ${\displaystyle \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{d}\mathrm{e}\mathrm{g}}$ and ${\displaystyle \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{g}}$ denote the maximum and minimum degree in ${\displaystyle G}$, respectively. This a consequence of a more general inequality (pp. 109 in ): $${\displaystyle \mathrm{v}\mathrm{o}\mathrm{l}(X)\le (1-\frac{1}{{\lambda }_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\prime }})\mathrm{v}\mathrm{o}\mathrm{l}(V(G))}$$ where ${\displaystyle X}$ is an independent set of vertices and ${\displaystyle \mathrm{v}\mathrm{o}\mathrm{l}(Y)}$ denotes the sum of degrees of vertices in ${\displaystyle Y}$ .

Historical outline

Spectral graph theory emerged in the 1950s and 1960s. Besides graph theoretic research on the relationship between structural and spectral properties of graphs, another major source was research in quantum chemistry, but the connections between these two lines of work were not discovered until much later. The 1980 monograph Spectra of Graphs by Cvetković, Doob, and Sachs summarised nearly all research to date in the area. In 1988 it was updated by the survey Recent Results in the Theory of Graph Spectra. The 3rd edition of Spectra of Graphs (1995) contains a summary of the further recent contributions to the subject.

The field of discrete geometric analysis, created and developed by Toshikazu Sunada in the 2000s, deals with spectral graph theory in terms of discrete Laplacians associated with weighted graphs. It finds application in various other fields, including shape analysis.

A more recent development in spectral graph theory is vertex-frequency analysis, a set of techniques for solving problems in many real-life applications such as signal processing.