= 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$ satisfy
$$
\mathbb P(E_i)\le x_i\prod_{j\in N(i)}(1-x_j),
$$
then $\mathbb P(\bigcap_iE_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
$$
\boxed{eq(d+1)\le1}.
$$
Back to article page
