Cheeger-Buser-Ungleichung

In der Mathematik stellt die Cheeger-Buser-Ungleichung eine Beziehung zwischen der isoperimetrischen Ungleichung und dem Spektrum des Laplace-Operators her. Es gibt eine differentialgeometrische Version (für riemannsche Mannigfaltigkeiten) und eine diskrete Version (für Graphen). Sie ist nach Jeff Cheeger und Peter Buser benannt.

Differentialgeometrische Version

Es sei $M$ eine Riemannsche Mannigfaltigkeit. Wir bezeichnen mit $h(M)$ die Cheeger-Konstante, d. h. die isoperimetrische Konstante. Der kleinste Eigenwert des Laplace-Beltrami-Operators $\Delta f=-\mathrm {div} (\mathrm {grad} \,f)$ ist $\lambda _{0}(M)=0$. Die Cheeger-Ungleichung schätzt die Cheeger-Konstante gegen den zweitkleinsten Eigenwert $\lambda _{1}(M)$ ab:

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

Über die variationelle Charakterisierung von $\lambda _{1}$ erhält man $\lambda _{1}\int _{M}f^{2}dV\leq \int _{M}|\nabla f|^{2}dV$ und damit ist die Cheeger-Ungleichung unmittelbar äquivalent zu einer oberen Schranke für die Konstante $C$ in der $L^{2}$-Poincaré-Ungleichung

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

für alle glatten Funktionen $f\colon M\to \mathbb {R}$ mit $\int _{M}fdV=0$.

Die Buser-Ungleichung (auch Ungleichung von Buser-Ledoux) besagt

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

wobei $K\leq 0$ eine untere Schranke für die Ricci-Krümmung sein soll. Mit einer unteren Schranke für die Ricci-Krümmung und einer oberen Schranke für $C$, oder äquivalent einer unteren Schranke für $\lambda _{1}(M)$, erhält man also eine untere Schranke für $h(M)$.

Diskrete Version

Betrachte die Adjazenzmatrix $A$ eines zusammenhängenden $k$-regulären Graphen $\Gamma$. Die Laplace-Matrix ist definiert als $\Delta =k\mathrm {Id} -A$. Ihr kleinster Eigenwert ist $\lambda _{0}(\Gamma )=0$. Der zweitkleinste Eigenwert $\lambda _{1}(\Gamma )$ wird als Maß für die Expansivität des Graphen interpretiert. Es gilt nämlich die auf Dodziuk, Alon und andere zurückgehende diskrete Cheeger-Buser-Ungleichung:

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

wobei $h(\Gamma )$ die Cheeger-Konstante, d. h. die isoperimetrische Konstante, des Graphen bezeichnet.

Literatur

Differentialgeometrische Version:

• Peter Buser: Über eine Ungleichung von 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.

Diskrete 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.

Weblinks

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