Cheeger-Konstante

In der Mathematik bezeichnet die Cheeger-Konstante eine isoperimetrische Konstante von Graphen und Mannigfaltigkeiten. Anschaulich misst sie deren Stabilität: Eine große Cheeger-Konstante bedeutet, dass sich der Graph (bzw. die Mannigfaltigkeit) nur durch Entfernen einer großen Anzahl von Kanten (bzw. einer Hyperfläche großen Volumens) in nicht miteinander verbundene große Teile zerlegen lässt.

Über die Cheeger-Buser-Ungleichung hängt die Cheeger-Konstante mit dem kleinsten positiven Eigenwert des Laplace-Operators zusammen.

Cheeger-Konstante von Graphen

Die Cheeger-Konstante dieses Graphen ist 1/4: Er kann durch Entfernen von 2 Kanten in zwei Teilgraphen aus je 8 Knoten zerlegt werden.

Es sei ${\displaystyle G=(E,K)}$ ein zusammenhängender Graph.

Für eine Menge von Ecken ${\displaystyle A\subset E}$ bezeichnet man mit ${\displaystyle \partial A\subset K}$ die Menge derjenigen Kanten, die genau eine Ecke in ${\displaystyle A}$ und die andere im Komplement von ${\displaystyle A}$ haben.

Die Cheeger-Konstante ist dann definiert als

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

Anschaulich bedeutet eine kleine Cheeger-Konstante, dass man den Graphen durch Entfernen einer relativ kleinen Menge von Kanten in zwei nicht miteinander zusammenhängende Komponenten annähernd gleicher Größe zerlegen kann. Falls der Graph zum Beispiel ein Telefonnetz beschreibt, dann ist die Cheeger-Konstante also ein Maß für die Stabilität des Netzwerks. Bei hinreichend großer Cheeger-Konstante bleibt das Netz auch nach Ausfall eines Teils der Verbindungen immer noch zusammenhängend.

Beispiel

Für ${\displaystyle k}$-reguläre Ramanujan-Graphen gilt die Ungleichung

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

Dies folgt aus der Cheeger-Buser-Ungleichung ${\displaystyle {\frac {1}{2}}\lambda _{1}\leq h(G)}$ und der Ungleichung ${\displaystyle k-2{\sqrt {k-1}}\leq \lambda _{1}}$ für den kleinsten positiven Eigenwert der Laplace-Matrix des Graphen.

Cheeger-Konstante von Mannigfaltigkeiten

Zerlegung der Sphäre in zwei Komponenten der Fläche ${\displaystyle 2\pi }$.

Es sei ${\displaystyle M}$ eine ${\displaystyle n}$-dimensionale geschlossene Riemannsche Mannigfaltigkeit.

Wir bezeichnen mit ${\displaystyle V(A)}$ das Volumen einer ${\displaystyle n}$-dimensionalen Untermannigfaltigkeit ${\displaystyle A\subset M}$ und mit ${\displaystyle S(E)}$ das ${\displaystyle (n-1)}$-dimensionale Volumen einer Hyperfläche ${\displaystyle E\subset M}$.

Die Cheeger-Konstante von ${\displaystyle M}$ ist definiert als

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

wobei das Infimum über alle zerlegenden Hyperflächen ${\displaystyle E\subset M}$ genommen wird und ${\displaystyle A}$ und ${\displaystyle B}$ jeweils die beiden Zusammenhangskomponenten von ${\displaystyle M\setminus E}$ sind.

Beispiel

Die Cheeger-Konstante der 2-dimensionalen Einheitssphäre ist

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

Das Infimum wird realisiert durch einen Großkreis der Länge ${\displaystyle 2\pi }$, welcher die Sphäre in zwei Komponenten der Fläche ${\displaystyle 2\pi }$ zerlegt.

Siehe auch

• Cheeger-Buser-Ungleichung