= Solution
The general <Lovász local lemma> concerns events $A_1,\ldots,A_m$ with a dependency <graph>: each $A_i$ is independent of the <sigma-algebra> generated by all nonneighbouring events other than itself. If numbers $x_i\in[0,1)$ satisfy
$$
\mathbb P(A_i)\le x_i\prod_{j\in\Gamma(i)}(1-x_j),
$$
then $\mathbb P(\bigcap_i A_i^c)\ge\prod_i(1-x_i)>0$.
Its symmetric form states that if $\mathbb P(A_i)\le q$, every dependency degree is at most $d$, and $eq(d+1)\le1$, then there is positive probability that no event occurs. For $d\ge1$, set all $x_i=1/(d+1)$. Since
$$
\left(1-\frac1{d+1}\right)^d\ge e^{-1},
$$
we have $x_i(1-x_i)^d\ge1/[e(d+1)]\ge q$, so the general form applies. The displayed inequality follows from $d\log(1+1/d)\le1$. When $d=0$, the events are mutually independent and each has probability below one, so their complements have positive joint probability directly.
Back to article page
