Cheeger constant (graph theory)

Example: computer networking

In applications to theoretical computer science, one wishes to devise network configurations for which the Cheeger constant is high (at least, bounded away from zero) even when |V(G)| (the number of computers in the network) is large.

For example, consider a ring network of N ≥ 3 computers, thought of as a graph G_N. Number the computers 1, 2, ..., N clockwise around the ring. Mathematically, the vertex set and the edge set are given by:

$${\displaystyle \begin{array}{cc}V(G_N)& =\{1,2,\cdots ,N-1,N\}\\ E(G_N)& =\{\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}\}\end{array}}$$

Take A to be a collection of ${\displaystyle \lfloor \frac{N}{2}\rfloor }$ of these computers in a connected chain:

$${\displaystyle A=\left\{1,2,\cdots ,\lfloor \frac{N}{2}\rfloor \right\}.}$$

So,

$${\displaystyle \mathrm{\partial }A=\left\{\left\{\lfloor \frac{N}{2}\rfloor ,\lfloor \frac{N}{2}\rfloor +1\right\},\{N,1\}\right\},}$$

and

$${\displaystyle \frac{|\mathrm{\partial }A|}{|A|}=\frac{2}{\lfloor \frac{N}{2}\rfloor }\to 0\text{ as }N\to \mathrm{\infty }.}$$

This example provides an upper bound for the Cheeger constant h(G_N), which also tends to zero as N → ∞. Consequently, we would regard a ring network as highly "bottlenecked" for large N, and this is highly undesirable in practical terms. We would only need one of the computers on the ring to fail, and network performance would be greatly reduced. If two non-adjacent computers were to fail, the network would split into two disconnected components.

Cheeger inequalities

The Cheeger constant is especially important in the context of expander graphs as it is a way to measure the edge expansion of a graph. The so-called Cheeger inequalities relate the eigenvalue gap of a graph with its Cheeger constant. More explicitly, for ${\displaystyle G\ne K_1,K_2,K_3}$, we have

$${\displaystyle 2h(G)\ge \lambda \ge \frac{h^2(G)}{2\mathrm{\Delta }(G)}}$$

in which ${\displaystyle \mathrm{\Delta }(G)}$ is the maximum degree for the nodes in ${\displaystyle G}$ and ${\displaystyle \lambda }$ is the spectral gap of the Laplacian matrix of the graph. The Cheeger inequality is a fundamental result and motivation for spectral graph theory.