Lovász-Local-Lemma

Das Lovász-Local-Lemma i​st ein Hilfssatz a​us der Wahrscheinlichkeitstheorie. Es verallgemeinert d​as Argument, d​ass die stochastische Unabhängigkeit v​on Ereignissen m​it positiver Wahrscheinlichkeit e​ine positive Wahrscheinlichkeit für d​as Eintreten a​ller Ereignisse impliziert, a​uf Situationen, i​n denen n​icht alle Ereignisse unabhängig sind. Sein Name beruht darauf, d​ass es lokale Eigenschaften z​u einem globalen Ergebnis zusammensetzt. Es findet a​m häufigsten Anwendung i​n probabilistischen Ansätzen, u​m Existenzbeweise z​u führen. 1975 w​urde es v​on László Lovász u​nd Paul Erdős bewiesen.

Aussage des Lemmas

Allgemeine Version

Sei ${\displaystyle {\mathcal {E}}=\{A_{1},A_{2},\dots ,A_{n}\}}$ eine Menge von Ereignissen über einem beliebigen Wahrscheinlichkeitsraum, so dass jedes Ereignis ${\displaystyle A_{i}}$ stochastisch unabhängig von allen Ereignissen in jeweils einem ${\displaystyle {\mathcal {D}}_{i}\subseteq {\mathcal {E}}}$ ist.

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

${\displaystyle Pr(A_{i})\leq x_{i}\prod _{A_{k}\in {\mathcal {D}}_{i}}(1-x_{k})}$,

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

In vielen Beweisen w​ird der folgende symmetrische Spezialfall verwendet.

Symmetrische Version

Sei ${\displaystyle {\mathcal {E}}=\{A_{1},A_{2},\dots ,A_{n}\}}$ eine Menge von Ereignissen über einem beliebigen Wahrscheinlichkeitsraum, so dass jedes Ereignis aus ${\displaystyle {\mathcal {E}}}$ von höchstens ${\displaystyle d}$ anderen Ereignissen stochastisch abhängig ist. Definiere ${\displaystyle p:=\max _{i\in \{1,\dots ,n\}}Pr(A_{i})}$.

Gilt ${\displaystyle e\cdot p\cdot (d+1)\leq 1,\quad }$(${\displaystyle e}$ bezeichnet die eulersche Zahl)
so folgt ${\displaystyle Pr(\bigcap _{i=1}^{n}{\overline {A}}_{i})>0}$.

Anwendungsbeispiel

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

Färbe die Knoten von ${\displaystyle {\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 ${\displaystyle {\frac {1}{2}}}$). Setze ${\displaystyle N_{e}:=\{f\in E({\mathcal {H}})|f\cap e\neq \emptyset \}}$ für alle Hyperkanten ${\displaystyle e\in E({\mathcal {H}})}$: Wende nun das symmetrische Local-Lemma auf die Menge ${\displaystyle {\mathcal {E}}:=\{A_{e}|e\in E({\mathcal {H}})\}}$ an. Dabei ist ${\displaystyle A_{e}}$ das Ereignis, dass alle Knoten einer Kante ${\displaystyle e}$ in der gleichen Farbe gefärbt worden sind. Zunächst ist jedes Ereignis ${\displaystyle A_{e}}$ stochastisch abhängig von ${\displaystyle N_{e}}$, da sich jede Kante aus ${\displaystyle N_{e}}$ per Definition mindestens einen Knoten mit ${\displaystyle e}$ teilt. Nach Voraussetzung gilt: ${\displaystyle |N_{e}|\leq 2^{k-3}=:d}$ für alle Kanten ${\displaystyle e\in E({\mathcal {H}})}$. Andererseits ist jedes Ereignis ${\displaystyle A_{e}}$ stochastisch unabhängig von ${\displaystyle \{A_{f}|f\in E({\mathcal {H}}),f\cap e=\emptyset \}}$, da die Knoten unabhängig voneinander gefärbt wurden. Da ${\displaystyle Pr(A_{e})\leq 2\left({\frac {1}{2}}\right)^{k}=2^{1-k}=:p}$ ist, gilt: ${\displaystyle e\cdot p\cdot (d+1)<1}$. Also ist ${\displaystyle Pr\left(\bigcap _{e\in E({\mathcal {H}})}{\overline {A}}_{e}\right)>0}$, das heißt: ${\displaystyle {\mathcal {H}}}$ ist 2-färbbar.[1]

In einer weiteren Version des Lovász-Local-Lemmas[2] genügt die Anforderung ${\displaystyle 4\cdot p\cdot d\leq 1}$. Mit dieser Aussage folgt die 2-Färbbarkeit auch für ${\displaystyle k\geq 3}$. Es gilt dann nämlich ${\displaystyle 4\cdot p\cdot d=4\cdot {\frac {2^{k-3}}{2^{k-1}}}=1}$.

Literatur

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

Einzelnachweise

1. Noga Alon; Joel H. Spencer. The Probabilistic Method. 3. Auflage, 2008. Seite 70
2. Michael Molloy; Bruce Reed. Graph Colouring and the Probabilistic Method. 2002, Kapitel 4