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 $\mathrm{\Delta }f=-\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{d}f)$ ist ${\lambda }_0(M)=0$. Die Cheeger-Ungleichung schätzt die Cheeger-Konstante gegen den zweitkleinsten Eigenwert ${\lambda }_1(M)$ ab:

$h(M)\le 2\sqrt{{\lambda }_1(M)}.$

Über die variationelle Charakterisierung von ${\lambda }_1$ erhält man ${\lambda }_1\underset{M}{\int }{f}^{2}dV\le \underset{M}{\int }|\mathrm{\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

$\underset{M}{\int }{f}^{2}dV\le C\underset{M}{\int }|\mathrm{\nabla }f{|}^{2}dV$

für alle glatten Funktionen $f:M\to ℝ$ mit $\underset{M}{\int }fdV=0$.

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

${\lambda }_1(M)\le 6\mathrm{m}\mathrm{a}\mathrm{x}\{\sqrt{-K}h(M),6h(M{)}^2\}$,

wobei $K\le 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 $\mathrm{\Gamma }$. Die Laplace-Matrix ist definiert als $\mathrm{\Delta }=k\mathrm{I}\mathrm{d}-A$. Ihr kleinster Eigenwert ist ${\lambda }_0(\mathrm{\Gamma })=0$. Der zweitkleinste Eigenwert ${\lambda }_1(\mathrm{\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(\mathrm{\Gamma })\le h(\mathrm{\Gamma })\le \sqrt{2{\lambda }_1(\mathrm{\Gamma })},$

wobei $h(\mathrm{\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, Vorlage:JSTOR.
• 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