Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / B / 6 / a

A dependency graph of events, written here as a loopless directed graph $D$ on the event indices, must satisfy a joint independence condition: for each $i$, $A_i$ is independent of the sigma-algebra generated by all $A_j$ with $j\ne i$ and no arc $i\to j$. In particular this means independence from every Boolean combination of those non-neighbour events, not merely pairwise independence. The outgoing neighbours list the events for which that independence is not required.

The asymmetric Lovász local lemma states that if there are numbers $0\le x_i<1$ withfor every index, thenFor maximum out-degree $d\ge 1$, take every $x_i=1/(d+1)$. Sinceone has $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge p$. Fewer than $d$ outgoing neighbours only increases the product, so the hypothesis is satisfied whenever $ep(d+1)\le 1$.

If $d=0$, take $x_i=p<1$; the neighbour products are empty and equal one. This separately covers the case in which $1/(d+1)$ would equal the forbidden value one. Thus the symmetric local lemma follows in every case.

For distinct indices put arcs in both directions whenever $S_i\cap S_j\ne \varnothing$. If $j$ is not an outgoing neighbour of $i$, every variable determining $A_j$ lies outside $S_i$. The entire family of such events is measurable with respect to variables outside $S_i$, whose sigma-algebra is independent of the variables inside $S_i$. Thus $A_i$ is independent of their whole generated sigma-algebra, establishing the required dependency graph of events. This justifies joint independence rather than just checking each pair.