Hypergraph list coloring and Euclidean Ramsey theory

A hypergraph is simple if it has no two edges sharing more than a single vertex. It is s ‐list colorable (or s ‐choosable) if for any assignment of a list of s colors to each of its vertices, there is a vertex coloring assigning to each vertex a color from its list, so that no edge is monochromatic. We prove that for every positive integer r , there is a function d r ( s ) such that no r ‐uniform simple hypergraph with average degree at least d r ( s ) is s ‐list‐colorable. This extends a similar result for graphs, due to the first author, but does not give as good estimates of d r ( s ) as are known for d 2 ( s ), since our proof only shows that for each fixed r ≥ 2, d r ( s ) ≤ 2   c   r s   r −1 .We use the result to prove that for any finite set of points X in the plane, and for any finite integer s , one can assign a list of s distinct colors to each point of the plane so that any coloring of the plane that colors each point by a color from its list contains a monochromatic isometric copy of X . © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011