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$.

For each fixed integer $q\ge 2$, every sufficiently high-degree finite regular graph has an assignment of $q$ colors such that every vertex has a neighbour whose color is its successor modulo $q$. This assignment need not be a proper vertex coloring. If the degree is $r$, independent uniform vertex colors make a given vertex fail with probability $(1-1/q{)}^r$. That event depends on its closed neighbourhood, and has at most $r^2$ dependencies, since only centres within distance two matter. The symmetric Lovász local lemma therefore gives such an assignment whenever $e(r^2+1)(1-1/q{)}^r\le 1$, which holds for all sufficiently large $r$.

Choose one successor neighbour from each vertex. The resulting directed graph has outdegree one and hence contains a directed cycle. Its color increases once modulo $q$ on each step, so its length is divisible by $q$. Thus a nontrivial cycle of length a multiple of $q$ is obtained when $q\ge 3$; for $q=2$ a directed two-cycle may simply traverse one undirected edge twice, so this last cycle inference needs a separate argument if an undirected simple cycle is required.

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.