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

A dependency digraph has vertices $1,\dots ,n$ and no loops. For each $i$, the event $A_i$ must be independent of the sigma-algebra generated jointly by all $A_j$ with $j\ne i$ for which there is no edge $i\to j$. Joint independence from that collection is required; pairwise independence alone does not suffice.

Write ${\Gamma }^{+}(i)$ for the outneighbours of $i$, and $B_S={\bigcap }_{j\in S}{A}_j^c$. We prove by induction on $|S|$ that $B_S$ has positive probability and, when $i\notin S$,For $S=\varnothing$, the asserted conditional bound follows from the hypothesis, since its product factors are at most one. For the induction step, positivity for a set of size $r$ follows by writing its avoidance probability as a chain product: all preceding conditioning sets have size below $r$, so each factor is at least $1-x_j>0$.

Now take $|S|=r$, split $S_1=S\cap {\Gamma }^{+}(i)$ and $S_2=S\setminus {\Gamma }^{+}(i)$, and condition first on $B_{S_2}$. Independence gives $\mathbb{P}(A_i\mid B_{S_2})=\mathbb{P}(A_i)$. Moreover, order the elements of $S_1$ and use the inductive conditional bounds on the successive avoidance factors. Their conditioning sets have size at most $r-1$, soThis remains true when $S_1$ is empty, with both sides one. ThereforeThe induction is complete. Finally expand the probability of avoiding all events in the order $1,\dots ,n$:This proves the asymmetric Lovász local lemma, including the positivity needed to make every conditioning step legitimate.