Choosability in random hypergraphs

The choice number of a hypergraph H = (V, E) is the least integer s for whi ch, for every family of color lists P = {S(v): v is an element of V}, satis fying \S(v)\ = s for every v is an element of V, there exists a choice func tion f so that f(v) is an element of S(v) for every v is an element of V, a nd no edge of H is monochromatic under f. In this paper we consider the asy mptotic behavior of the choice number of a random k-uniform hypergraph H(k, n, p). Our main result states that for every k greater than or equal to 2 and for all values of the edge probability p = p(n) down to p = O(n(-k + 1) ) the ratio between the choice number and the chromatic number of H(k, n, p ) does not exceed k(1/(k - 1)) asymptotically. Moreover, for large values o f p, namely, when p greater than or equal to n(-(k - 1)2/(2k) + c) for an a rbitrary positive constant e, the choice number and the chromatic number of H(k, n, p) have almost surely the same asymptotic value. (C) 2001 Academic Press.