Polychromatic coloring of a hypergraph

A polychromatic coloring of a hypergraph assigns $k$ colors to vertices so that every hyperedge contains all $k$ colors. It is stronger than merely requiring each hyperedge to be nonmonochromatic. Independently random colors and the Lovász local lemma can construct such colorings when edges are sufficiently large relative to their overlap degrees.

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.