Andi on-line

… und wie sie ihrem Namen gerecht wird.

Seit dem Wochenende beschäftige ich mich mit Extremaler Kombinatorik, einem Fach, über das ich mich am 11. April prüfen lassen werde. Der Einstieg war nicht einfach, aber jetzt kommt langsam Licht uns Dunkel. Nicht erschrecken: Ich mach hier mal den Versuch, eines der Ergebnisse zu erklären. Es geht um Szemeredis Regularitätslemma und die Abschätzung einer Konstanten, die damit verbunden ist. Die Aussage dieses Satzes – er verspricht für Graphen mit einer Größe von mindestens M Knoten eine tolle Eigenschaft – versuche ich im Anschluss zu erklären. Aber vorher die extreme Konstante.
Und diese Konstante M hängt in folgender Weise nur von einem gegebenem positiven Epsilon ab:

M ist der Turm zur Basis 2 mit Höhe (1/Epsilon)^5.

Damit ist gemeint: Man starte mit a_1 = 2 und potenziere dann jeweils 2 mit a_i um a_(i+1) zu erhalten. Dann ist der Turm der Höhe (1/Epsilon)^5 gerade der Wert von a_i mit i = (1/Epsilon)^5. Ein kleines Rechenbeispiel:
Sei Epsilon = 0.5. Damit ist (1/Epsilon)^5 = 32. Wir müssten also a_32 berechnen. Nun ist
a_1 = 2
a_2 = 2^2 = 4
a_3 = 2^(2^2) = 2^4 = 16
a_4 = 2^(2^(2^2)) = 2^16 = 65536
a_5 = 2^(2^(2^(2^2))) = 2^65536 > 2 * 10^19728
(eine 2 mit 19728 Nullen; zum Vergleich: die geschätzte Anzahl der Atome im Universum ist in der Größenordnung von 10^80)

Damit sollte gezeigt sein, dass M für sinnvolle Epsilon so exorbitant groß wird, dass man es nicht mehr aufschreiben will. Immerhin hätten wir in obigem Prozess noch 27 Schritt machen müssen, um M für Epsilon = 0.5 zu bestimmen. Aber was sonst hätte man von Extremaler Kombinatorik erwartet?
Weiter zum Regularitätslemma
Respekt! Da will es jemand genau wissen.

Also hier der versprochene Erklärungsversuch für Szemeredis Regularitätslemma:

Ein Graph ist – in seiner elementarsten Interpretation – eine Menge von Punkten V(auch Knoten genannt) und eine Menge E von Verbindungen zwischen diesen Punkten (auch Kanten genannt). Als einfaches Beispiel denke man hier an ein Dreieck, dessen Ecken durchnummeriert sind. Dieses Dreieck ist ein Graph mit V= {1,2,3} und E = { {1,2}, {2,3}, {3,1} }. Einen solchen Graphen kann man partitionieren, d.h. die Menge seiner Knoten in kleinere Mengen aufteilen, so dass jedes Element genau in einer kleineren Menge landet. Nun kann man sich die Verteilung der Kanten zwischen den so entstandenen kleineren Mengen ansehen. Die Kantendichte ist dabei ein Maß dafür, wie viele der möglichen Kanten zwischen zwei kleinen Mengen vorhanden sind.
Für ein ganz konkretes paar von kleinen Mengen betrachten wir diese Verteilung. Wenn für jeden nicht all zu kleinen Teilgraphen des Paares die Dichte gleich der Dichte des gesamten Paares ist, nennen wir das Paar Epsilon-regulär. Und wenn wiederum fast alle Paare, die man aus den kleinen Mengen bilden kann, Epsilon-regulär sind, nennen wird die Partition Epsilon-regulär. Und hier kommt wieder die Konstante M ins Spiel. Jeder Graph mit mindestens M Knoten hat nämlich eine solche Epsilon-reguläre Partition in k kleine Mengen, wobei m <= k <= M ist.
Und wofür man das braucht erkläre ich ein ander Mal…