Cheeger constant

In mathematics , the Cheeger constant denotes an isoperimetric constant of graphs and manifolds. It clearly measures their stability: A large Cheeger constant means that the graph (or the manifold) can only be broken down into large, unconnected parts by removing a large number of edges (or a hypersurface of large volume).

Via the Cheeger-Buser inequality , the Cheeger constant is related to the smallest positive eigenvalue of the Laplace operator .

Cheeger constant of graphs

The Cheeger constant of this graph is 1/4: It can be broken down into two subgraphs of 8 nodes each by removing 2 edges.

Let it be a connected graph . ${\displaystyle G=(E,K)}$

For a set of corners , one denotes the set of edges that have exactly one corner in and the other in the complement of . ${\displaystyle A\subset E}$ ${\displaystyle \partial A\subset K}$ ${\displaystyle A}$ ${\displaystyle A}$

The Cheeger constant is then defined as

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

A small Cheeger constant means that the graph can be broken down into two non-connected components of approximately the same size by removing a relatively small number of edges. If the graph describes a telephone network, for example, then the Cheeger constant is a measure of the stability of the network. If the Cheeger constant is sufficiently large, the network will still remain connected even if some of the connections fail.

example

For -regular Ramanujan graphs the inequality holds ${\displaystyle k}$

${\displaystyle h(G)\geq {\frac {k}{2}}-{\sqrt {k-1}}}$.

This follows from the Cheeger-Buser inequality and the inequality for the smallest positive eigenvalue of the Laplace matrix of the graph. ${\displaystyle {\frac {1}{2}}\lambda _{1}\leq h(G)}$ ${\displaystyle k-2{\sqrt {k-1}}\leq \lambda _{1}}$

Cheeger constant of manifolds

Decomposition of the sphere into two components of the surface . ${\displaystyle 2\pi ^{2}}$

Let it be a -dimensional closed Riemannian manifold . ${\displaystyle M}$ ${\displaystyle n}$

We denote with the volume of a -dimensional submanifold and with the -dimensional volume of a hypersurface . ${\displaystyle V(A)}$ ${\displaystyle n}$ ${\displaystyle A\subset M}$ ${\displaystyle S(E)}$ ${\displaystyle (n-1)}$ ${\displaystyle E\subset M}$

The Cheeger constant of is defined as ${\displaystyle M}$

${\displaystyle h(M):=\inf _{E\subset M}{\frac {S(E)}{\min(V(A),V(B))}}}$,

where the infimum is taken over all decomposing hypersurfaces and and are the two connected components of . ${\displaystyle E\subset M}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle M\setminus E}$

example

The Cheeger constant of the 2-dimensional unit sphere is

${\displaystyle h(S^{2})={\frac {1}{\pi }}}$.

The infimum is realized by a great circle of length , which divides the sphere into two components of the surface . ${\displaystyle 2\pi }$ ${\displaystyle 2\pi ^{2}}$

See also

• Cheeger-Buser inequality