On the 2-colorability of random hypergraphs

Dimitris Achlioptas, Cristopher Moore

A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vert…