Premium
Hypergraph list coloring and Euclidean Ramsey theory
Author(s) -
Alon Noga,
Kostochka Alexandr
Publication year - 2011
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20361
Subject(s) - combinatorics , hypergraph , vertex (graph theory) , mathematics , monochromatic color , euclidean geometry , simple (philosophy) , complete coloring , fractional coloring , finite set , discrete mathematics , integer (computer science) , graph , computer science , physics , geometry , mathematical analysis , philosophy , epistemology , line graph , graph power , optics , programming language
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