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 GraphenBearbeiten

 
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.

BeispielBearbeiten

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 MannigfaltigkeitenBearbeiten

 
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.

BeispielBearbeiten

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 auchBearbeiten