Cheeger-Buser inequality

In mathematics , the Cheeger-Buser inequality establishes a relationship between the isoperimetric inequality and the spectrum of the Laplace operator . There is a differential geometric version (for Riemannian manifolds) and a discrete version (for graphs). It is named after Jeff Cheeger and Peter Buser .

Differential geometric version

Let it be a Riemannian manifold . We denote by the Cheeger constant , i.e. H. the isoperimetric constant. The smallest eigenvalue of the Laplace-Beltrami operator is . The Cheeger inequality estimates the Cheeger constant against the second smallest eigenvalue : ${\displaystyle M}$ ${\displaystyle h(M)}$ ${\displaystyle \Delta f=-\mathrm {div} (\mathrm {grad} \,f)}$ ${\displaystyle \lambda _{0}(M)=0}$ ${\displaystyle \lambda _{1}(M)}$

${\displaystyle h(M)\leq 2{\sqrt {\lambda _{1}(M)}}.}$

Via the variational characterization of one obtains and thus the Cheeger inequality is directly equivalent to an upper bound for the constant in the - Poincaré inequality ${\displaystyle \lambda _{1}}$ ${\displaystyle \lambda _{1}\int _{M}f^{2}dV\leq \int _{M}|\nabla f|^{2}dV}$ ${\displaystyle C}$ ${\displaystyle L^{2}}$

${\displaystyle \int _{M}f^{2}dV\leq C\int _{M}|\nabla f|^{2}dV}$

for all smooth functions with . ${\displaystyle f\colon M\to \mathbb {R} }$ ${\displaystyle \int _{M}fdV=0}$

The Buser inequality (also Buser-Ledoux inequality ) states

${\displaystyle \lambda _{1}(M)\leq 6\,\mathrm {max} \left\{{\sqrt {-K}}h(M),6h(M)^{2}\right\}}$,

where should be a lower bound for the Ricci curvature . With a lower bound for the Ricci curvature and an upper bound for , or equivalently a lower bound for , one obtains a lower bound for . ${\displaystyle K\leq 0}$ ${\displaystyle C}$ ${\displaystyle \lambda _{1}(M)}$ ${\displaystyle h(M)}$

Discreet version

Consider the adjacency matrix of a connected - regular graph . The Laplace matrix is defined as . Your smallest eigenvalue is . The second smallest eigenvalue is interpreted as a measure of the expansion of the graph. The discrete Cheeger-Buser inequality , which goes back to Dodziuk, Alon and others, applies : ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle \Gamma }$ ${\displaystyle \Delta =k\mathrm {Id} -A}$ ${\displaystyle \lambda _{0}(\Gamma )=0}$ ${\displaystyle \lambda _{1}(\Gamma )}$

${\displaystyle {\frac {1}{2}}\lambda _{1}(\Gamma )\leq h(\Gamma )\leq {\sqrt {2\lambda _{1}(\Gamma )}},}$

where the Cheeger constant , d. H. the isoperimetric constant of the graph. ${\displaystyle h(\Gamma )}$

literature

Differential geometric version:

• Peter Buser : About an inequality from Cheeger. Math. Z. 158 (1978), no. 3, 245-252, doi: 10.1007 / BF01214795 .
• Michel Ledoux : A simple analytic proof of an inequality by P. Buser. Proc. Amer. Math. Soc. 121 (1994) no. 3, 951-959, JSTOR 2160298 .
• Isaac Chavel : Eigenvalues ​​in Riemannian Geometry. Academic Press, 1984. ISBN 978-0121706401 .

Discrete version:

• Alexander Lubotzky : Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski. Progress in Mathematics, 125. Birkhäuser Verlag, Basel, 1994. ISBN 3-7643-5075-X .

Web links

• S. Liu: Cheeger constant, spectral clustering and eigenvalue ratios of Laplacians
• FRK Chung: Laplacians of graphs and Cheeger inequalities