Cheeger constant (graph theory)

In mathematics, the Cheeger constant (or Cheeger 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).

Definition

Let $G$ be an undirected (connected) graph with vertex set $V(G)$ and edge set $E(G)$. For a collection of vertices $A\subseteq V(G)$, let $\partial A$ denote the collection of all edges going from a vertex in $A$ to a vertex outside of $A$:

$\partial A:=\{(x,y)\in E|x\in A,y\in V(G)\setminus A\}.$

(Remember that edges are unordered, so the edge $(x,y)$ is the same as the edge $(y,x)$.) Then the Cheeger constant of $G$, denoted $h(G)$, is defined by

$h(G):=\min \left\{\left.{\frac {|\partial A|}{|A|}}\right|A\subseteq V(X),0<|A|\leq {\frac {|V(G)|}{2}}\right\}.$

Intuitively, if the Cheeger constant $h(G)$ is small, then there exists a "bottleneck", in the sense that there are two "large" sets of vertices with "few" connections (edges) between them.

Example: computer networking

Ring network layout

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\geq 3$ computers, thought of as a graph $G_{N}$. Number the computers $1,2,\dots ,N$ clockwise around the ring. Mathematically, the vertex set is

$V(G_{N}):=\{1,2,\dots ,N\}$

and the edge set is

$E(G_{N}):=\{(1,2),(2,3),\dots ,(N-1,N),(N,1)\}.$

Take $A$ to be a collection of $\lfloor N/2\rfloor$ of these computers in a connnected chain:

$A:=\{1,2,\dots ,\lfloor N/2\rfloor \}.$

Clearly, $\partial A=\{(\lfloor N/2\rfloor ,\lfloor N/2\rfloor +1),(N,1)\}$, so

${\frac {|\partial A|}{|A|}}={\frac {2}{\lfloor N/2\rfloor }}\to 0{\mbox{ as }}N\to \infty .$

This example provides an upper bound for the Cheeger constant $h(G_{N})$, which also tends to zero as $N$ tends to infinity. 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 four computers

$1,\lfloor N/2\rfloor ,\lfloor N/2\rfloor +1,N$

to fail, and network performance would be greatly degraded. If both $1$ and $\lfloor N/2\rfloor$ were to fail, the network would split into two disconnected components.