= Polychromatic hypergraph colouring
A colouring is polychromatic with $r$ colours if every <hypergraph edge> contains a vertex of every colour. This is stronger than requiring every edge to be nonmonochromatic. Under independent uniform colours, a $k$-element edge misses at least one of three colours with probability $3(2/3)^k-3(1/3)^k$. If each edge meets at most $m$ other edges, the edge-intersection <dependency graph of events> and the <Lovász local lemma> therefore give a polychromatic three-colouring whenever $e(m+1)[3(2/3)^k-3(1/3)^k]\leq1$.
Back to article page
