Asymptotically Good List-Colorings

Thelist-chromatic index,χl′(H), of a hypergraph H is the leasttsuch that for any assignment oft-setsS(A) to the edgesAof H, there is a proper coloringσof H withσ(A)∈S(A) for allA∈H. m. Let k be fixed and H a hypergraph having edges of size at most k and maximum degree D, and satisfying[formula]Then[formula] f 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. A51(1989), 24–42). On the other hand, even for simple graphs, earlier work falls far short of deciding the asymptotic behavior ofχl′. uided-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.