Eine untere Schranke für die Schwellenwertfunktion der Dreifärbbarkeit

— Studienarbeit —

Michael Behrisch Betreuer: Dr. Anusch Taraz

Institut für Informatik Humboldt–Universität zu Berlin Lehrstuhl für Algorithmen und Komplexität

19. April 2001

Zusammenfassung Ziel dieser Studienarbeit ist es zu beweisen, dass die Knoten eines zufälligen Graphen, der bei n Knoten etwa 1.9·n Kanten hat, mit hoher Wahrscheinlichkeit so mit drei Farben gefärbt werden können, dass zwei Knoten, die durch eine Kante verbunden sind, verschiedene Farben haben.

1 Einleitung

Sei G_{n} die Menge aller Graphen mit Knotenmenge [n] := {1, …, n} und G_{n,p} ein zufälliger Graph aus G_{n}, der generiert wird, indem jede Kante mit Erfolgswahrscheinlichkeit p = p(n) ausgewürfelt wird. In der grundlegenden Arbeit zum Thema zufällige Graphen von Erdős und Rényi [6] wurde gezeigt, dass viele Grapheneigenschaften eine so genannte Schwellenwertfunktion t besitzen, das heißt:

Definition 1. Für eine Grapheneigenschaft A ⊂ G_{n} heißt eine Funktion t = t(n) Schwellenwertfunktion, wenn:

p(n) ≪ t(n) ⇒ ℙ [G_{n,p} ∈ A] ⟶^{n→∞} 1,

p(n) ≫ t(n) ⇒ ℙ [G_{n,p} ∈ A] ⟶^{n→∞} 0.

Im ersten Fall sagt man, G_{n,p} hat fast sicher die Eigenschaft A. Für eine Grapheneigenschaft A ⊂ G_{n} heißt eine Funktion t = t(n) scharfe Schwellenwertfunktion, wenn für beliebiges ε > 0 gilt:

p(n) ≤ (1 − ε)t(n) ⇒ ℙ [G_{n,p} ∈ A] ⟶^{n→∞} 1,

p(n) ≥ (1 + ε)t(n) ⇒ ℙ [G_{n,p} ∈ A] ⟶^{n→∞} 0.

Achlioptas und Friedgut [1] haben nun gezeigt, dass die chromatische Zahl χ eines Graphen (die kleinste Zahl k, so dass es eine k-Partition der Knotenmenge gibt, die nur Knoten, die nicht durch eine Kante verbunden sind, der gleichen Partitionsklasse zuordnet) solch einen scharfen Schwellenwert in der Größenordnung \frac{c_{k}}{n} hat, was Inhalt des folgenden Satzes ist.

Satz 2. Für jedes k ≥ 3 gibt es eine Funktion c_{k}(n) > 0, so dass für jedes ε > 0 und jede Funktion p(n) mit p ≤ \frac{c_{k}−ε}{n} ein G_{n,p} fast sicher k-färbbar ist, während für p ≥ \frac{c_{k}+ε}{n} ein G_{n,p} fast sicher nicht k-färbbar ist.

Es wird vermutet, dass c_{k} für n gegen unendlich gegen eine feste Zahl strebt, bis jetzt konnten jedoch selbst für c_{3} nur obere und untere Schranken angegeben werden. So lässt sich durch einfaches Abschätzen des Erwartungswerts der Anzahl der Färbungen eines G_{n,p} in Verbindung mit der Markowschen Ungleichung (Lemma 5) schon zeigen, dass c_{3} < 5.42. Achlioptas und Molloy [3] verbesserten diese Schranke auf c_{3} < 5.044 indem sie nur noch so genannte rigide Färbungen zuliessen, die jeder dreifärbbare Graph hat, deren Erwartungswert aber schneller schrumpft. Kaporis, Kirousis und Stamatiou [8] erreichten durch genauere Berechnung des Erwartungswerts der Anzahl rigider Färbungen noch eine Verbesserung auf c_{3} < 4.99.

Für die untere Schranke stammt das beste bekannte Resultat (c_{3} > 3.847) aus der Analyse eines Färbungsalgorithmus’ ebenfalls von Achlioptas und Molloy [2] und wird in dieser Arbeit mit dem gleichen Ansatz erneut bewiesen.

Wegen der Schärfe des Schwellenwerts kann man folgende Proposition zur Vereinfachung des Beweises nutzen.

Proposition 3. Falls für eine Konstante d_{k} und p = \frac{d_{k}}{n} der G_{n,p} mit Wahrscheinlichkeit ρ > 0 mit k Farben gefärbt werden kann, so gilt d_{k} ≤ sup c_{k}.

Beweis. Wenn obiges d_{k} echt größer als sup c_{k} wäre, so ließe sich auch ein ε finden, um dass sich beide unterscheiden, woraus nach Satz 2 folgt, dass G_{n,p} fast sicher nicht k-färbbar ist, was im Widerspruch zur Voraussetzung steht.

Zu Beginn werden noch einige nützliche Abschätzungen bewiesen.

Lemma 4. Sei x eine nicht negative reelle Zahl. Dann gilt: 1 − x ≤ e^{−x}

Beweis. Sei f(x) := 1 − x und g(x) := e^{−x}. Wegen f′(x) = −1 und g′(x) = −e^{−x} ist klar, dass f(0) = g(0) und f′(0) = g′(0). Da für alle x > 0 gilt f′(x) < g′(x), folgt mit dem Mittelwertsatz der Differentialrechnung das Behauptete.

Lemma 5. Sei X eine nicht negative Zufallsvariable, μ := 𝔼 [X]. Dann gilt:

1.

∀t > 0 : ℙ [X ≥ t] ≤ \frac{𝔼 [X]}{t}  (Markowsche Ungleichung).

2. Sei X weiterhin die Summe unabhängiger Indikatorvariablen, so dass X = ∑_{i=1}^{k} Y_{i}, Y_{i} ∈ {0, 1} mit ℙ [Y_{i} = 1] = p_{i}. Dann gilt für beliebiges β > 1

ℙ [X ≥ βμ] ≤ (\frac{e}{β})^{βμ}  (Tschernowsche Ungleichung).

Beweis.

1.

𝔼 [X] =^{Def} ∑_{y∈Ω(X)} y · ℙ [X = y] ≥ ∑_{y≥t} y · ℙ [X = y] ≥ t · ∑_{y≥t} ℙ [X = y] = t · ℙ [X ≥ t]

2. Für jedes positive t ist

ℙ [X ≥ βμ] = ℙ [exp(tX) ≥ exp(tβμ)].

Aus der Markow-Ungleichung (siehe 1.) folgt:

ℙ [X ≥ βμ] ≤ \frac{𝔼 [exp(tX)]}{exp(tβμ)}.

Aufgrund der Darstellung von X als Summe von Indikatorvariablen und deren Unabhängigkeit folgt:

𝔼 [exp(tX)] = 𝔼 [exp(t ∑_{i=1}^{k} Y_{i})] = 𝔼 [∏_{i=1}^{k} exp(tY_{i})] = ∏_{i=1}^{k} 𝔼 [exp(tY_{i})].

Die Zufallsvariable exp(tY_{i}) nimmt mit Wahrscheinlichkeit p_{i} den Wert exp(t) und mit Wahrscheinlichkeit 1 − p_{i} den Wert exp(0) = 1 an. Ihr Erwartungswert ist demzufolge:

𝔼 [exp(tY_{i})] = p_{i} exp(t) + (1 − p_{i}) = p_{i}(e^{t} − 1) + 1 ≤ exp(p_{i}(e^{t} − 1)),

da x + 1 ≤ exp(x). Es gilt also:

ℙ [X ≥ βμ] ≤ \frac{∏_{i=1}^{k} exp(p_{i}(e^{t} − 1))}{exp(tβμ)}

= \frac{exp(∑_{i=1}^{k} p_{i}(e^{t} − 1))}{exp(tβμ)}

= \frac{exp(μ(e^{t} − 1))}{exp(tβμ)}.

Da die obige Ungleichung für beliebige positive t gilt und β > 1, kann man t = ln β setzen und erhält:

ℙ [X ≥ βμ] ≤ \frac{e^{μ(β−1)}}{β^{βμ}}

≤ (\frac{e}{β})^{βμ}.

2 Eine untere Schranke

Eine untere Schranke für c_{3} lässt sich finden, indem man einen Färbungsalgorithmus analysiert und beweist, dass er gegebene zufällige Graphen mit höchstens drei Farben färbt. Diesem Ansatz soll im Folgenden nachgegangen werden.

2.1 Der Algorithmus Listenfärbung

Algorithm 1: k–Greedy–Listenfärbung Input: Ein Graph auf n Knoten und eine Zahl k Output: Ein mit höchstens k Farben gefärbter Graph oder ”Fehlschlag“ k–GL(G)

(1) Sei U := V (G) und L_{v} := {1, …, k} für jedes v ∈ U.

(2) while U ≠ ∅

(3) Wähle einen zufälligen Knoten v aus {u ∈ U : |L_{u}| ist minimal}.

(4) if L_{v} ≠ ∅

(5) Gib v eine zufällige Farbe ω ∈ L_{v}.

(6) else

(7) Ausgabe ”Fehlschlag“.

(8) foreach u ∈ U ∩ Γ(v)

(9) L_{u} := L_{u} \ {ω}.

(10) Setze U := U \ {v}.

Die Funktionsweise dieses Algorithmus ist nicht schwer zu verstehen. Er hält für jeden Knoten eine Liste der Farben L_{v}, mit denen dieser noch gefärbt werden kann, und wählt, solange noch Knoten ungefärbt sind, unter den Knoten mit einer kardinalitätsminimalen Liste einen aus und färbt ihn, wenn möglich. Anschließend entfernt er die Farbe aus den Vorratslisten der Nachbarn. Offensichtlich liefert dies eine Färbung von G mit k Farben oder die Ausgabe ”Fehlschlag“. Um die Analyse zu vereinfachen, gehe man davon aus, dass der Algorithmus auch bei der Ausgabe Fehlschlag erst einmal weiter arbeitet.

Für die hier angestrebte untere Schranke für c := c_{3} gilt es nun das größte c zu finden, so dass 3-GL für einen zufälligen Graphen G_{n,p} mit p = \frac{c}{n} immer noch erfolgreich färbt. Dabei genügt es zu zeigen, dass die Erfolgswahrscheinlichkeit echt größer als ein festes ρ > 0 ist, da mit Proposition 3 dann bereits die sichere Dreifärbbarkeit folgt.

Die Analyse wird sich dabei im wesentlichen darauf stützen, die Menge der Knoten zu kontrollieren, die im Laufe des Algorithmus nur noch höchstens zwei Farben in ihrer Farbliste besitzen. Es wird gezeigt, dass für geeignete Werte von c in diese Menge von Knoten pro Schritt des Algorithmus nur ein Knoten eintritt, der dann im nächsten Schritt gefärbt wird, womit der Knoten niemals weitere Farben verliert, und der Algorithmus den gesamten Graph erfolgreich färbt.

Proposition 6. Der Algorithmus k-GL färbt Graphen, bei denen alle Komponenten höchstens einen Kreis haben, optimal.

Beweis. Zum Beweis ist es günstiger, eine deterministische Variante des Algorithmus zu wählen, was aber, wie man sehen wird, keine wirkliche Einschränkung bedeutet. Sei weiterhin ohne Beschränkung der Allgemeinheit der zu färbende Graph zusammenhängend (sonst färbe man die Komponenten einzeln).

Seien also die Knoten des Graphen fortlaufend nummeriert, und ersetze man die Zeile ”Wähle einen zufälligen Knoten v aus …“ durch ”Wähle den Knoten v mit der niedrigsten Nummer aus …“. Da die Nummerierung beliebig ist, stellt diese Veränderung offenbar keine Einschränkung dar.

Da der Graph zusammenhängend ist, gibt es in jedem Schritt des Algorithmus’ (außer dem ersten) einen Knoten, der nicht mehr über die volle Farbliste verfügt, da sein Nachbar bereits gefärbt wurde. Damit werden offenbar in jedem Schritt nur Knoten gefärbt, die bereits mindestens einen gefärbten Nachbarn besitzen. Demzufolge ist der von der Menge der gefärbten Knoten auf dem Originalgraph induzierte Subgraph stets zusammenhängend. Daraus folgt wiederum, dass der letzte gefärbte Knoten entweder ein Blatt oder ein Kreisknoten mit genau zwei Nachbarn ist.

Der Beweis erfolgt nun über vollständige Induktion über die Knotenzahl, wobei der Induktionsanfang (ein Knoten) trivial ist. Sei nun G ein Graph auf n + 1 Knoten, bei dem im Laufe des Algorithmus’ der Knoten v als letzter gefärbt werden würde. Man sieht, dass das Entfernen von v aus G am Laufe des Algorithmus (bis zum vorletzten Knoten) nichts ändert, da die Wahl eines zu färbenden Knoten im Algorithmus immer nur von schon gefärbten Knoten abhängt und v ja als letzter gefärbt werden würde und somit die Farblisten seiner Nachbarn nicht beeinflusst haben könnte. Nach Induktionsvoraussetzung wird G \ v aber korrekt gefärbt, denn G \ v ist ein zusammenhängender Graph mit höchstens einem Kreis und einem Knoten weniger als G.

Damit wird nun auch v korrekt gefärbt, denn ist er ein Blatt, so hat er nur einen Nachbarn, und es ist offensichtlich noch mindestens eine Farbe in seiner Farbliste. Ist er jedoch ein Kreisknoten vom Grad zwei, so war G \ v ein Baum und wurde nach Induktionsvoraussetzung mit zwei Farben gefärbt. Somit wird v, wenn der Kreis, den er schließt, gerade Länge hat, offenbar zwischen zwei gleich gefärbten Knoten eines Pfades ungerader Länge liegen und demzufolge noch die zweite Farbe in seiner Liste haben, während bei ungerader Länge in jedem Fall eine dritte Farbe vonnöten ist, die sich in der Liste von v, da er nur zwei Nachbarn hat, definitiv noch findet.

Proposition 7. Sei p = \frac{c}{n} mit c < 1. Dann hat fast sicher jede Komponente des G_{n,p} höchstens einen Kreis.

Beweis. Zuerst wird gezeigt, dass G_{n,p} fast sicher keinen Kreis hat, der mehr als konstant viele Knoten enthält.

Die Wahrscheinlichkeit, dass auf i ausgewählten Knoten ein Kreis vorhanden ist, ist gerade \frac{i!}{2i·p^{i}}, denn die Knoten können beliebig angeordnet werden, wobei allerdings bei Permutation (aufgrund der Wahl des Startknoten und der Orientierung) jeder Kreis 2i-mal gezählt wird. Des weiteren müssen i Kanten vorhanden sein. Die Wahrscheinlichkeit für die Existenz eines Kreises der Länge i, wird im folgenden mit Hilfe der Markowschen Ungleichung (Lemma 5) abgeschätzt:

ℙ [C_{i} ⊆ G_{n,p}] ≤ 𝔼 [#C_{i}] = \binom{n}{i}\frac{i!}{2i}p^{i} ≤ \frac{n!}{(n − i)! 2i}(\frac{1}{n})^{i} ≤ \frac{n^{i}}{n^{i}2i} = \frac{1}{2i},

was für jedes wachsende i gegen 0 strebt.

Der Rest des Beweis wird indirekt geführt. Angenommen G_{n,p} hat eine Komponente, die zwei Kreise (konstanter Größe) enthält. Dann sind zwei Fälle möglich:

1. Die beiden Kreise berühren, bzw. überschneiden sich oder sind durch einen Pfad konstanter (das heißt, nicht mit wachsender Knotenzahl steigender) Länge verbunden. Damit bilden die beiden Kreise (zusammen mit dem eventuell verbindenden Pfad) einen balancierten Subgraph H ⊂ G_{n,p} konstanter Größe mit der Dichte d_{H} = \frac{|E(H)|}{|V (H)|} > 1. Da die Schwellenwertfunktion für das Enthaltensein eines balancierten Subgraphen (konstanter Größe) der Dichte d gerade t = n^{− \frac{1}{d}}, ist offensichtlich p ≪ t und H somit fast sicher nicht in G_{n,p} enthalten.

2. Die beiden Kreise sind durch einen Pfad wachsender Länge verbunden. Damit müsste es einen Subgraph H geben, der aus einem wachsenden Pfad mit einem Kreis konstanter Länge am Ende besteht. Die Wahrscheinlichkeit für einen solchen (bei Pfadlänge l und Kreislänge i) lässt sich wieder (Lemma 5) abschätzen:

ℙ [H ⊆ G_{n,p}] ≤ 𝔼 [#H] = \binom{n}{i}\frac{i!}{2}p^{i}\binom{n − i}{l}l! p^{l}

= \frac{n! (n − i)!}{2(n − i)! (n − i − l)!}p^{i+l}

= \frac{n!}{2(n − i − l)!}(\frac{c}{n})^{i+l}

≤ \frac{n^{i+l}}{2} (\frac{c}{n})^{i+l}

= \frac{c^{i+l}}{2}

was wegen c < 1 für jedes wachsende l gegen 0 strebt.

Um eine untere Schranke für c_{3} zu finden, genügt es im Prinzip, für ein beliebig (aber fest) gewähltes c zu zeigen, dass G_{n,p} mit p = \frac{c}{n} noch dreifärbbar ist. Die beiden obigen Propositionen sollen lediglich motivieren, warum im folgenden immer c > 1 angenommmen werden wird.

2.2 Die erwartete Anzahl der Knoten mit i Farben ”Vorrat“

Der Algorithmus ist gerade am Zeitpunkt t, wenn er im (t+1)sten Schleifendurchlauf ist, das heißt, wenn gerade der (t + 1)ste Knoten gefärbt wird. Mit dieser Bezeichnung ist also zum Beispiel L_{v} (die Menge der vorrätigen Farben für den Knoten v) eine Funktion von t.

Definition 8. Für 0 ≤ i ≤ 3, 0 ≤ t ≤ n und l ⊆ {1, 2, 3} mit |l| = i seien:

S_{i}(t) := {v ∈ V : |L_{v}(t)| = i}  (die Menge der Knoten mit i Farben zum Zeitpunkt t),
S_{i}^{l}(t) := {v ∈ S_{i}(t) : L_{v}(t) = l}  (die Menge der Knoten mit Farbliste l zum Zeitpunkt t),
U_{i}(t) := ⋃_{j=0}^{i} S_{j}(t)  (die Menge der Knoten mit höchstens i Farben zum Zeitpunkt t),
ΔS_{i}(t) := |S_{i}(t + 1)| − |S_{i}(t)|,
ΔU_{i}(t) := |U_{i}(t + 1)| − |U_{i}(t)|,
I_{i}(t) := 𝔼 [Anzahl von Knoten, die sich von S_{i+1}(t) nach S_{i}(t + 1) bewegen].

Lemma 9.

I_{2}(t) = \frac{c}{n}|S_{3}(t)|.  (1)

Beweis. Der Beweis benutzt die sogenannte ”Methode der verzögerten Entscheidungen“. Das heißt, man tut so, als wäre der (zufällige) Graph nicht in seiner Gesamtheit schon zu Beginn des Algorithmus gegeben, sondern das Auswürfeln einer Kante findet erst statt, sobald der Algorithmus diese Kante verfolgen möchte. Nach der Definition des Algorithmus ist dann klar, dass in jedem Schritt genau die zu dem zu färbenden Knoten inzidenten Kanten ausgewürfelt werden, die nicht zu schon gefärbten Knoten führen. Sei der zu färbende Knoten v. Da die Kanten von v in die Menge der nicht gefärbten Knoten jetzt erst ermittelt werden, ist die Wahrscheinlichkeit für jede Kante v offenbar gerade \frac{c}{n}. Demzufolge ist die erwartete Zahl der Nachbarn von v in S_{3} genau \frac{c}{n}|S_{3}(t)|. Da allen diesen Knoten jetzt eine Farbe aus ihrer Vorratsliste gestrichen wird (eben die Farbe mit der v gefärbt wird), werden sie alle im nächsten Schritt in S_{2} sein. Das aber ist genau die Aussage des Lemmas.

Aus Lemma 9 lässt sich nun einfach die erwartete Änderung von |U_{2}(t)|, das heißt ΔU_{2}(t), bestimmen. Denn solange U_{2} nicht leer ist, wird nach Definition des Algorithmus immer genau ein Knoten aus U_{2} entnommen, da ein Knoten mit minimaler Farbliste definitiv in U_{2} ist. Die Knoten, die nach U_{2} hineingehen, sind aber genau die, die von S_{3} nach S_{2} gehen,was bedeutet:

𝔼 [ΔU_{2}(t)] = \frac{c}{n}|S_{3}(t)| − 1  für U_{2}(t) ≠ ∅.  (2)

Genauso lässt sich für die erwartete Änderung von S_{3} schlussfolgern, denn falls U_{2} nicht leer ist, wird diese Änderung nur durch die erwartete Anzahl von Knoten nach Lemma 9 bestimmt, während sonst noch ein weiterer Knoten entfernt wird:

𝔼 [ΔS_{3}(t)] = −\frac{c}{n}|S_{3}(t)|  für U_{2}(t) ≠ ∅.  (3)

Wegen des eventuell zusätzlich entfernten Knotens gilt aber immer folgende Ungleichung:

𝔼 [ΔS_{3}(t)] ≥ −\frac{c}{n}|S_{3}(t)| − 1.  (3’)

Nachdem nun die erwartete Anzahl sich bewegender Knoten durch den Grad abgeschätzt werden konnte, soll nun noch eine obere Schranke für diese Zahl beziehungsweise letztendlich eher eine obere Schranke für den Grad angegeben werden.

Lemma 10. Die Wahrscheinlichkeit, dass der Maximalgrad des G_{n,p} für p = \frac{c}{n} größer als ln n ist, strebt schneller als n^{−3} gegen 0, oder formal:

ℙ [∃v ∈ V : |Γ(v)| ≥ ln n] = o(n^{−3}).

Beweis. Man kann sich vorstellen, dass der Grad eines Knotens bestimmt wird durch n − 1 unabhängige Zufallsentscheidungen über die Existenz von Kanten zu seinen Nachbarn. Damit lässt sich zur Abschätzung des Grades eines festen Knotens v die Tschernowsche Ungleichung (Lemma 5) verwenden, wobei der Erwartungswert für den Grad offenbar c\frac{n−1}{n} ≤ c ist.

ℙ [|Γ(v)| ≥ ln n] ≤ (\frac{ec}{ln n})^{ln n}

Die Wahrscheinlichkeit, dass überhaupt ein Knoten solch hohen Grad hat, ist nach oben beschränkt durch die Summe der Wahrscheinlichkeiten über alle Knoten, also gilt:

ℙ [∃v ∈ V : |Γ(v)| ≥ ln n] ≤ n(\frac{ec}{ln n})^{ln n} = \frac{n^{2}c^{ln n}}{(ln n)^{ln n}} = \frac{n^{2+ln c}}{n^{ln ln n}} = n^{2+ln c−ln ln n} = o(n^{−3}).

2.3 Fast immer wird fast alles gut

Zu Beginn dieses Abschnitts wird ein Lemma bewiesen, welches einen anschaulichen Zusammenhang zwischen I_{i} und U_{i} formalisiert. Ist nämlich U_{i} zu einem bestimmten Zeitpunkt t_{0} im Laufe des Algorithmus leer und ist zu diesem und späteren Zeitpunkten I_{i} < 1, so wird wahrscheinlich nie ein Knoten nach U_{i−1} kommen, denn es wird (im Erwartungswert) immer nur höchstens ein Knoten nach U_{i} hineinkommen, der dann aber sofort wieder gefärbt und damit entfernt wird. Mit noch größerer Wahrscheinlichkeit gilt das natürlich für U_{i−2}.

Lemma 11. Seien t_{0} ≥ 0 und 1 ≥ δ > 0 so dass I_{i}(t) < 1 − δ für t ≥ t_{0}. Falls U_{i}(t_{0}) = ∅, so gibt es ein ρ > 0 (unabhängig von n), so dass

mit Wahrscheinlichkeit ρ ⋃_{t≥t_{0}} U_{i−1}(t) = ∅ und fast sicher ⋃_{t≥t_{0}} U_{i−2}(t) = ∅ gilt.

Beweis. Setzt man wieder voraus, dass die Nachbarn eines Knotens in die Menge der noch nicht gefärbten Knoten erst ermittelt werden, wenn der Knoten gefärbt wird, so sieht man, dass der Grad eines Knotens als Summe einer festen Zahl unabhängiger Einzelentscheidungen mit Erfolgswahrscheinlichkeit p eine binomial- und damit asymptotisch eine poissonverteilte Zufallsvariable ist. Da sich die nicht gefärbten Knoten auf die Mengen S_{i} mit i > 0 verteilen, folgt daraus, dass die Anzahl der Knoten, die sich von S_{i+1} nach S_{i} bewegen, asymptotisch poissonverteilt mit Erwartungswert I_{i} ist.

Sei nun Z(t) definiert durch Z(t_{0}) = 0 und Z(t + 1) = max{0, Z(t) + Po(1 − δ) − 1}, wobei Po(1 − δ) eine poissonverteilte Zufallsvariable mit Erwartungswert 1 − δ bezeichnet. Offenbar gilt jetzt für alle natürlichen Zahlen m: ℙ [Z(t) > m] ≥ ℙ [U_{i}(t) > m].

Achlioptas und Molloy [2] legen in ihrem Artikel dar, dass sich aus diesen Fakten folgern lässt, dass fast sicher ∑_{t≥t_{0}} |U_{i}(t)| < kn.

Da für jeden Knoten die Wahrscheinlichkeit, dass er nach U_{i−1} weitergereicht wird höchstens \frac{c}{n} ist, lässt sich die Wahrscheinlichkeit ρ, dass kein Knoten nach U_{i−1} kommt, abschätzen durch ρ ≥ (1 − \frac{c}{n})^{kn} ⟶^{n→∞} e^{−ck}. Damit ist der erste Teil des Lemmas bewiesen.

Da ∑_{t≥t_{0}} |U_{i}(t)| < kn und jeder Knoten nur mit Wahrscheinlichkeit \frac{c}{n} weitergereicht wird, gilt ∑_{t≥t_{0}} |U_{i−1}(t)| < k′. Damit entspricht die Wahrscheinlichkeit, dass ⋃_{t≥t_{0}} U_{i−1} zwei adjazente Knoten enthält, gerade der Wahrscheinlichkeit, dass unter einer festen Anzahl von Knoten zwei adjazente zu finden sind. Der Erwartungswert für die Anzahl der Kanten bei k′ Knoten ist offenbar gerade \binom{k′}{2}p = \binom{k′}{2} \frac{c}{n} ⟶^{n→∞} 0. Damit ist gezeigt, dass ⋃_{t≥t_{0}} U_{i−1} fast sicher keine zwei adjazenten Knoten enthält, woraus unmittelbar folgt, dass ⋃_{t≥t_{0}} U_{i−2} = ∅.

Das Problem mit den Gleichungen (2) und (3) ist, dass sie nur gelten, wenn U_{2}(t) nicht leer ist. Es ist also nötig zu zeigen, dass dies über verhältnismäßig lange Zeiträume im Laufe des Algorithmus’ der Fall ist, denn mit der Gültigkeit dieser Gleichungen wird es möglich sein, den Verlauf von U_{2}(t) abzuschätzen.

Lemma 12. Es gibt ein ε = ε(c) > 0, so dass fast sicher für alle t mit ln^{2} n ≤ t ≤ εn gilt: U_{2}(t) ≠ ∅.

Beweis. Alon und Spencer zeigen in ihrem Buch [4], dass für p = \frac{c}{n} mit c > 1 ein G_{n,p} fast sicher genau eine Komponente der Größe kn für ein nur von c abhängendes k hat, während die zweitgrößte Komponente nur noch O(ln n) Knoten umfasst.

Da die Nachbarn eines bereits gefärbten Knoten (sofern sie nicht selbst schon gefärbt wurden) immer in U_{2} zu finden sind und zu färbende nur dort entnommen werden, kann U_{2} nur leer werden, wenn eine Komponente vollständig gefärbt wurde. Also ist die Aussage des Lemmas gezeigt, wenn man (die stärkere Aussage) beweist, dass bei ln n zufälligen Wahlen eines Knotens aus einer Menge der Mächtigkeit n fast sicher ein Knoten aus einer festen Teilmenge der Größe kn gewählt wurde, da man dann in der größten Komponente ist und diese erst vollständig gefärbt werden muss, bevor U_{2} wieder leer werden kann.

Dabei entspricht die zufällige Wahl hier der Wahl eines Knotens aus S_{3} bei leerem U_{2}, denn es muss mindestens ln n mal aus S_{3} gewählt werden, um nach mehr als ln^{2} n Schritten noch ein leeres U_{2} zu erhalten, da die kleineren Komponenten maximal ln n Knoten enthalten.

Die Wahrscheinlichkeit, dass man einmal daneben ”tippt“, liegt offenbar bei 1 − k und dass einem das bei ln n unabhängigen Versuchen passiert bei (1 − k)^{ln n} ⟶^{n→∞} 0.

Definition 13. Sei im folgenden t_{2}^{∅} das kleinste t > εn, so dass U_{2}(t) = ∅.

2.4 Der Satz von Wormald

Aus Lemma 12 und den Gleichungen (2) und (3) folgt, dass für ln^{2} n ≤ t ≤ t_{2}^{∅} gilt:

𝔼 [ΔS_{3}(t)] = −\frac{c}{n}|S_{3}(t)| und

𝔼 [ΔU_{2}(t)] = \frac{c}{n}|S_{3}(t)| − 1.

Der folgende Satz (eine leichte Abwandlung des Hauptsatzes aus dem Artikel von Nicholas Wormald [11]) sagt, dass sich diese Gleichungen als Differentialgleichungen für |S_{3}(t)| und |U_{2}(t)| interpretieren lassen, deren Lösung tatsächlich als Näherung für den Verlauf von |S_{3}(t)| und |U_{2}(t)| verstanden werden kann.

Satz 14. Sei a eine feste natürliche Zahl und für 1 ≤ l ≤ a seien mit Y_{l}(t) Zufallsvariablen bezeichnet, die den Ergebnissen einer Sequenz von t ≤ n Zufallsexperimenten eine reelle Zahl zuordnen, so dass für eine Konstante C und alle l sowie alle Sequenzen von Experimenten gilt: Y_{l}(t) < Cn. Seien weiterhin f_{l} (a + 1)-stellige, reellwertige Funktionen. Gelte weiterhin für eine Funktion m = m(n):

(i) Es gibt Funktionen ω = ω(n) und λ = λ(n) mit λ^{4} ln n < ω < n^{2/3}/λ und λ → ∞ für n → ∞, so dass für alle l, alle t < m und alle Sequenzen von Zufallsexperimenten gilt:

ℙ [|Y_{l}(t + 1) − Y_{l}(t)| > \frac{\sqrt{ω}}{λ^{2}\sqrt{ln n}}] = o(n^{−3}).  (4)

(ii) Für alle l, alle t < m und alle Sequenzen von Zufallsexperimenten gilt:

𝔼 [|Y_{l}(t + 1) − Y_{l}(t)|] = f_{l}(t/n, Y_{1}(t)/n, …, Y_{a}(t)/n) + o(1).

(iii) Es existiert eine reelle Zahl L, so dass für alle f_{l} und alle reellen r_{1}, …, r_{a+1}, s_{1}, …, s_{a+1} gilt:

|f_{l}(r_{1}, …, r_{a+1}) − f_{l}(s_{1}, …, s_{a+1})| ≤ L ∑_{i=1}^{a+1} |r_{i} − s_{i}|  (Lipschitz-Stetigkeit).

Dann gilt folgendes:

(a) Das Differentialgleichungssystem

\frac{dz_{l}}{ds} = f_{l}(s, z_{1}, …, z_{a}), l = 1, …, a,

hat eine eindeutige Lösung für z_{l}(0) = ẑ_{l}.

(b) Für alle l und t < m gilt fast sicher:

Y_{l}(t) = nz_{l}(\frac{t}{n}) + o(n),

mit den z_{l} wie oben und ẑ_{l} = Y_{l}(0)/n.

Dieser Satz soll nun auf das vorliegende Problem angewandt werden

Proposition 15. Für 0 ≤ t ≤ t_{2}^{∅} gilt fast sicher

|S_{3}(t)| = ne^{−c \frac{t}{n}} + o(n)
|U_{2}(t)| = n − t − ne^{−c \frac{t}{n}} + o(n).

Beweis. Es wird Y_{1}(t) := S_{3}(t + ln^{2}(n)) und Y_{2}(t) := U_{2}(t + ln^{2}(n)) gesetzt, da nach Lemma 12 die Gültigkeit der Erwartungswertgleichungen (2) und (3) erst ab t = ln^{2}(n) gesichert ist. Dann sind

f_{1}(t/n, Y_{1}(t)/n, Y_{2}(t)/n) = −cY_{1}(t)/n und
f_{2}(t/n, Y_{1}(t)/n, Y_{2}(t)/n) = cY_{1}(t)/n − 1.

Mit diesen Gleichungen sind die zweite Bedingung (siehe (2) und (3)) und die dritte Bedingung (die Funktionen sind aufgrund ihrer Linearität Lipschitz-stetig) sicher erfüllt. Es bleibt zu zeigen, dass auch die erste Bedingung erfüllt ist. Man setze λ(n) := ln^{1/4} n und ω(n) := ln^{4} n, womit

λ^{4} ln n < ω < n^{2/3}/λ ⇔ ln^{2} n < ln^{4} n < n^{2/3}/ ln^{1/4} n

und λ ⟶^{n→∞} ∞ gelten. Desweiteren gilt

\frac{\sqrt{ω}}{λ^{2}\sqrt{ln n}} = \frac{\sqrt{ln^{4} n}}{ln^{1/2} n\sqrt{ln n}} = \frac{ln^{2} n}{\sqrt{ln^{2} n}} = ln n.

Damit sind folgende Aussagen zu zeigen:

ℙ [|ΔS_{3}(t)| > ln n] = o(n^{−3})
ℙ [|ΔU_{2}(t)| > ln n] = o(n^{−3})

Offensichtlich sind |ΔS_{3}(t)| und |ΔU_{2}(t)| immer kleiner als der Maximalgrad im zu färbenden Graphen, da sich in jedem Schritt höchstens alle Nachbarn des zu färbenden Knoten von S_{3} nach U_{2} bewegen könnten (die Farblisten aller anderen bleiben unbeeinflusst). Damit folgen die beiden Aussagen unmittelbar aus Lemma 10.

Damit ist es möglich, die Aussage des Satzes anzuwenden, und man erhält folgendes Differentialgleichungssystem, wobei s_{3} := z_{1} und u_{2} := z_{2}:

s′_{3}(x) = −cs_{3}(x),  s_{3}(0) = 1 − o(1);
u′_{2}(x) = cs_{3}(x) − 1,  u_{2}(0) = o(1),

deren einzige Lösung gerade s_{3}(x) = e^{−cx} + o(1) und u_{2}(x) = 1 − x − e^{−cx} + o(1) ist.

Um die Proposition vollständig zu beweisen, muss noch nachgewiesen werden, dass die Beschränkung auf t > ln^{2} n letztendlich unnötig war. Da bereits bekannt ist, dass sich die Größe von S_{3} und U_{2} in jedem Schritt um maximal den Grad eines Knotens ändert und Lemma 10 diesen Grad fast sicher durch ln n beschränkt, unterscheiden sich S_{3}(0) und S_{3}(ln^{2} n) (bzw. U_{2}(0) und U_{2}(ln^{2} n)) in ihrer Größe um höchstens ln^{3} n = o(n). Eine höhere Genauigkeit wird aber auch nicht angestrebt. Damit ist die Behauptung der Proposition bewiesen.

Proposition 16. Für beliebige l_{1}, l_{2} ∈ {{1, 2}, {2, 3}, {1, 3}} gilt:

|S_{2}^{l_{1}} | − |S_{2}^{l_{2}} | = o(n).

Beweis. Die im vorherigen Beweis benutzten Differentialgleichungen lassen sich auch für die Zufallsvariablen S_{2}^{l_{i}} formulieren. Da diese Gleichungen dann offensichtlich symmetrisch in l_{1} und l_{2} sind und auch die Anfangsbedingungen gleich sind, wird sich auch ihre Lösung nicht unterscheiden. Da der Satz von Wormald aber nur eine Genauigkeit bis auf o(n) hergibt, muss diese Differenz wohl zugestanden werden.

2.5 Der schlussendliche Beweis

Lemma 17. Fast sicher wird nach dem Zeitpunkt t_{2}^{∅} nicht mehr ”Fehlschlag“ ausgegeben.

Beweis. Aus Gleichung (1) ist bekannt, dass I_{2}(0) = c > 1, denn S_{3}(0) = n. Desweiteren ist (auch wegen (1)) I_{2}(n) = 0 und I_{2}(t) ist monoton fallend mit wachsendem t, denn S_{3} wird ja immer kleiner. Sei t^{∗} das kleinste t (der früheste Zeitpunkt) zu dem I_{2}(t) < 1 wird. Es wird zunächst gezeigt, dass es ein ε > 0 gibt, so dass fast sicher t^{∗} > εn. Damit I_{2} klein wird, muss S_{3} klein werden, genauer für I_{2}(t) = \frac{c}{n}|S_{3}(t)| < 1, muss |S_{3}(t)| < \frac{n}{c} gelten.

Aus der Ungleichung (3’) ist bekannt, wie stark sich S_{3}(t) pro Schritt (im Erwartungswert) höchstens verkleinert, nämlich: 𝔼 [ΔS_{3}(t)] ≥ −\frac{c}{n}|S_{3}(t)| − 1 ≥ −c − 1. Nun lässt sich die Wahrscheinlichkeit bestimmen, dass S_{3}(t) schon vor dem Zeitpunkt εn zu klein ist, d.h., dass schon in den ersten Schritten zu viel heraus genommen wurde (Es wird mit −ΔS_{3}(t) gerechnet, da dies eine nicht negative Zufallsvariable ist und nur damit Lemma 5 angewendet werden kann):

ℙ [∑_{t=0}^{t^{∗}} −ΔS_{3}(t) ≥ n − \frac{n}{c}] ≤ \frac{1}{n − \frac{n}{c}} 𝔼 [∑_{t=0}^{t^{∗}} −ΔS_{3}(t)]  (Markow)

= \frac{c}{n(c − 1)} ∑_{t=0}^{t^{∗}} 𝔼 [−ΔS_{3}(t)]  (Linearität)

≤ \frac{c}{n(c − 1)} ∑_{t=0}^{t^{∗}} c + 1  (Abschätzung für ΔS_{3}(t))

= \frac{(t^{∗} + 1)c(c + 1)}{n(c − 1)},

was für t^{∗} = o(n) gegen 0 strebt. Also hat man vor einem Zeitpunkt t = εn fast sicher noch nicht genügend Knoten aus S_{3} entfernt, um I_{2} unter 1 zu drücken also gilt t^{∗} > εn.

Außerdem muss t^{∗} < n − \frac{n}{c} gelten, denn zu jedem späteren Zeitpunkt wurden bereits n − \frac{n}{c} Knoten gefärbt und stehen somit definitiv nicht mehr als Elemente für S_{3} zur Verfügung. Also gibt es ein k mit 0 < k < 1 − \frac{1}{c}, so dass t^{∗} ∼ kn. Aus der in Proposition 15 für |U_{2}(t)| hergeleiteten Funktion, folgt nun:

|U_{2}(t^{∗})| = n − t^{∗} − ne^{−c \frac{t^{∗}}{n}} + o(n)
= n − kn − ne^{−c \frac{kn}{n}} + o(n)
= n(1 − k − e^{−ck} + o(1))
≥ k′n  für ein festes k′ > 0.

Da in jedem Schritt nach t^{∗} höchstens ein Knoten aus U_{2} entnommen werden kann, dauert es noch mindestens k′n Schritte bis U_{2} leer ist, was dem Zeitpunkt t_{2}^{∅} entspricht, kurz: t_{2}^{∅} > t^{∗} + k′n. Zur Veranschaulichung des Ablaufs jetzt eine kleine Skizze zum Verhalten von I_{2} und U_{2}, die auch unser noch zu zeigendes Ergebnis (bezüglich U_{0}) für t > t_{2}^{∅} beinhaltet.

0  I_{2} ≥ 1 ln_{2} n  U_{2} ≠ ∅ I_{2} ≥ 1  t^{∗}  U_{2} ≠ ∅ I_{2} < 1  t_{2}^{∅}  U^{0} = ∅ I_{2} < 1 − δ  n

Aus der in Proposition 15 für |S_{3}(t)| hergeleiteten Funktion, folgt mit (1):

I_{2}(t_{2}^{∅}) − I_{2}(t^{∗}) =^{(1)} \frac{c}{n}(ne^{−c \frac{t^{∗}}{n}} + o(n) − ne^{−c \frac{t^{∅}_{2}}{n}} − o(n))
= ce^{−c \frac{t^{∗}}{n}} − ce^{−c \frac{t^{∅}_{2}}{n}} + o(1)
≥ ce^{−ck} − ce^{−c} + o(1)  wegen t^{∗} ∼ kn und t_{2}^{∅} ≤ n
≥ δ  für ein festes δ > 0.

Damit gilt I_{2}(t_{2}^{∅}) < 1−δ. Da I_{2}(t) fallend ist, kann man Lemma 11 mit i = 2 und t_{0} = t_{2}^{∅} anwenden und erhält, dass U_{0}(t) nach dem Zeitpunkt t_{2}^{∅} fast sicher keinen Knoten mehr enthalten wird, womit das Lemma bewiesen ist.

Im Hinblick auf Lemma 11 ist es jetzt das Ziel zu zeigen, dass es Werte von c gibt, so dass fast sicher I_{1}(t) < 1 − ε für irgendein ε > 0 und alle 0 < t < n. Denn dann ließe sich mit Hilfe des ersten Teils von Lemma 11 folgern, dass mit positiver Wahrscheinlichkeit U_{0}(t) = ∅ für alle t und damit der Algorithmus erfolgreich ist.

Aufgrund von Proposition 16 lässt sich nun ähnlich wie in Lemma 9 I_{1}(t) bestimmen

Lemma 18.

I_{1}(t) = \frac{2c}{3n}|S_{2}(t)| + o(1)

Beweis. Der Beweis verläuft analog zum Beweis von Lemma 9.

Sei der zu färbende Knoten v. Die erwartete Zahl der Nachbarn von v in jeder der S_{2}^{l} ist genau \frac{c}{n} |S_{2}^{l}(t)|. Da aber nur in zwei der drei möglichen l die Farbe, mit der v gefärbt wurde, vorkommt, gilt:

I_{1}(t) = \frac{c}{n} (|S_{2}^{l_{1}}(t)| + |S_{2}^{l_{2}}(t)|)
= \frac{c}{n} (\frac{1}{3}|S_{2}(t)| + o(n) + \frac{1}{3}|S_{2}(t)| + o(n))  (Lemma 16)

= \frac{2c}{3n} (|S_{2}(t)| + o(n)) = \frac{2c}{3n}|S_{2}(t)| + o(1)

Es wird nun versucht, eine obere Schranke für |S_{2}(t)| zu ermitteln, da sich aus dieser (aufgrund des letzten Lemmas) eine obere Schranke für I_{2}(t) und somit eine Bedingung im gewünschten Sinne ableiten ließe. Da |S_{2}(t)| ≤ |U_{2}(t)|, wird das Maximum der für |U_{2}(t)| ermittelten Funktion als obere Schranke für |S_{2}(t)| angenommen. Da diese Funktion nur für t ≤ t_{2}^{∅} gilt, kann auch die Schranke nur für diesen Bereich bewiesen werden. Nach Proposition 15 weiß man, dass für t ≤ t_{2}^{∅}:

|U_{2}(t)| = n − t − ne^{−c \frac{t}{n}} + o(n)  und damit
|U_{2}(t)|′ = −1 + ce^{−c \frac{t}{n}}  und
|U_{2}(t)|′′ = −\frac{c^{2}}{n} e^{−c \frac{t}{n}} .

Da die zweite Ableitung für alle t negativ ist, sind alle Extremstellen Maximumstellen. Um diese zu bestimmen, werden die Nullstellen t_{m} der ersten Ableitung ermittelt.

0 = −1 + ce^{−c \frac{tm}{n}} ⇔ \frac{1}{c} = e^{−c \frac{tm}{n}} ⇔ ln \frac{1}{c} = −c\frac{t_{m}}{n} ⇔ t_{m} = n\frac{ln c}{c}

Damit gilt:

max_{0≤t≤t_{2}^{∅}} |U_{2}(t)| = n − t_{m} − ne^{−c \frac{tm}{n}} + o(n)

= n − n\frac{ln c}{c} − ne^{−c \frac{n \frac{ln c}{c}}{n}} + o(n)

= n − n\frac{ln c}{c} − ne^{− ln c} + o(n)

= n (1 − \frac{1 + ln c}{c}) + o(n).

Also gilt für t ≤ t_{2}^{∅}:

I_{1}(t) ≤ \frac{2c}{3n}|U_{2}(t)| + o(1)

≤ \frac{2c}{3n} max_{0≤t≤t_{2}^{∅}} |U_{2}(t)| + o(1)

= \frac{2c}{3n} (n (1 − \frac{1 + ln c}{c}) + o(n)) + o(1)

= \frac{2c}{3} (1 − \frac{1 + ln c}{c}) + o(1)

= \frac{2c}{3} − \frac{2 + 2 ln c}{3} + o(1)

Das heißt für I_{1}(t) < 1 − ε ist ausreichend:

\frac{2c}{3} − \frac{2 + 2 ln c}{3} < 1 − ε

c − 1 − ln c < \frac{3}{2} − \frac{3}{2}ε

c − ln c < \frac{5}{2} − \frac{3}{2}ε

Numerisches Lösen der zugehörigen Gleichung zeigt, dass diese Ungleichung für c < 3.847396 … gilt.

Satz 19. Ein Graph auf n Knoten mit höchstens 1, 923n zufällig verteilten Kanten ist fast sicher mit drei Farben färbbar.

Beweis. Mit obiger Ungleichung wurde gezeigt, dass für c < 3.847 fast sicher I_{1}(t) < 1 − δ für t < t_{2}^{∅} und irgendein δ > 0. Wendet man nun Lemma 11 mit t_{0} = 0 an, so ergibt sich, dass mit Wahrscheinlichkeit ρ > 0 U_{0}(t) = ∅ für alle 0 ≤ t ≤ t_{2}^{∅}. Dies bedeutet, dass der Algorithmus in diesem Zeitraum keinem ungefärbten Knoten eine leere Farbliste beschert, also erfolgreich arbeitet. Zusammen mit Lemma 17 und Proposition 3 folgt daraus dass der Algorithmus fast sicher einen gegebenen G_{n,p} mit p ≤ \frac{3.847}{n} mit drei Farben färbt.

Bollobas zeigt in seinem Buch [5], dass sich für konvexe Grapheneigenschaften (A heißt konvex, falls für F ∈ A, H ∈ A und F ⊂ G ⊂ H auch immer G ∈ A), ein Graph mit \frac{cn}{2} zufällig verteilten Kanten genauso verhält wie ein G_{n,p} mit p = \frac{c}{n}.

Die erwartete Anzahl Kanten in dem betrachteten Graph ist nun gerade:

𝔼 [|E(G_{n,p})|] = \binom{n}{2}p ≤ \frac{n^{2}}{2} \frac{3.847}{n} ≤ 1.923n,

womit (zusammen mit der leicht einzusehenden Konvexität der (Nicht-)Dreifärbbarkeit) die Aussage des Satzes gezeigt ist.

Literatur

[1] Dimitris Achlioptas and Ehud Friedgut. A sharp threshold for k-colorability. Random Structures & Algorithms, 14:63–70, 1999.

[2] Dimitris Achlioptas and Michael Molloy. The analysis of a list-coloring algorithm on a random graph. 38th Annual Symposium on the Foundations of Computer Science, pages 204–212, 1997.

[3] Dimitris Achlioptas and Michael Molloy. Almost all graphs with 2.522n edges are not 3colorable. The Electronic Journal of Combinatorics, 6, 1999.

[4] Noga Alon and Joel H. Spencer. The Probabilistic Method. John Wiley & Sons, New York, 1992.

[5] Béla Bollobás. Modern Graph Theory. Springer, New York, 1998.

[6] Paul Erdős and Alfred Rényi. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 15:17–61, 1960.

[7] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random Graphs. John Wiley & Sons, New York, 2000.

[8] Alexis C. Kaporis, Lefteris M. Kirousis, and Yannis C. Stamatiou. A note on the noncolorability threshold of a random graph. The Electronic Journal of Combinatorics, 7, 2000.

[9] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

[10] Hans Jürgen Prömel et al. Einführung in Graphen und Algorithmen. Online-Skriptum, 1996.

[11] Nicholas C. Wormald. Differential equations method for random processes and random graphs. Annals of Applied Probability, 5:1217–1235, 1995.

[12] Nicholas C. Wormald. The differential equation method for random graph processes and greedy algorithms. In Michał Karoński and Hans Jürgen Prömel, editors, Lectures on Approximation and Randomized Algorithms, pages 73–155, 1999.