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

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.

The symmetric Lovász local lemma states: if each bad event has probability at most $p$, each event is independent of the collection of all but at most $d$ other events, andthen the probability that none of the bad events occurs is positive. Independence is from the sigma-algebra generated by the indicated nonneighbours, as in part (a). A sufficient sharper parameter condition is $p\le x(1-x{)}^d$ for some $x\in (0,1)$; taking $x=1/(d+1)$ gives the displayed standard bound when $d\ge 1$. When $d=0$, mutual independence directly gives the conclusion under the displayed bound.

If there are no triangles, any edge colouring works. Otherwise $\Delta \ge 2$. Put $q=\lceil 3\sqrt{\Delta }\rceil$ and colour each edge independently and uniformly from $q$ colours. For each triangle $T$, let $A_T$ be the event that its three edges have one colour. ThenEvents for triangles sharing no edge depend on disjoint edge-colour variables, so each event is jointly independent of the collection of all such nonneighbours. Each edge of a triangle lies in at most $\Delta -2$ other triangles: a common neighbour of its endpoints must be one of at most $\Delta -1$ neighbours besides the other endpoint, and one of these is the third vertex of $T$ itself. Thus the dependency degree is at most $d=3(\Delta -2)$.

Because $q^2\ge 9\Delta$,The symmetric local lemma gives positive probability of avoiding every monochromatic triangle. HenceFor an edgeless graph the empty colouring handles even the zero-colour case $\Delta =0$.