Cheeger constant (graph theory)

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.

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.

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 → ∞.

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.

[2] The Cheeger inequality is a fundamental result and motivation for spectral graph theory.