Asymptotically good list-colorings

The list-chromatic index, χ′l(ℋ), of a hypergraph ℋ is the least t such that for any assignment of t-sets S(A) to the edges A of ℋ, there is a proper coloring σ of ℋ with σ(A) ∈ S(A) for all A ∈ ℋ. THEOREM. Let k be fixed and ℋ a hypergraph having edges of size at most k and maximum degree D, and satisfying max{d(x, y): x, y distinct vertices of ℋ} = o(D). Then χ′l(ℋ)/D → 1 (D → ∞). Thus if edge sizes are bounded and pairwise degrees are relatively small, we have asymptotic agreement of χ′l 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 Ser. A 51 (1989), 24-42). On the other hand, even for simple graphs, earlier work falls far short of deciding the asymptotic behavior of χ′l. 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.