Expander-Graphen, stabile Telefon-Netzwerke und Sortieralgorithmen.
Es ging in den letzen Wochen ja um Anwendungen der Geometrisierung von Flächen. Eine “Anwendung” der 2-dimensionalen hyperbolischen Geometrie war die Veranschaulichung von Modulformen, der “5. Grundrechenart”.
Wir hatten letzte Woche darüber geschrieben, daß Modulformen viele zahlentheoretische Zusammenhänge kodieren. Um auch noch eine ‘reellere’ Anwendung von Modulformen zu diskutieren, soll es heute (und nächste Woche) um Expander-Graphen (und ihre Konstruktion m.H. von Modulformen) gehen.
Ein Expander-Graph ist ein Graph (bestehend aus Ecken und Kanten, man denke an ein Telefon-Netzwerk oder auch einen Mikrochip) mit guten Zusammenhangseigenschaften. Also: das Entfernen einer bestimmten Anzahl von Kanten soll den Zusammenhang nicht zerstören. In den Beispielen unten (Quelle: Mathworld) wird z.B. durch das Entfernen von 3 Kanten der Zusammenhang nicht zerstört (bzw. es wird nur eine Ecke abgetrennt), durch das Entfernen von 4 Kanten aber schon.
Wie man die ‘Expansion’ eines Graphen genau berechnet, hatte ich hier schon mal beschrieben. Anschaulich geht es einfach um folgendes: die ‘Expansion’ des Graphen ist groß, wenn es nicht möglich ist, ihn durch Entfernen weniger Kanten in zwei annähernd gleich große Komponenten zu zerlegen.
Für praktische Zwecke will man natürlich nicht nur einen einzelnen Graphen konstruieren, sondern man will (möglichst systematisch) Graphen mit immer mehr Ecken finden, deren ‘Expansion’ oberhalb einer positiven Schranke bleibt.
Also, bei einer steigenden Zahl von Telefon-Kunden soll das wachsende Netz trotzdem noch immer gute Zusammenhangseigenschaften haben (ohne zuviele Leitungen zu brauchen.)
Die wirklichen Anwendungen von Expander-Graphen sind natürlich weniger in der Konstruktion von Telefon-Netzwerken, sondern in anderen wichtigen Algorithmen. Lubotzky schreibt im Vorwort seines Buches über Expander:
“We cannot do better than quoting Klawe’s introduction”
und zitiert dann aus Klawe’s Artikel (1984) u.a.:
Perhaps the most practical applications of expanding graphs occur in the two most recent results.
Ajtai, Komlos and Szemeredi have announced the construction of an oblivious sorting network using O(nlogn) comparators, and having depth O(logn). Again, expanding graphs form the basic components, and of course, the explicit construction of the network depends on the explicit construction of expanding graphs. The problem of constructing such a sorting network has been open for twenty years, which perhaps illustrates best the unexpected power of expanding graphs.
Finally, expanding graphs have been used by Karp and Pippenger to design an algorithm which can be applied to virtually all the well-known Monte-Carlo algorithms to reduce the number of uses of a randomization resource (i.e., coin-flips or calls to a random number generator) while still maintaining polynomial running time.
Das von Ajtai-Komlos-Szemeredi 1983 entwickelte AKS-Sortier-Netzwerk ist übrigens bis heute das beste, und man kann beweisen, daß es asymptotisch optimal ist.
Man braucht also systematische Verfahren, um Expander-Graphen zu konstruieren.
Das sollte eigentlich nicht schwierig sein: man weiß, daß im Sinne der Wahrscheinlichkeitstheorie die meisten Graphen Expander sind.
Gromov schreibt in seinem Manuskript über “Structures, Learning and Ergosystems” auf Seite 71 ff:
A cluster W is a subset in the vertex set V of G, such that “most” edges issuing from the vertices in W have their second vertices back in W.
[…]
Some graphs, can not be clusterized: every vertex (sub)set W in such a graph either has, roughly, as many outcoming edges as there are edges within this (sub)set or the complement of W in the full vertex set V of the graph has this property.
[…]
But if you start believing it and look, for example, at graphs obtained by randomly attaching M edges to (the pairs of vertices of) an N-string (or to any connected graph with N edges, e.g. to a tree with N + 1 vertices) you see with little effort that if M bigger than N, then the unclusterable graphs come up with overwhelming probability for large N. This was first(?) observed by Kolmogorov-Brazdin (1967). Now-a-days, these are called expander graphs
Soll heißen: wenn man einfach zufällig einen Graphen zeichnet, sollte dieser mit hoher Wahrscheinlichkeit ein Expander sein.
Trotzdem braucht man ziemlich komplizerte Methoden,wenn man systematisch Expander-Graphen konstruieren will. Einfach zu konstruierende Graphen sind oft keine Expander. (Eine, zugegenermaßen ziemlich weit hergeholte, Analogie zur Topologie: die meisten Flächen sind hyperbolisch, eine zufällig gezeichnete Fläche sollte also hyperbolisch sein. Trotzdem wird, wer versucht Flächen zu konstruieren, zunächst auf die Sphäre und den Torus kommen, die gerade als einzige nicht hyperbolisch sind.
Ähnlich in höheren Dimensionen, wo es gar nicht so einfach ist, explizite Beispiele hyperbolischer Mannigfaltigkeiten zu konstruieren, obwohl die meisten 3-Mannigfaltigkeiten hyperbolisch sind.)
Eine der Methoden zur Konstruktion von Expander-Graphen benutzt Modulformen und 2-dimensionale hyperbolische Geometrie, ein bißchen mehr dazu nächste Woche.
Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 90, Teil 91, Teil 92, Teil 93, Teil 94, Teil 95, Teil 96, Teil 97, Teil 98, Teil 99, Teil 100
Letzte Kommentare