Letzte Woche auf dem ArXiv erschien eine Arbeit von Gromov-Guth über höherdimensionale Verallgemeinerungen von Expander-Graphen, mit Anwendungen auf die Distortion von Knoten.

Expander-Graphen

Die “Expansivität” eines Graphen (mit Ecken E, Kanten K) wird durch die Cheeger-Zahl gemessen:

h:=min { #K(A,B)/min(#A,#B) : A U B = E }

wobei man also alle Zerlegungen der Eckenmenge E in zwei Teile A und B anschaut und #K(A,B) dann die Zahl der Verbindungskanten von A nach B ist.

Die “Expansivität” mißt die Stabilität des durch den Graphen beschriebenen Netzwerkes:
h ist klein, wenn man den Graphen so in zwei (annähernd gleich große) Teile zerlegen kann, daß es nur wenige Verbindungen zwischen den beiden Teilen gibt – das “Netzwerk” ist dann sehr instabil, weil eine Störung dieser wenigen Verbindungen bereits den Zusammenhang zerstört.
(Die Graphen unten kann man z.B. durch Entfernen von 4 Kanten in Hälften mit 8-10 Stücken zerlegen, also ist h höchstens 4/8=0,5. Quelle: Mathworld)

U.a. für Anwendungen in der Theoretischen Informatik forscht man (vgl. TvF 101, TvF 102, TvF 103) schon seit langem nach systematische Methoden, um regelmäßige Graphen mit
– irgendeiner (großen) Zahl n von Ecken und
– irgendeiner festen Zahl d von Kanten an jeder Ecke
– mit nicht zu kleiner Expansivität h zu konstruieren.
Solche Folgen von Graphen (bei denen die Expansivität h größer ist als eine Konstante ε) heißen Expander-Folgen.

Graphen im 3-dimensionalen Raum (Kolmogorov-Barzdin)

Gemeinhin wurde die Definition von Expander-Graphen und der Beweis, daß zufällig gewählte Graphen Expander sind, einer Arbeit von Pinsker aus dem Jahr 1973 (“On the complexity of a concentrator”) zugeschrieben. Offenbar erst seit kurzem ist bekannt, daß Kolmogorov und Barzdin in einer 1967 (auf Russisch) veröffentlichten Arbeit über Einbettungen von Graphen im 3-dimensionalen Raum schon Expander betrachteten und auch bereits bewiesen hatten, daß zufällige Graphen Expander sind.

In der Arbeit von Kolmorov-Barzdin ging es eigentlich um die Frage, wie man verdickte Graphen in den 3-dimensionalen Raum R³ einbetten kann. D.h. man hat einen gegebenen Graphen und man sucht die kleinste Zahl R, so daß sich der mit Radius 1 verdickte Graph in einen Ball B mit Radius R einbetten läßt. (Soll heißen: man hat den eingebetten Graphen Γ in B, seine 1-Umgebung liegt in B und die 1-Umgebung ist eingebettet: die 1-Umgebungen unterschiedlicher Ecken oder Kanten schneiden sich nicht, außer natürlich, wenn die Ecke ein Randpunkt der Kante ist.)

Kolmogorov-Barzdin bewiesen, daß man einen (mit Radius 1 verdickten) d-regulären Graphen mit N Ecken in einen Ball mit Radius R=c_dN^1/2 einbetten kann.
Außerdem, und hier kommen dann Expander ins Spiel, untersuchten sie, ob dieser Wert optimal ist: sie zeigten, daß es Folgen von Expandern (mit N gegen unendlich) gibt, für die man R nicht kleiner als c_dN^1/2 wählen kann.
Die Idee der Konstruktion: man wähle eine Ebene, so daß gleich viele Ecken (also jeweils N/2) des Graphen auf beiden Seiten der Ebene liegen. Wenn der Graph Expansivität h hat, gibt es also hN/2 Kanten, die die beiden Eckenmengen verbinden, d.h. die Ebene schneidet mindestens hN/2 Kanten. Der Schnitt der Ebene mit dem Ball B hat Flächeninhalt ≤πR². Wenn der Graph mit Dicke 1 eingebettet ist, schneiden die 1-Umgebungen der hN/2 Kanten den Ball B in Kreisen der Gesamt-Fläche π(hN/2)², also kann R nicht kleiner sein als (hN/2)².

Höherdimensionale Version von Kolmogorov-Barzdin

In der neuen Arbeit von Gromov-Guth wird zunächst die Arbeit von Kolmogorov-Barzdin verallgemeinert:
man hat einen k-dimensionalen Simplizialkomplex, den man in den n-dimensionalen Raum einbetten will – gesucht ist das kleinste R, so daß sich der mit Radius 1 verdickte Simplizialkomplex in einen Ball B mit Radius R einbetten läßt.

Gromov-Guth vermuten, daß sich ein k-dimensionaler Simplizialkomplex mit L Simplizes mit Dicke 1 in einen Ball vom Radius R=c_n,LN^1/(n-k) einbetten läßt. Beweisen können sie dies für den unwesentlich größeren Wert R=c_n,LN^1/(n-k)(log N)^2k+2.