Lovász local lemma

In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma allows one to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs. There are several different versions of the lemma. The simplest and most frequently used is the symmetric version given below. 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. For other versions, see . In 2020, Robin Moser and Gábor Tardos received the Gödel Prize for their algorithmic version of the Lovász Local Lemma, which uses entropy compression to provide an efficient randomized algorithm for finding an outcome in which none of the events occurs. Let A1, A2,..., Ak be a sequence of events such that each event occurs with probability at most p and such that each event is independent of all the other events except for at most d of them. Lemma I (Lovász and Erdős 1973; published 1975) If then there is a nonzero probability that none of the events occurs. Lemma II (Lovász 1977; published by Joel Spencer) If where e = 2.718... is the base of natural logarithms, then there is a nonzero probability that none of the events occurs. Lemma II today is usually referred to as "Lovász local lemma". Lemma III (Shearer 1985) If then there is a nonzero probability that none of the events occurs. The threshold in Lemma III is optimal and it implies that the bound is also sufficient. A statement of the asymmetric version (which allows for events with different probability bounds) is as follows: Lemma (asymmetric version). Let be a finite set of events in the probability space Ω.