The Lovász local lemma is a probabilistic method for proving that a collection of events can all be avoided even when the events are not
mutually independent. Let 
be events, and let 
be a dependency graph: each 
is independent of every event determined by the 
whose vertices are neither 
nor adjacent to 
in 
. Write 
for the neighbors of 
. If there are numbers 
such that
 |
(1)
|
then
 |
(2)
|
In particular, there is an outcome in which none of the events occurs.
The frequently used symmetric form assumes that 
for every 
and that each event is dependent on at most 
other events. It is enough that
 |
(3)
|
Unlike a direct union bound, the local lemma exploits the limited dependence among the bad events. It has applications throughout combinatorics, including graph coloring, Ramsey theory, and constructions avoiding prescribed local configurations.
