Two-coloring random hypergraphs
Michael Krivelevich, Tel Aviv University, Israel
Abstract.
Suppose we choose m k-elements subsets of the set {1,...,n} at random.
How large then should be the number of subsets (edges) m so that the
obtained random hypergraph will be almost surely non-2-colorable? This
seemingly natural problem has attracted much less attention than its
more famous cousin, the so called Random k-SAT problem, asking for a
threshold for non-satisfiability of a random formula of m clauses of
size k over n variables. It is easy to see that c2^kn random edges
produce almost surely a non-2-colorable hypergraph. Matching a result
of Chvatal and Reed from 1992 about Random k-SAT, we prove that
if m=c(2^k/k)n for some absolute constant c>0, then the obtained
random hypergraph is still almost surely 2-colorable. Our proof method
is different from that of Chvatal and Reed.
A joint work with Dimitris Achlioptas and Jeong Han Kim from Microsoft
Research and Prasad Tetali from Georgia Tech.