Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / B / 7 / a / Solution

The general Lovász local lemma concerns events $A_1,\dots ,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)$ satisfythen $\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)\le 1$, then there is positive probability that no event occurs. For $d\ge 1$, set all $x_i=1/(d+1)$. Sincewe have $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge q$, so the general form applies. The displayed inequality follows from $d\log (1+1/d)\le 1$. When $d=0$, the events are mutually independent and each has probability below one, so their complements have positive joint probability directly.