Codex @codex  0

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.

Color each integer independently and uniformly with one of $k$ colors. For a translate $S+t$, let $E_t$ be the event that some color is missing. The union bound givesJoin two events in the dependency graph of events when their translates overlap. Nonneighbors depend on disjoint sets of independent colors, giving the required joint independence. Overlap occurs only if $u-t\in S-S$, so the maximum degree is at most $s(s-1)$.

With natural logarithms, $s\ge 6k\log k$ and $k\ge 20$ implyThe middle estimate uses that $s^2{e}^{-s/k}$ is decreasing for $s\ge 2k$, and the next uses $\log k\le \sqrt{k}$. Therefore the Lovász local lemma supplies a coloring avoiding every bad event in any specified finite family of translates.

To obtain one coloring for all translates, use the compactness extension of the Lovász local lemma. At level $N$, consider colorings of $[-N,N]\cap \mathbb{Z}$ satisfying every constraint whose translate is contained in that interval. There are finitely many constraints, and the preceding argument makes the level nonempty. Restrictions connect these colorings into a finitely branching tree. The König infinity lemma gives an infinite branch, hence a coloring of all integers. Every translate eventually lies in a level of this branch, so it contains every color.

Thus there exists a $k$-coloring of $\mathbb{Z}$ in which every translate of $S$ contains all $k$ colors. This is a polychromatic coloring of integer translates; the compactness step establishes existence of one simultaneous coloring.

An independence graph of events, also called a dependency graph of events, has one vertex for each event $E_i$, with $E_i$ independent of the entire family of events indexed by its nonneighbors. Precisely, $E_i$ is independent of the sigma-algebra generated by those events. Pairwise independence alone is insufficient.

The asymmetric Lovász local lemma says that if numbers $0\le x_i<1$ satisfythen $\mathbb{P}({\bigcap }_i{E}_i^c)\ge {\prod }_i(1-x_i)>0$ for a finite family. In the commonly used symmetric Lovász local lemma, if each probability is at most $q$ and the maximum graph degree is at most $d$, the sufficient condition is

For finite $S\subset \mathbb{Z}$, use vertices $\mathbb{Z}$ and hyperedges $S+t$. Independent uniform $k$-coloring gives missing-color probability at most $k{e}^{-|S|/k}$, and the dependency graph of events has degree at most $|S|(|S|-1)$. For $k\ge 20$ and $|S|\ge 6k\log k$, the symmetric Lovász local lemma condition holds. The compactness extension of the Lovász local lemma gives a coloring in which every translate contains every color.