The Chromatic Numbers of Random Hypergraphs

For a pair of integers 1 fl ! r, the fl-chromatic number of an r-uniform hypergraph H = (V; E) is the minimal k, for which there exists a partition of V into subsets T 1 ; : : : ; T k such that je " T i j fl for every e 2 E. In this paper we determine the asymptotic behavior of the fl-chromatic number of the random r-uniform hypergraph H r (n; p) for all possible values of fl and for all values of p down to p = \Theta(n \Gammar+1 ). 1 Introduction A hypergraph H is an ordered pair H = (V; E) , where V is a finite set (the vertex set), and E is a family of distinct subsets of V (the edge set). A hypergraph H = (V; E) is r-uniform if all edges of H are of size r. In this paper we consider only r-uniform hypergraphs. Our terminology follows that of [2]. A random r-uniform hypergraph H r (n; p) is an r-uniform hypergraph on n labeled vertices V = [n] = f1; : : : ; ng, in which every subset e ae V of size jej = r is chosen to be an edge of H randomly and independently with prob..