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 ein zusammenhängender Graph.

Für eine Menge von Ecken bezeichnet man mit die Menge derjenigen Kanten, die genau eine Ecke in und die andere im Komplement von haben.

Die Cheeger-Konstante ist dann definiert als

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 -reguläre Ramanujan-Graphen gilt die Ungleichung

.

Dies folgt aus der Cheeger-Buser-Ungleichung und der Ungleichung 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 .

Es sei eine -dimensionale geschlossene Riemannsche Mannigfaltigkeit.

Wir bezeichnen mit das Volumen einer -dimensionalen Untermannigfaltigkeit und mit das -dimensionale Volumen einer Hyperfläche .

Die Cheeger-Konstante von ist definiert als

,

wobei das Infimum über alle zerlegenden Hyperflächen genommen wird und und jeweils die beiden Zusammenhangskomponenten von sind.

Beispiel

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

.

Das Infimum wird realisiert durch einen Großkreis der Länge , welcher die Sphäre in zwei Komponenten der Fläche zerlegt.

Siehe auch

Auf dieser Seite verwendete Medien

Graph of small expansivity.jpg
Autor/Urheber: Café Bene, Lizenz: CC BY-SA 3.0
This graph can be decomposed into two subgraphs of almost equal size by removing only two edges. It thus has small expansivity and a small Cheeger constant.