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

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.

Color every edge independently and uniformly with one of $k$ colors. For each unoriented simple four-edge path $P$, let $A_P$ be its repetition event. Its four distinct edges must satisfy two prescribed color equalities, so $\mathbb{P}(A_P)=k^{-2}$.

Events with edge-disjoint paths depend on disjoint random variables. A fixed edge lies on at most $4{\Delta }^3$ unoriented four-edge paths: count its four possible positions and two orientations, bound the remaining choices by ${\Delta }^3$, then divide the oriented path count by two. Thus the union of all paths sharing any of $P$'s four edges has size at most $16{\Delta }^3$. This union includes $P$ itself, so a dependency graph has $d+1\le 16{\Delta }^3$.

For $k\ge 8{\Delta }^{3/2}$,The symmetric Lovász local lemma yields positive probability of avoiding every event. Therefore such an edge coloring exists. If there are no four-edge paths the conclusion is immediate.

Use the same independent coloring, now with events indexed by unoriented six-edge paths. A repetition fixes the second three-edge color block to equal the first, so each event has probability $k^{-3}$. A fixed edge belongs to at most $6{\Delta }^5$ such paths, and a six-edge path has at most $36{\Delta }^5$ events in its closed dependency neighbourhood. Thus $d+1\le 36{\Delta }^5$.

For $k\ge 5{\Delta }^{5/3}$,The symmetric Lovász local lemma again guarantees a coloring avoiding all six-edge repetition events. Thus the required coloring exists, with the empty event family handled trivially.

Use both families of bad events in one asymmetric Lovász local lemma application. Give every four-edge event parameter $x_4$ and every six-edge event parameter $x_6$. A path of length $\ell$ shares edges with at most $4\ell {\Delta }^3$ four-edge paths and $6\ell {\Delta }^5$ six-edge paths. It therefore suffices to verifyThese slightly excessive exponents are safe even though they may count the event itself. Choose $x_4=2/k^2$ and $x_6=2/k^3$. For $k\ge C{\Delta }^{5/3}$, the sums of exponents times their parameters are bounded by constants times $C^{-2}{\Delta }^{-1/3}+C^{-3}$, uniformly in $\Delta \ge 1$. Taking $C$ sufficiently large makes each product of factors at least $1/2$, for example using $(1-x{)}^r\ge 1-rx$ and multiplying the two factors. Both displayed inequalities then hold. Positive probability of no bad event gives simultaneous avoidance of both lengths. Keeping two event parameters avoids replacing the rarer six-edge events by the larger four-edge probability.

These are the avoiding short repetitions in an edge coloring bounds, for repetitively colored paths.