Two‐coloring random hypergraphs

A 2‐coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H=H(k, n, p) be a random k‐uniform hypergraph on a vertex set V of cardinality n, where each k‐subset of V is an edge of H with probability p, independently of all other k‐subsets. Let {article}{empty}{document}m = pnk{document} denote the expected number of edges in H. Let us say that a sequence of events ℰn holds with high probability (w.h.p.) if limn→∞Pr[ℰn]=1. It is easy to show that if m=c2kn then w.h.p H is not 2‐colorable for c>ln 2/2. We prove that there exists a constant c>0 such that if m=(c2k/k)n, then w.h.p H is 2‐colorable.