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.

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

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