Proc. RANDOM 2002

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 vertices formed by picking m edges uniformly, independently and with replacement. It is easy to show that if r <= r_c = 2^{k-1} ln 2 - (ln 2) /2, then with high probability H_k(n,m=rn) is not 2-colorable. We complement this observation by proving that if r <= r_c - 1 then with high probability H_k(n,m=rn) is 2-colorable.

Cris Moore <moore@santafe.edu>