Английская Википедия:Cheeger constant (graph theory)
Шаблон:Short description Шаблон:About Шаблон:More footnotes 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.
Definition
Let Шаблон:Mvar be an undirected finite graph with vertex set Шаблон:Math and edge set Шаблон:Math. For a collection of vertices Шаблон:Math, let Шаблон:Math denote the collection of all edges going from a vertex in Шаблон:Mvar to a vertex outside of Шаблон:Mvar (sometimes called the edge boundary of Шаблон:Mvar):
- <math>\partial A := \{ \{x, y\} \in E(G) \ : \ x \in A, y \in V(G) \setminus A \}.</math>
Note that the edges are unordered, i.e., <math>\{x, y\} = \{y, x\}</math>. The Cheeger constant of Шаблон:Mvar, denoted Шаблон:Math, is defined by[1]
- <math>h(G) := \min \left\{\frac{| \partial A |}{| A |} \ : \ A \subseteq V(G), 0 < | A | \leq \tfrac{1}{2} | V(G)| \right\}.</math>
The Cheeger constant is strictly positive if and only if Шаблон:Mvar 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.
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 Шаблон:Math (the number of computers in the network) is large.
For example, consider a ring network of Шаблон:Math computers, thought of as a graph Шаблон:Mvar. Number the computers Шаблон:Math clockwise around the ring. Mathematically, the vertex set and the edge set are given by:
- <math>\begin{align}
V(G_{N}) &= \{ 1, 2, \cdots, N-1, N \} \\ E(G_{N}) &= \big\{ \{1, 2\}, \{2, 3\}, \cdots, \{N - 1, N\}, \{N, 1\} \big\} \end{align}</math>
Take Шаблон:Mvar to be a collection of <math>\left \lfloor \tfrac{N}{2} \right \rfloor</math> of these computers in a connected chain:
- <math>A = \left \{ 1, 2, \cdots, \left \lfloor \tfrac{N}{2} \right \rfloor \right \}.</math>
So,
- <math>\partial A = \left \{ \left \{ \left \lfloor \tfrac{N}{2} \right \rfloor, \left \lfloor \tfrac{N}{2} \right \rfloor + 1 \right \}, \{N, 1\} \right \},</math>
and
- <math>\frac{| \partial A |}{| A |} = \frac{2}{\left \lfloor \tfrac{N}{2} \right \rfloor} \to 0 \mbox{ as } N \to \infty.</math>
This example provides an upper bound for the Cheeger constant Шаблон:Math, which also tends to zero as Шаблон:Math. Consequently, we would regard a ring network as highly "bottlenecked" for large Шаблон:Mvar, 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
- <math> 2h(G) \geq \lambda \geq \frac{h^2(G)}{2 \Delta(G)} </math>
in which <math>\Delta(G)</math> is the maximum degree for the nodes in <math>G</math> and <math>\lambda</math> is the spectral gap of the Laplacian matrix of the graph.[2] The Cheeger inequality is a fundamental result and motivation for spectral graph theory.
See also
- Spectral graph theory
- Algebraic connectivity
- Cheeger bound
- Conductance (graph)
- Connectivity (graph theory)
- Expander graph
References
