A Meeting Point of Probability, Graphs, and Algorithms: The Lovasz Local Lemma and Related Results-A Survey

A classic and fundamental result, known as the Lovasz Local Lemma, is a gem in the probabilistic method of combinatorics. At a high level, its core message can be described by the claim that weakly dependent events behave similarly to independent ones. A fascinating feature of this result is that even though it is a purely probabilistic statement, it provides a valuable and versatile tool for proving completely deterministic theorems. The Lovasz Local Lemma has found many applications; despite being originally published in 1973, it still attracts active novel research. In this survey paper, we review various forms of the Lemma, as well as some related results and applications.

Automated summary

The Lovasz Local Lemma, a classic result in combinatorics' probabilistic method, reveals that weakly dependent events behave similarly to independent ones. Despite being a purely probabilistic statement, it serves as a valuable and versatile tool in proving deterministic theorems, with various applications and continued research interest.