The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.