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

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

Über die variationelle Charakterisierung von ${\displaystyle \lambda _{1}}$ erhält man ${\displaystyle \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 ${\displaystyle C}$ in der ${\displaystyle L^{2}}$-Poincaré-Ungleichung

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

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

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

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

wobei ${\displaystyle 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 ${\displaystyle C}$, oder äquivalent einer unteren Schranke für ${\displaystyle \lambda _{1}(M)}$, erhält man also eine untere Schranke für ${\displaystyle h(M)}$.

Diskrete Version

Betrachte die Adjazenzmatrix ${\displaystyle A}$ eines zusammenhängenden ${\displaystyle k}$-regulären Graphen ${\displaystyle \Gamma }$. Die Laplace-Matrix ist definiert als ${\displaystyle \Delta =k\mathrm {Id} -A}$. Ihr kleinster Eigenwert ist ${\displaystyle \lambda _{0}(\Gamma )=0}$. Der zweitkleinste Eigenwert ${\displaystyle \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:

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

wobei ${\displaystyle 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.
• Isaac Chavel: Eigenvalues in Riemannian Geometry. Academic Press, 1984. ISBN 978-0121706401.
• Michel Ledoux: A simple analytic proof of an inequality by P. Buser. Proc. Amer. Math. Soc. 121 (1994), no. 3, 951–959, JSTOR:2160298.

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