# Lovasz Local Lemma

The probabilistic method is a non-constructive way of proving the existence of an object having certain property. The argument usually goes as follows: a randomly selected object has the desired property with probability strictly positive, thus there must exist an object having the property; however, we do not know how to explicitly construct such an object. The Lovasz Local Lemma is an example of the probabilistic method.

### The Lovasz Local Lemma

Suppose that we have a collection of events $$\{A_1,\ldots, A_n\}$$, and consider the probability that none of them happens:
${\bf Pr}[\wedge_{i=1}^{n} \overline{ A_i}].$
If the events are mutually independent, and if there exists $$p < 1$$ such that $${\bf Pr}[ A_i] \leq p$$ for every $$i$$, then ${\bf Pr}[\wedge_{i=1}^{n} \overline{A_i}] = \prod_{i=1}^{n} {\bf Pr}[\overline{A_i}] \geq (1-p)^n > 0.$

Note that, although $$(1-p)^n$$ is exponentially small in $$n$$, it is still positive.

The Lovasz Local Lemma generalizes “mutually independent” condition to allow limited dependencies among the events.

We say an event $$A$$ is mutually independent of a set of events $$\{ B_i\}_{i=1}^n$$ if for any subset $$I\subseteq [n]$$, it holds that $${\bf Pr}[A\mid \wedge_{i\in I}B_i] = {\bf Pr}[A]$$.