Lovacz Local Lemma

Let \(A_1, ... A_m\) be bad events such that \(\forall i\)

• \[\mathbb{P}[A_i] \leq p\]
• \(A_i\) is mutually independent of all but \(d\) other events

Then:

1. If \(p d \leq 1/4\), then \(\mathbb{P}[\cap_i \overline{A_i}] \geq (1 - 2 p)^m > 0\)
2. If \(p d \leq 1/e\), then \(\mathbb{P}[\cap_i \overline{A_i}] \geq (1 - \frac{1}{d+1})^m > 0\)