The Lovasz Local Lemma gives conditions under which a large collection of mostly independent unwanted events can be avoided simultaneously with positive probability, even in cases where the ordinary union bound is too weak to guarantee this. Named for László Lovasz, it is a foundational tool of the probabilistic method in combinatorics, used to prove the existence of combinatorial structures that are otherwise hard to construct directly.
Facts
Partially Attested
Proof YearWikipedia dates a weaker version by Lovasz and Erdos to 1975; the sharper form is credited to Lovasz in the same period, so the year is for the first published version. Classification
Statement Form Connections
Has Statement Form
In Branch
Proved By
Source Lovasz local lemma (Wikipedia)
Sources
1. Lovasz local lemma (Wikipedia)
History section
A weaker version was proved in 1975 by László Lovász and Paul Erdős in the article Problems and results on 3-chromatic hypergraphs and some related questions.
Proved By: László Lovász, Lead
A weaker version was proved in 1975 by László Lovász and Paul Erdős in the article Problems and results on 3-chromatic hypergraphs and some related questions.
In Group: Ramsey Theory and Extremal Combinatorics, Lead section
of them occurs. This lemma is most commonly used in the probabilistic method, in particular to give existence proofs. There
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.