Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 11 / 4 / i / Solution

An independence graph of events, also called a dependency graph of events, has one vertex for each event $E_i$, with $E_i$ independent of the entire family of events indexed by its nonneighbors. Precisely, $E_i$ is independent of the sigma-algebra generated by those events. Pairwise independence alone is insufficient.

The asymmetric Lovász local lemma says that if numbers $0\le x_i<1$ satisfythen $\mathbb{P}({\bigcap }_i{E}_i^c)\ge {\prod }_i(1-x_i)>0$ for a finite family. In the commonly used symmetric Lovász local lemma, if each probability is at most $q$ and the maximum graph degree is at most $d$, the sufficient condition is