Advanced Search  Browse by Discipline  Scientific Societies
E-print Alerts  Add E-prints  E-print Network    Advanced Search
   Hypergraph list coloring and Euclidean Ramsey Theory Alexandr
Kostochka  Summary: Hypergraph list coloring and Euclidean
Ramsey Theory Noga Alon Alexandr Kostochka April 28, 2010 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 dr(s) such that no
r-uniform simple hypergraph with average degree at least dr(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
dr(s) as are known for d2(s), since our proof only shows that
for each fixed r 2, dr(s) 2crsr-1 . We use the result to prove
that for any finite