Cheeger constant (graph theory)

In mathematics, 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. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold. The Cheeger constant is named after the mathematician Jeff Cheeger. Let G be an undirected finite graph with vertex set V(G) and edge set E(G). For a collection of vertices A ⊆ V(G), let ∂A denote the collection of all edges going from a vertex in A to a vertex outside of A (sometimes called the edge boundary of A): Note that the edges are unordered, i.e., . The Cheeger constant of G, denoted h(G), is defined by The Cheeger constant is strictly positive if and only if G is a connected graph. Intuitively, if the Cheeger constant is small but positive, then there exists a "bottleneck", in the sense that there are two "large" sets of vertices with "few" links (edges) between them. The Cheeger constant is "large" if any possible division of the vertex set into two subsets has "many" links between those two subsets. 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 GN. Number the computers 1, 2, ..., N clockwise around the ring. Mathematically, the vertex set and the edge set are given by: Take A to be a collection of of these computers in a connected chain: So, and This example provides an upper bound for the Cheeger constant h(GN), 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.