= Polychromatic coloring of integer translates
For finite $S\subset\mathbb Z$, use vertices $\mathbb Z$ and hyperedges $S+t$. Independent uniform $k$-coloring gives missing-color probability at most $ke^{-|S|/k}$, and the <dependency graph of events> has degree at most $|S|(|S|-1)$. For $k\ge20$ and $|S|\ge6k\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.
Back to article page
