Asymptotically good list-colorings

The list-chromatic index, chi'(1)(H), of a hypergraph H is the least t such that for any assignment of t-sets S(A) to the edges A of H, there is a proper coloring sigma of H with sigma(A) is an element of S(A) for all A is an element of H. Let k be fixed and H a hypergraph having edges of size at most k and maximum degree D, and satisfying max{d(x, y): x, y distinct vertices of H} = o(D). Then chi'(1)(H)/D-->1 (D-->infinity). Thus if edge sizes are bounded and pairwise degrees are relatively small, we have asymptotic agreement of chi'(1) with its trivial lower bound, the maximum degree. The corresponding result for ordinary chromatic index is a theorem of Pippenger and Spencer (J. Combin. Theory Sei. A 51 (1989), 24-42). On the other hand, even for simple graphs, earlier work falls far short of deciding the asymptotic behavior of chi'(1). The ''guided-random'' method used in the proof is in the spirit of some earlier work and is thought to be of particular interest. One simple ingredient is a martingale inequality which ought to prove useful beyond the present context. (C) 1996 Academic Press, Inc.