Lovász local lemma

For bad events with a dependency graph of maximum degree $D$, the symmetric Lovász local lemma guarantees positive probability that none occurs whenever each event has probability at most $p$ and $ep(D+1)\le 1$.

In an independent random two-colouring of $K_N$, a given $k$-vertex set is monochromatic with probability $2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events on sets intersecting in at most one vertex use disjoint edges. Thus dependency degree is at most $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)$. The Lovász local lemma gives a colouring avoiding all monochromatic $K_k$ when $e{2}^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}(1+(\genfrac{}{}{0ex}{}{k}{2}\left)\right(\genfrac{}{}{0ex}{}{N-2}{k-2}))\le 1$. For $N=ck{2}^{k/2}$ the expression is $O(k^{3/2}(ec/\sqrt{2}{)}^k)$, by Stirling's approximation. Taking $c$ tending sufficiently slowly to $\sqrt{2}/e$ proves $R(k)\ge (\sqrt{2}/e+o(1))k{2}^{k/2}$.

Let $B_v$ be independent Bernoulli random variables on a rooted $d$-ary tree, and put $A_v=\{B_v=1,B_w=0\text{ for every child }w\}$. Events at nonadjacent vertices use disjoint variables, giving a dependency graph of events of maximum degree $d+1$. Assign leaf success probability $p$ and successive probabilities $r_{j+1}=p/(1-r_j{)}^d$. If $p>{\max }_{0\le r\le 1}r(1-r{)}^d=p_d$, the recursion eventually reaches one. Set the final root success probability to one. Each event has probability at most $p$, but following success vertices down from the root must reach an occurring event. Thus the bad events cover the sample space. This gives an upper bound for uniform avoidance thresholds without assuming a converse to the Lovász local lemma.

For countably many constraints on finite-valued variables, each involving finitely many variables, apply the finite Lovász local lemma to every finite constraint subfamily. Partial satisfying assignments on increasing finite variable sets form a finitely branching tree with nonempty levels. The König infinity lemma gives an infinite branch, producing one assignment satisfying all constraints. This existence argument does not assert positive probability of simultaneous avoidance in an infinite product space.

For a finite family with a dependency graph of events, if $0\le x_i<1$ satisfy $\mathbb{P}(E_i)\le x_i{\prod }_{j\in N(i)}(1-x_j)$, then $\mathbb{P}({\bigcap }_i{E}_i^c)\ge {\prod }_i(1-x_i)>0$. Choosing equal $x_i$ gives the familiar symmetric criterion $eq(d+1)\le 1$ when event probabilities are at most $q$ and the maximum dependency degree is $d$.

A dependency graph of events joins potentially dependent events. Each event must be independent of the sigma-algebra generated by all its nonneighbors, a joint condition stronger than pairwise independence. In a product probability space, joining events whose sets of underlying independent variables overlap gives such a graph. This supplies the hypothesis of the Lovász local lemma.

For events $A_i$, a directed graph is an independence digraph if $A_i$ is independent of the sigma-algebra generated by the events indexed by its non-outneighbors, excluding $i$. The direction records which joint independence condition is available. A cyclically oriented triangle imposes pairwise independence; it does not impose independence of all three events together.

Let $A_1,\dots ,A_m$ be bad events with a lopsidependency graph. If numbers $x_i\in [0,1)$ satisfyfor every $i$, then $\mathbb{P}({\bigcap }_i{A}_i^c)>0$. Unlike the ordinary Lovász local lemma, a lopsidependency graph may omit pairs whose interaction can only make their simultaneous avoidance easier.

For bad events $A_i$, a correlation graph is sufficient for the Lopsided Lovász local lemma when, for every set $S$ of nonneighbors and every positive-probability conditioning event, $\mathbb{P}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)\le \mathbb{P}(A_i)$. A dependency graph of events satisfies this with equality. The condition concerns simultaneous avoidance, not just signs of pairwise correlations.