Lovász Local Lemma Das ist ein Hilfssatz aus der Wahrscheinlichkeitstheorie Es verallgemeinert das Argument dass die sto

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 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.

Einen konstruktiven Beweis und eine algorithmische Version gaben Robin A. Moser und Gábor Tardos 2008/09 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

Allgemeine Version 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

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

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.

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

Literatur Bearbeiten

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

Einzelnachweise Bearbeiten

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
Robin A. Moser: A constructive proof of the Lovasz Local Lemma, Arxiv 2008
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,
Noga Alon; Joel H. Spencer. The Probabilistic Method. 3. Auflage, 2008. Seite 70
Michael Molloy; Bruce Reed. Graph Colouring and the Probabilistic Method. 2002, Kapitel 4

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: März 18, 2024, 08:31 am

Das Lovasz Local Lemma ist ein Hilfssatz aus der Wahrscheinlichkeitstheorie Es verallgemeinert das Argument dass die stochastische Unabhangigkeit von Ereignissen mit positiver Wahrscheinlichkeit eine positive Wahrscheinlichkeit fur das Eintreten aller Ereignisse impliziert auf Situationen in denen nicht alle Ereignisse unabhangig sind Sein Name beruht darauf dass es lokale Eigenschaften zu einem globalen Ergebnis zusammensetzt Es findet am haufigsten Anwendung in probabilistischen Ansatzen um Existenzbeweise zu fuhren 1975 wurde es von Laszlo Lovasz und Paul Erdos bewiesen 1 Einen konstruktiven Beweis und eine algorithmische Version gaben Robin A Moser und Gabor Tardos 2008 09 2 3 und erhielten dafur den Godel Preis 2020 Zusatzlich konnten sie die Algorithmen fur die Verwendung von LLL vollstandig de randomisieren Inhaltsverzeichnis 1 Aussage des Lemmas 1 1 Allgemeine Version 1 2 Symmetrische Version 2 Anwendungsbeispiel 3 Literatur 4 EinzelnachweiseAussage des Lemmas BearbeitenAllgemeine Version Bearbeiten Sei E A 1 A 2 A n displaystyle mathcal E A 1 A 2 dots A n nbsp eine Menge von Ereignissen uber einem beliebigen Wahrscheinlichkeitsraum so dass jedes Ereignis A i displaystyle A i nbsp stochastisch unabhangig von allen Ereignissen in jeweils einem D i E displaystyle mathcal D i subseteq mathcal E nbsp ist Falls reelle Zahlen x 1 x 2 x n 0 1 displaystyle x 1 x 2 dots x n in 0 1 nbsp existieren so dass fur alle i 1 2 n displaystyle i in 1 2 dots n nbsp gilt P r A i x i A k D i 1 x k displaystyle Pr A i leq x i prod A k in mathcal D i 1 x k nbsp so folgt P r i 1 n A i j 1 n 1 x j gt 0 displaystyle Pr bigcap i 1 n overline A i geq prod j 1 n 1 x j gt 0 nbsp In vielen Beweisen wird der folgende symmetrische Spezialfall verwendet Symmetrische Version Bearbeiten Sei E A 1 A 2 A n displaystyle mathcal E A 1 A 2 dots A n nbsp eine Menge von Ereignissen uber einem beliebigen Wahrscheinlichkeitsraum so dass jedes Ereignis aus E displaystyle mathcal E nbsp von hochstens d displaystyle d nbsp anderen Ereignissen stochastisch abhangig ist Definiere p max i 1 n P r A i displaystyle p max i in 1 dots n Pr A i nbsp Gilt e p d 1 1 displaystyle e cdot p cdot d 1 leq 1 quad nbsp e displaystyle e nbsp bezeichnet die eulersche Zahl so folgt P r i 1 n A i gt 0 displaystyle Pr bigcap i 1 n overline A i gt 0 nbsp Anwendungsbeispiel BearbeitenSei H displaystyle mathcal H nbsp ein Hypergraph so dass jede Hyperkante mindestens k displaystyle k nbsp Knoten enthalt und sich mit hochstens 2 k 3 displaystyle 2 k 3 nbsp weiteren Hyperkanten schneidet und k 5 displaystyle k geq 5 nbsp Dann ist H displaystyle mathcal H nbsp 2 farbbar Farbe die Knoten von H displaystyle mathcal H nbsp zunachst zufallig unabhangig und gleichverteilt mit zwei Farben d h die Wahrscheinlichkeit dass ein Knoten beispielsweise rot oder blau ist betragt jeweils 1 2 displaystyle frac 1 2 nbsp Setze N e f E H f e displaystyle N e f in E mathcal H f cap e neq emptyset nbsp fur alle Hyperkanten e E H displaystyle e in E mathcal H nbsp Wende nun das symmetrische Local Lemma auf die Menge E A e e E H displaystyle mathcal E A e e in E mathcal H nbsp an Dabei ist A e displaystyle A e nbsp das Ereignis dass alle Knoten einer Kante e displaystyle e nbsp in der gleichen Farbe gefarbt worden sind Zunachst ist jedes Ereignis A e displaystyle A e nbsp stochastisch abhangig von N e displaystyle N e nbsp da sich jede Kante aus N e displaystyle N e nbsp per Definition mindestens einen Knoten mit e displaystyle e nbsp teilt Nach Voraussetzung gilt N e 2 k 3 d displaystyle N e leq 2 k 3 d nbsp fur alle Kanten e E H displaystyle e in E mathcal H nbsp Andererseits ist jedes Ereignis A e displaystyle A e nbsp stochastisch unabhangig von A f f E H f e displaystyle A f f in E mathcal H f cap e emptyset nbsp da die Knoten unabhangig voneinander gefarbt wurden Da P r A e 2 1 2 k 2 1 k p displaystyle Pr A e leq 2 left frac 1 2 right k 2 1 k p nbsp ist gilt e p d 1 lt 1 displaystyle e cdot p cdot d 1 lt 1 nbsp Also ist P r e E H A e gt 0 displaystyle Pr left bigcap e in E mathcal H overline A e right gt 0 nbsp das heisst H displaystyle mathcal H nbsp ist 2 farbbar 4 In einer weiteren Version des Lovasz Local Lemmas 5 genugt die Anforderung 4 p d 1 displaystyle 4 cdot p cdot d leq 1 nbsp Mit dieser Aussage folgt die 2 Farbbarkeit auch fur k 3 displaystyle k geq 3 nbsp Es gilt dann namlich 4 p d 4 2 k 3 2 k 1 1 displaystyle 4 cdot p cdot d 4 cdot frac 2 k 3 2 k 1 1 nbsp Literatur BearbeitenMichael Molloy Bruce Reed Graph Colouring and the Probabilistic Method Springer 2002 ISBN 3 540 42139 4 S 221 229 Einzelnachweise Bearbeiten P Erdos L Lovasz Problems and results on 3 chromatic hypergraphs and some related questions in A Hajnal R Rado V T Sos Hrsg Infinite and Finite Sets to Paul Erdos on his 60th birthday Band 2 North Holland 1975 S 609 627 Robin A Moser A constructive proof of the Lovasz Local Lemma Arxiv 2008 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 Noga Alon Joel H Spencer The Probabilistic Method 3 Auflage 2008 Seite 70 Michael Molloy Bruce Reed Graph Colouring and the Probabilistic Method 2002 Kapitel 4 Abgerufen von https de wikipedia org w index php title Lovasz Local Lemma amp oldid 222861798