Diplomarbeit:
Diplomarbeit von Michael Nüsken bei Prof. Dr. Volker Strassen. Eingereicht am 27. Januar 1993.
(Als DVI-Datei, 14k.)
Euler [12] beschäftigte sich 1782 mit einer `neuen Art magischer Quadrate'. Diese heute sogenannten Eulerquadrate sind Ergebnis einer Verallgemeinerung des alten Rätsels der sechsunddreißig Offiziere. Beim Divisionsball ordnet jedes der sechs anwesenden Regimenter für jeden der sechs Dienstgrade je einen Offizier für eine besondere Aufgabe ab: Die sechsunddreißig Offiziere sollten zur Feier des Tages so im Quadrat aufgestellt werden, daß in jeder Zeile und jeder Spalte genau ein Offizier jeden Regiments und jeden Dienstgrades steht. Wir wissen heute, daß diese Aufgabe nicht lösbar ist. Am Rande sei bemerkt, daß Euler die Regimenter mit lateinischen und die Dienstgrade mit griechischen Buchstaben bezeichnet hat. Eulerquadrate hießen daher in der Literatur oft auch `graeco-lateinische Quadrate'.
Ein Eulerquadrat der Ordnung n definiert man heute als ein Paar zueinander orthogonaler, lateinischer n x n-Quadrate. Ein lateinisches Quadrat enthält nur einen Eintrag pro Feld, und jeder Eintrag tritt genau einmal in jeder Zeile und Spalte auf. Zwei lateinische Quadrate nennt man orthogonal zueinander genau dann, wenn beim Übereinanderlegen kein Paar von Einträgen doppelt vorkommt. Offensichtlich kann es für n=2 kein Eulerquadrat geben. Euler fand (und zählte z.T.) Lösungen für n=3, 4, 5, 7, 8, 9, sowie für beliebige ungerade n und durch 4 teilbare n, aber nicht für n=6. Er vermutete, daß es in diesem Falle und allgemeiner für n=2 (mod 4) keine Lösung gibt. Erst 1901 bestätigte Tarry [20] Euler im Falle n=6 und 1959/60 konnten Bose, Shrikhande und Parker [2,3,4] zeigen, daß Eulers Vermutung für n>6 falsch ist.
Mittlerweile hatte man eine Reihe anderer Strukturen untersucht und Verbindungen zwischen Familien paarweise orthogonaler, lateinischer Quadrate, sogenannten `orthogonalen Arrays' [5] und gewissen Steiner Systemen hergestellt. Ein Steiner System S(r,k,n) vom Index 1 zu Parametern r<=k<=n ist, graphentheoretisch formuliert, ein System von k-Cliquen im vollständigen r-Graphen K(n,r), sodaß jede Kante von K(n,r) zu genau einer k-Clique in gehört. Bekannte Beispiele sind die bekannten Steiner Tripel Systeme S(2,3,n). Andere Beispiele ergeben sich für r=2 im Zusammenhang mit endlichen affinen und projektiven Geometrien und BIBDs (Balanced Incomplete Block Designs). Endliche Möbiusgeometrien [17] sind Steiner Systeme zu r=3. Aus einer Konfiguration zu n=k2, k>=3, r=2, d.i. eine spezielle, affine Geometrie, erhält man ein Eulerquadrat der Ordnung k und sogar k-1 paarweise orthogonale, lateinische Quadrate. Eine ausführliche Darstellung dieser Zusammenhänge und eine große Auswahl an Ergebnissen findet man bei Wallis [22].
Ein Steiner System ist gleichzeitig Packung und Überdeckung. Eine Packung P bzw. Überdeckung K des vollständigen r-Graphen K(n,r) mit k-Cliquen K(k,r) ist ein System von k-Cliquen in K(n,r), sodaß jede Kante zu höchstens bzw. mindestens einer k-Clique des Systems gehört. Nennen wir die größtmögliche Größe einer Packung Packungszahl p(K(n,r),K(k,r)) und analog die kleinstmögliche Größe einer Überdeckung Überdeckungszahl k(K(n,r),K(k,r)). Einfache Abzählargumente (Lemma 2.2) liefern p(K(n,r),K(k,r)) <= (nr) / (kr) <= k(K(n,r),K(k,r)), wobei Gleichheit genau dann gilt, wenn es ein entsprechendes Steiner System gibt. Dann muß natürlich dieser Quotient ganzzahlig sein. Für die Existenz eines Steiner Systems sind aber selbst die notwendigen Bedingungen `(k-ir-i) teilt (n-ir-i) für i=0,...,r-1' nicht immer hinreichend. Es kann kein Steiner System S(2,6,36) geben, denn sonst müßte es auch eine Lösung zum Problem der 36 Offiziere geben. Für r=2 konnte Wilson [23] zeigen, daß diese Bedingungen immerhin für große n genügen. Für beliebiges r sind aber noch keine allgemeinen Ergebnisse bekannt. Bis heute ist es noch nicht einmal gelungen, (nicht-triviale) Steiner Systeme für r>=6 zu finden [16,15]. Solange wir keine genauen Ergebnisse kennen, interessieren wir uns daher für gute Schranken an Packungs- und Überdeckungszahl.
Erdös und Hanani [11] untersuchten 1963 Packungen und Überdeckungen bei festem k und r asymptotisch für große n. Sie konnten für r=2, k beliebig sowie für r=3, k-1 Primpotenz zeigen, daß sich Packungszahl und Überdeckungszahl asymptotisch optimal verhalten. Dazu verwendeten sie im zweiten Falle perfekte Packungen für genügend viele n. Sie vermuteten, daß allgemein für jedes r und k Packungs- und Überdeckungszahl asymptotisch gut sind. Rödl [19] gelang es 1985 schließlich diese Vermutung mit probabilistischen Methoden zu bestätigen.
Der Satz besagt, daß
p(K(n,r),K(k,r)) k(K(n,r),K(k,r))
lim ------------------ = 1 = lim ------------------,
(nr) / (kr) (nr) / (kr)
gilt für n gegen unendlich. Wenn nur genügend Punkte vorhanden sind, dh. n groß ist, so kann man eine Packung finden, die 1-e der perfekten Größe hat. Diese überdeckt dann 1-e aller Kanten. Elementare Argumente liefern unmittelbar, daß die beiden Grenzwertaussagen zueinander äquivalent sind. Hat man etwa eine Packung P, so erhält man daraus eine Überdeckung K, indem man für jede `übrige' Kante eine beliebige, passende k-Clique hinzufügt. War die Packung groß, so wird diese Überdeckung klein sein. Umgekehrt erhält man aus einer Überdeckung eine Packung durch Entfernen aller Cliquen, die eine Kante mit einer anderen Clique der Packung gemein haben.
Rödls Beweis fußt auf zwei wesentlichen Ideen. Man möchte probabilistische Methoden einsetzen und zeigen, daß bei geeigneter zufälliger Wahl eines Systems von Cliquen der Graph K(n,r) gut überdeckt wird. Die erste Idee besteht darin, eine Überdeckung in kleinen Schritten aus e-Nibbles zusammenzusetzen. Man beginnt mit dem vollständigen Graphen K(n,r), wählt ein zufälliges, kleines System von k-Cliquen des Graphen und entfernt alle überdeckten Kanten. In einem genügend kleinen System liegen die gewählten Cliquen erwartungsmäßig `weit' auseinander und überdecken nur wenige Kanten doppelt. Dann wiederholt man dieses Verfahren mit dem ausgedünnten Graphen. So wird sichergestellt, daß Cliquen des nächsten Systems keine schon überdeckte Kante noch einmal überdecken. Zu einem geeigneten Zeitpunkt bricht man ab und überdeckt die wenigen, übrigen Kanten grob. Die zweite Idee, die dieses Vorgehen erst möglich macht, besteht darin, eine gewisse Gleichmäßigkeit nach dem Entfernen der Kanten einer oder mehrer `schöner' Nibbles zu gewährleisten. Aus diesen Gleichmäßigkeitsaussagen hat sich in den letzten Jahren der Begriff Quasizufälligkeit entwickelt.
Bei zufälligen, rho-Bernoulli-verteilten Graphen beobachtet man, daß gewisse Grapheninvarianten etwa gleich ihrem Erwartungswert sind; große Abweichungen sind selten. Ein quasizufälliger Graph soll nun in einem gewissen Sinne `dicht' an einem zufälligen Graphen liegen. Praktisch verlangt man, daß asymptotisch keine (oder nur wenige) großen Abweichungen solcher Grapheninvarianten von ihrem Erwartungswert auftreten. Alle diese Eigenschaften haben asymptotisch Wahrscheinlichkeit 1 und müssen sich daher stark überschneiden. Aber eine ganze Reihe davon sind sogar untereinander äquivalent. Quasizufälligkeit ist daher eine viel universellere Eigenschaft als man zunächst vermuten würde.
In dieser Arbeit zeigen wir den Satz von Rödl (Satz 2.3) mit Hilfe dieser neuen Methoden. Anschließend führen wir einen direkten Beweis für eine wesentliche Äquivalenz gewisser asymptotischer Eigenschaften quasizufälliger Graphen.
Unser Beweis des Satzes von Rödl hält sich im wesentlichen an die Skizze von Alon und Spencer in [1], die eine genaue Umsetzung der geschilderten Ideen mit Hilfe der Quasizufälligkeit ist. Der direkte Äquivalenzbeweis basiert auf Methoden, die uns bereits bei den Vorbereitungen für den Satz von Rödl begegnen werden (siehe Feststellung 2.6), und der Verallgemeinerung einer Idee (zum Beweis von Satz 3.2), mit der Thomason [21] bei 2-Graphen Erfolg hatte.