Lovász Local Lemma

Das Lovász-Local-Lemma ist ein Hilfssatz aus der Wahrscheinlichkeitstheorie. Es verallgemeinert das Argument, dass die stochastische Unabhängigkeit von Ereignissen mit positiver Ausfallwahrscheinlichkeit eine positive Wahrscheinlichkeit für den Ausfall aller Ereignisse impliziert, auf Situationen, in denen nicht alle Ereignisse unabhängig sind. Sein Name beruht darauf, dass es lokale Eigenschaften zu einem globalen Ergebnis zusammensetzt. Es findet am häufigsten Anwendung in probabilistischen Ansätzen, um Existenzbeweise zu führen. 1975 wurde es von László Lovász und Paul Erdős bewiesen.

Aussage des Lemmas

Allgemeine Version

Sei $\mathcal{E} = \{A_1, A_2, \dots, A_n\}$ eine Menge von Ereignissen über einem beliebigen Wahrscheinlichkeitsraum, so dass jedes Ereignis A_i stochastisch unabhängig von allen anderen bis auf $\mathcal{E} \setminus (A_i \cup D_i)$ für jeweils ein $\mathcal{D}_i \subseteq \mathcal{E}$ ist.

Falls reelle Zahlen $x_1, x_2, \dots, x_n \in [0,1)$ existieren, so dass für alle $i \in \{1,2,\dots,n\}$ gilt:

$Pr(A_i) \le x_i \prod_{A_k \in \mathcal{D}_i} (1-x_k)$,

so folgt: $Pr(\bigcap_{i=1}^{n} \overline{A}_i) \ge \prod_{j=1}^{n} (1-x_j) > 0$.

In vielen Beweisen wird der folgende symmetrische Spezialfall verwendet.

Symmetrische Version

Sei $\mathcal{E} = \{A_1, A_2, \dots, A_n\}$ eine Menge von Ereignissen über einem beliebigen Wahrscheinlichkeitsraum, so dass jedes Ereignis aus $\mathcal{E}$ von höchstens d anderen Ereignissen stochastisch abhängig ist.

Falls

1. $\forall i \in \{1,2,\dots,n\} : Pr(A_i) \le p$, wobei $p \in [0,1]$,
2. $e\cdot p \cdot (d+1) \le 1$,

so folgt $Pr(\bigcap_{i=1}^{n} \overline{A}_i) > 0$.

Anwendungsbeispiel

Sei $\mathcal{H}$ ein Hypergraph, so dass jede Hyperkante mindestens k Knoten enthält und sich mit höchstens 2^{k − 3} weiteren Hyperkanten schneidet. Dann ist $\mathcal{H}$ 2-färbbar.

Färbe die Knoten von $\mathcal{H}$ zunächst zufällig, unabhängig und gleichverteilt mit zwei Farben (d.h. die Wahrscheinlichkeit, dass ein Knoten beispielsweise rot oder blau ist, beträgt jeweils $\frac{1}{2}$). Setze $N_e := \{f \in E(\mathcal{H}) | f \cap e \neq \emptyset\}$ für alle Hyperkanten $e \in E(\mathcal{H})$: Wende nun das symmetrische Local-Lemma auf die Menge $\mathcal{E} := \{A_e | e \in E(\mathcal{H})\}$ an: Zunächst ist jedes Ereignis A_e stochastisch abhängig von N_e, da sich jede Kante aus N_e per Definition mindestens einen Knoten mit e teilt. Nach Voraussetzung gilt: $|N_e| \le 2^{k-3} =: d$ für alle Kanten $e \in E(\mathcal{H})$. Andererseits ist jedes Ereignis A_e stochastisch unabhängig von $\{A_f | f \in E(\mathcal{H}), f \cap e = \emptyset\}$, da die Knoten unabhängig voneinander gefärbt wurden. Da $Pr(A_e) \le 2\left(\frac{1}{2}\right)^k = 2^{1-k} =: p$ ist, gilt: $e\cdot p \cdot (d+1) = \frac{e}{4} < 1$. Also ist $Pr\left(\bigcap_{e \in E(\mathcal{H})} \overline{A}_e\right) > 0$, das heißt: $\mathcal{H}$ ist 2-färbbar.

Literatur

• Michael Molloy; Bruce Reed: Graph Colouring and the Probabilistic Method. Springer, 2002, ISBN 3540421394, S. 221-229.