A Complete Hierarchy of Local LemmasResearch Paper
Suppose each vertex of a graph carries a bad event with , and is a dependency graph: each is independent of the collection of events at its non-neighbors. The Lovász Local Lemma gives a local sufficient condition under which, with positive probability, no bad event occurs. Shearer (Shearer 1985) found the exact condition: writing