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 R3 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=cdN1/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 cdN1/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 ≤πR2. 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)2, also kann R nicht kleiner sein als (hN/2)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=cn,LN1/(n-k) einbetten läßt. Beweisen können sie dies für den unwesentlich größeren Wert R=cn,LN1/(n-k)(log N)2k+2.
Als höherdimensionale Analogie der Expander-Graphen betrachten sie dann Simplizialkomplexe, für die sich diese Schranke nicht wesentlich verbessern läßt.
Ihre Beispiele sind (in Analogie zum Beweis für Expander-Graphen) k-dimensionale Simplizialkomplexe X mit der Eigenschaft, daß es zu jeder stetigen Abbildung F:X–>Rk ein y in Rk gibt, so daß F-1(y) mindestens W abgeschlossene k-Simplizes schneidet, für ein festes W. (Im Fall der Expander-Graphen war W=hN/2.)
Arithmetische hyperbolische Mannigfaltigkeiten als höherdimensionale Expander
Gromov-Guth betrachten dann auch noch ein allgemeineres Problem, in dem die 1-Umgebung des Simplizialkomplexes X nicht unbedingt eingebettet sein muß, sondern nur eine Retraktion auf X besitzt. Sie fragen wieder nach unteren Abschätzungen für den Radius R eines Balles, in den eine solche Einbettung möglich ist. Im Kapitel “Estimates for rank of homology and simplicial volume” beweisen sie untere Abschätzungen für Rn gegen die Summe der Bettizahlen oder gegen bestimmte simpliziale Normen auf der Zp-Homologie (aber nicht, wie die Kapitel-Überschrift suggerieren könnte, gegen das simpliziale Volumen), jeweils multipliziert mit konstanten Faktoren.
Explizite Beispiele von solchen höherdimensionalen Expandern sind arithmetische hyperbolische 3-Mannigfaltigkeiten. Für diese bekommt man (bzgl. der allgemeineren Definition von Retraktions-Dicke 1 im vorigen Abschnitt und damit erst recht bzgl. der ursprünglichen Definition von Einbettungen mit Dicke 1) eine untere Abschätzung von R gegen c(hV)1/(n-1), wobei V das Volumen der Mannigfaltigkeit ist und h die Expansivität, die man für Mannigfaltigkeiten ähnlich wie für Graphen definiert:
https://people.maths.ox.ac.uk/lackenby/gottlk2b.pdf
Es ist bekannt, daß man zu arithmetischen hyperbolischen 3-Mannigfaltigkeiten Türme von Überlagerungen mit h>const.>0 und V gegen unendlich hat.
Insbesondere liefern diese Türme also Mannigfaltigkeiten mit beliebig großen Werten für R (den minimalen Radius, in den sich die Mannigfaltigkeit mit Dicke 1 im n-dimensionalen Raum einbetten ließe). Man bekommt also Folgen von 3-dimensionalen Expandern.
Anwendung: Distortion von Knoten
Eine konkrete Anwendung hat das Ergebnis aus dem vorigen Abschnitt, nämlich auf die Konstruktion von Knoten beliebig großer Distortion.
Sei K ein Knoten im 3-dimensionalen Raum. Für Punkte x,y auf K kann man sowohl ihren Abstand dR3(x,y) im 3-dimensionalen Raum als auch den (größeren) Abstand dK(x,y) entlang des Knotens messen. Die Distortion des Knotens ist dann das Supremum von dK(x,y)/dR3(x,y) über alle x≠y. Gromov hatte 1983 die Frage aufgeworfen, ob es zu jedem D Isotopie-Klassen von Knoten gibt mit Distortion > D für alle Knoten in dieser Isotopieklasse.
Eine erste positive Antwort hatte Pardon 2010 für Torusknoten gegeben.
Die Arbeit von Gromov-Guth gibt jetzt eine andere Konstruktion von Knoten großer Distortion. Nach einem Satz von Hilden-Montesinos ist jede geschlossene orientierte 3-Mannigfaltigkeit eine verzweigte 3-fache Überlagerung der 3-Sphäre. Sei K der Knoten, entlang dessen die Überlagerung verzweigt ist. Gromov-Guth beweisen nun, daß man (im Fall hyperbolischer 3-Mannigfaltigkeiten) die Distortion des Knotens K nach unten abschätzen kann gegen chV, wobei wieder h die Expansivität und V das Volumen ist.
Insbesondere für die Folgen “3-dimensionalen Expander” (d.h. die im vorigen Abschnitt erwähnten arithmetischen hyperbolischen 3-Mannigfaltigkeiten), geht die Distortion der Knoten, entlang derer die Überlagerungen verzweigt sind, gegen Unendlich.
Andere Verallgemeinerungen
Es gibt einige andere Ansätze zur Definition höher-dimensionaler Expander. Kurz vor Weihnachten hat Matthew Kahle auf dem ArXiv eine Arbeit mit einer kohomologischen Definition von höherdimensionalen Expandern veröffentlicht, in der er beweist, daß zufällig gewählte Simplizialkomplexe Expander im Sinne seiner Definition sind (asymptotisch für hohe Eckenzahlen mit Wahrscheinlichkeit 1).
Eine andere Verallgemeinerung benutzt Eigenwerte gewisser Operatoren. Für Graphen hängt die Expansivität eng mit dem kleinsten Eigenwert des Laplace-Operators (TvF 102) zusammen, als höherdimensionale Verallgemeinerung konstruierten Lubotzky-Samuels-Vishne Simplizialkomplexe, deren Hecke-Operatoren analoge Abschätzungen erfüllen. Diese Beispiele wiederum haben bestimmte “Überlappungseigenschaften”, die in einer letzten Mai auf dem ArXiv erschienenen Arbeit “Overlap properties of geometric expanders” von Fox-Gromov-Lafforgue-Naor-Pach untersucht werden (und die man ebenfalls als eine Verallgemeinerung der “Expansivität” interpretieren kann):
Für Expander-Graphen Γ hat man (mit demselben Beweis, mit dem man oben beim Kolmogorov-Barzdin-Argument zeigt, daß jede Ebene hN/2 Kanten schneidet) für jede stetige Abbildung f:Γ–>R einen Punkt y in R, so daß f-1(y) mindestens hN/2 Kanten schneidet. Man sagt, daß diese stetige Abbildung f:Γ–>R “hoch-überlappend” ist. Fox-Gromov-Lafforgue-Naor-Pach zeigen, daß die d-dimensionalen Beispiele von Lubotzky-Samuels-Vishne analoge Überlappungseigenschaften haben: für jede stetige Abbildung in den Rd gibt es einen Punkt im Rd, der im Bild einer bestimmten Anzahl von Simplizes liegt.
Gromov, M. (2009). Singularities, Expanders and Topology of Maps. Part 1: Homology Versus Volume in the Spaces of Cycles Geometric and Functional Analysis, 19 (3), 743-841 DOI: 10.1007/s00039-009-0021-7
Gromov, M. (2010). Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry Geometric and Functional Analysis, 20 (2), 416-526 DOI: 10.1007/s00039-010-0073-8
LUBOTZKY, A., SAMUELS, B., & VISHNE, U. (2005). Explicit constructions of Ramanujan complexes of type European Journal of Combinatorics, 26 (6), 965-993 DOI: 10.1016/j.ejc.2004.06.007
Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, & Janos Pach (2010). Overlap properties of geometric expanders ArXiv arXiv: 1005.1392v1
Matthew Kahle (2010). Topological expanders ArXiv arXiv: 1012.5316v1
Misha Gromov, Larry Guth (2011). Generalizations of the Kolmogorov-Barzdin embedding estimates ArXiv : arXiv: 1103.3423v1
Letzte Kommentare