Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 14 / 5

The general, or asymmetric Lovász local lemma, is as follows. Let $E_1,\dots ,E_m$ be events, with a dependency graph of events having neighbour sets $N(i)$. Each $E_i$ must be independent of the sigma-algebra generated by all the events indexed by its nonneighbours. If numbers $0\le x_i<1$ satisfythenFor completeness, the key inductive bound is $\mathbb{P}(E_i\mid {\bigcap }_{j\in S}{E}_j^c)\le x_i$ whenever $i\notin S$. Split $S$ into neighbours $S_1$ of $i$ and nonneighbours $S_2$. If $S_1$ is empty, the dependency condition gives the bound directly. Otherwise,The denominator bound follows by exposing the exclusions in $S_1$ one at a time and using the induction hypothesis with strictly fewer conditioning events. The same induction ensures that all conditioning events have positive probability. Finally multiply the successive conditional probabilities of avoiding $E_1,\dots ,E_m$ to obtain the stated lower bound.

For the symmetric form, suppose each event has probability at most $q$ and the dependency graph has maximum degree $D\ge 1$. Choose $x_i=1/(D+1)$. ThenThe final inequality follows from $(1+1/D{)}^D\le e$. Thus $eq(D+1)\le 1$ suffices for positive probability that no bad event occurs. If $D=0$, the dependency condition gives joint independence and the same criterion implies $q<1$, so the conclusion follows directly.

Apply this to a fair independent two-colouring of the hypergraph vertices, with $E_W$ the event that hypergraph edge $W$ is monochromatic. Its probability is $q=2^{1-r}$. Events on disjoint hypergraph edges use disjoint independent variables, giving a dependency graph by joining intersecting hypergraph edges. Each hypergraph edge meets at mostother hypergraph edges; repeated counting only enlarges this upper bound. The slightly looser bound $D+1\le r(\Delta +1)$ is enough for the printed condition. Indeed,The symmetric Lovász local lemma therefore gives a proper two-colouring. A hypergraph with no hypergraph edges is trivially colourable and needs no dependency calculation.

Let $S$ be the number of red vertices in $W$. It has a binomial distribution with parameters $r$ and $1/2$, so independence givesFor $t=1$, the strict inequality $\log \cosh (1/2)<1/8$ follows by integrating $\tanh u<u$ for $u>0$. Hence the exponential Markov bound yieldsThereforeThis supplies the tail estimate directly, including the strict constant in the requested bound.

For each hypergraph edge $W$, let $B_W$ be the event that one of its two colours occupies more than $3r/4$ vertices. By colour symmetry and the union bound, the preceding calculation givesAgain the dependency graph joins intersecting hypergraph edges and has $D+1\le r(\Delta +1)$. The assumed degree bound impliesThe symmetric Lovász local lemma gives positive probability that no $B_W$ occurs. Thus there is a two-colouring in which each colour occupies at most $3r/4$ vertices of every hypergraph edge. Equivalently, both colour counts in every hypergraph edge lie between $r/4$ and $3r/4$; no rounding difficulty arises because the counts are integers and the bad events use strict inequalities.