## Abstract

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) ≤ 2crsr-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.

Original language | English (US) |
---|---|

Pages (from-to) | 377-390 |

Number of pages | 14 |

Journal | Random Structures and Algorithms |

Volume | 39 |

Issue number | 3 |

DOIs | |

State | Published - Oct 2011 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

## Keywords

- Average degree
- Euclidean Ramsey Theory
- Hypergraphs
- List coloring