= Solution
The general, or <asymmetric Lovász local lemma>, is as follows. Let $E_1,\ldots,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\leq x_i<1$ satisfy
$$
\mathbb P(E_i)\leq x_i\prod_{j\in N(i)}(1-x_j),
$$
then
$$
\mathbb P\left(\bigcap_{i=1}^m E_i^c\right)\geq\prod_{i=1}^m(1-x_i)>0.
$$
For completeness, the key inductive bound is $\mathbb P(E_i\mid\bigcap_{j\in S}E_j^c)\leq 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,
$$
\mathbb P\left(E_i\mid\bigcap_{j\in S}E_j^c\right)
\leq\frac{\mathbb P(E_i\mid\bigcap_{j\in S_2}E_j^c)}{\mathbb P(\bigcap_{j\in S_1}E_j^c\mid\bigcap_{j\in S_2}E_j^c)}
\leq\frac{\mathbb P(E_i)}{\prod_{j\in S_1}(1-x_j)}\leq x_i.
$$
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,\ldots,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\geq1$. Choose $x_i=1/(D+1)$. Then
$$
x_i\prod_{j\in N(i)}(1-x_j)
\geq\frac{1}{D+1}\left(\frac{D}{D+1}\right)^D
\geq\frac{1}{e(D+1)}.
$$
The final inequality follows from $(1+1/D)^D\leq e$. Thus \b[$eq(D+1)\leq1$ 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 most
$$
D\leq\sum_{v\in W}(d_H(v)-1)\leq r(\Delta-1)
$$
other <hypergraph edges>; repeated counting only enlarges this upper bound. The slightly looser bound $D+1\leq r(\Delta+1)$ is enough for the printed condition. Indeed,
$$
\Delta<\frac{2^r}{2re}-1
\quad\Longrightarrow\quad
e,2^{1-r}(D+1)\leq e,2^{1-r}r(\Delta+1)<1.
$$
The symmetric <Lovász local lemma> therefore gives \b[a proper two-colouring]. A <hypergraph> with no <hypergraph edges> is trivially colourable and needs no dependency calculation.
Back to article page
