Lovász-Local-Lemma

Das Lovász Local Lemma ist ein Hilfssatz aus der Wahrscheinlichkeitstheorie. Es besagt, dass sofern einige Ereignisse nur zu einem gewissen Grad stochastisch unabhängig voneinander sind, mit einer positiven Wahrscheinlichkeit keines der Ereignisse eintritt. Sein Name beruht auf der Tatsache, dass man aus der Betrachtung lokaler Eigenschaften ein globales Resultat erhält. Es findet am häufigsten Anwendung in probabilistischen Ansätzen, um Existenzbeweise zu führen. Es wurde 1975 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}$ stochatisch 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})\leq x_{i}\prod _{A_{k}\in {\mathcal {D}}_{i}}(1-x_{k})$

so folgt: $Pr(\bigcap _{i=1}^{n}{\overline {A}}_{i})\geq \prod _{j=1}^{n}(1-x_{j})>0$

Da es oftmals schwer ist, das Local Lemma in der allgemeinen Version auf ein Problem anzuwenden, bedient man sich häufig des schwächeren symmetrischen Local Lemmas, welches als Korollar aus dem Lovász Local Lemma hervorgeht und am gebräuchlichsten ist.

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})\leq p$, wobei $p\in [0,1]$
2. $ep(d+1)\leq 1$

so folgt, dass $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 voneinander und gleichmässig mit einer 2-Färbung (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}|\leq 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})\leq 2({\frac {1}{2}})^{k}=2^{-(k-1)}=:p$ ist, gilt: $ep(d+1)={\frac {e}{4}}<1$, also ist $Pr(\bigcap _{e\in E({\mathcal {H}})}{\overline {A}}_{e})>0$, das heisst: ${\mathcal {H}}$ ist 2-färbbar.

Literatur

• Michael Molloy; Bruce Reed: Graph Colouring and the Probabilistic Method. Springer, 2002, ISBN 3-540-42139-4.