Choosability in Random Hypergraphs

The choice number of a hypergraph H=(V, E) is the least integer s for which, for every family of color lists S={S(v): v∈V}, satisfying |S(v)|=s for every v∈V, there exists a choice function f so that f(v)∈S(v) for every v∈V, and no edge of H is monochromatic under f. In this paper we consider the asymptotic behavior of the choice number of a random k-uniform hypergraph H(k, n, p). Our main result states that for every k⩾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 k1/(k−1) asymptotically. Moreover, for large values of p, namely, when p⩾n−(k−1)2/(2k)+ε for an arbitrary positive constant ε, the choice number and the chromatic number of H(k, n, p) have almost surely the same asymptotic value.