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

For events $A_i$ with a dependency graph, assume each event is independent of the sigma-algebra generated by its nonneighbours. If numbers $x_i\in [0,1)$ satisfy $P(A_i)\le x_i{\prod }_{j\in \Gamma (i)}(1-x_j)$, the general Lovász local lemma givesThe symmetric version says that if every event has probability at most $q$, the dependency graph has maximum degree at most $d$, and $eq(d+1)\le 1$, then none occurs with positive probability. For $d\ge 1$, set $x_i=1/(d+1)$. Since $(1-1/(d+1){)}^d\ge e^{-1}$, the general condition follows from the symmetric numerical hypothesis. The logarithmic inequality $\log (1+1/d)\le 1/d$ proves that estimate. When $d=0$, the events are mutually independent and each has probability below one, so the conclusion is immediate. This is the intended implication from the general to the symmetric form; the source repeats the word symmetric in its final clause.