Lovász-Local-Lemma

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das Lovász-Local-Lemma ist ein Hilfssatz aus der Wahrscheinlichkeitstheorie. Es verallgemeinert das Argument, dass die stochastische Unabhängigkeit von Ereignissen mit positiver Wahrscheinlichkeit eine positive Wahrscheinlichkeit für das Eintreten 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.[1]

Einen konstruktiven Beweis und eine algorithmische Version gaben Robin A. Moser und Gábor Tardos 2008/09[2][3] und erhielten dafür den Gödel-Preis (2020). Zusätzlich konnten sie die Algorithmen für die Verwendung von LLL vollständig de-randomisieren.

Aussage des Lemmas

[Bearbeiten | Quelltext bearbeiten]

Allgemeine Version

[Bearbeiten | Quelltext bearbeiten]

Sei eine Menge von Ereignissen über einem beliebigen Wahrscheinlichkeitsraum, so dass jedes Ereignis stochastisch unabhängig von allen Ereignissen in jeweils einem ist.

Falls reelle Zahlen existieren, so dass für alle gilt:

,

so folgt: .

In vielen Beweisen wird der folgende symmetrische Spezialfall verwendet.

Symmetrische Version

[Bearbeiten | Quelltext bearbeiten]

Sei eine Menge von Ereignissen über einem beliebigen Wahrscheinlichkeitsraum, so dass jedes Ereignis aus von höchstens anderen Ereignissen stochastisch abhängig ist. Definiere .

Gilt ( bezeichnet die eulersche Zahl)
so folgt .

Anwendungsbeispiel

[Bearbeiten | Quelltext bearbeiten]

Sei ein Hypergraph, so dass jede Hyperkante mindestens Knoten enthält und sich mit höchstens weiteren Hyperkanten schneidet und . Dann ist 2-färbbar.

Färbe die Knoten von 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 ). Setze für alle Hyperkanten : Wende nun das symmetrische Local-Lemma auf die Menge an. Dabei ist das Ereignis, dass alle Knoten einer Kante in der gleichen Farbe gefärbt worden sind. Zunächst ist jedes Ereignis stochastisch abhängig von , da sich jede Kante aus per Definition mindestens einen Knoten mit teilt. Nach Voraussetzung gilt: für alle Kanten . Andererseits ist jedes Ereignis stochastisch unabhängig von , da die Knoten unabhängig voneinander gefärbt wurden. Da ist, gilt: . Also ist , das heißt: ist 2-färbbar.[4]

In einer weiteren Version des Lovász-Local-Lemmas[5] genügt die Anforderung . Mit dieser Aussage folgt die 2-Färbbarkeit auch für . Es gilt dann nämlich .

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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: A. Hajnal; R. Rado; V. T. Sós (Hrsg.). Infinite and Finite Sets (to Paul Erdős on his 60th birthday), Band 2, North-Holland, 1975, S. 609–627
  2. Robin A. Moser: A constructive proof of the Lovasz Local Lemma, Arxiv 2008
  3. R. A. Moser, G. Tardos, A constructive proof of the general Lovasz Local Lemma, Journal of the ACM, Band 47, 2010, Heft 2, S. 1–11, Arxiv 2009,
  4. Noga Alon; Joel H. Spencer. The Probabilistic Method. 3. Auflage, 2008. Seite 70
  5. Michael Molloy; Bruce Reed. Graph Colouring and the Probabilistic Method. 2002, Kapitel 4