Cheeger constant

Summary

The Cheeger constant of a finite graph measures its worst bottleneck. It is the least ratio of the number of edges leaving a set of vertices to the size of the set. The minimum runs over the sets with at most half of the vertices. It is zero exactly for disconnected graphs, and it is large when every set of vertices has many edges to its complement. It is also called the edge expansion or isoperimetric number, and bounded-degree graphs with Cheeger constant bounded below are expander graphs. The Cheeger inequalities compare it with the second smallest eigenvalue of the Laplacian matrix.