97-29: The chromatic numbers of random hypergraphs

DIMACS TR: 97-29

The chromatic numbers of random hypergraphs

Authors: Michael Krivelevich and Benny Sudakov

ABSTRACT
For a pair of integers 0 < t < r, the t-chromatic number of an r-uniform hypergraph H=(V,E) is the minimal k, for which there exists a partition of V into color classes U1,...,Uk such that every edge of H intersects every color class in at most t vertices. In this paper we determine the asymptotic behavior of the t-chromatic number of the random r-uniform hypergraph on n vertices with edge probability p=p(n) for all possible values of t and for a wide range of values of p.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-29.ps.gz

DIMACS Home Page