Polychromatic coloring of a hypergraph (source code)

= Polychromatic coloring of a hypergraph

A <polychromatic coloring of a hypergraph> assigns $k$ colors to vertices so that every hyperedge contains all $k$ colors. For $k\geq2$, 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.