Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 11 / 4 / ii

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.