Hypergraph list coloring and Euclidean Ramsey theory

Noga Alon, Alexandr Kostochka

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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 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 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 languageEnglish (US)
Pages (from-to)377-390
Number of pages14
JournalRandom Structures and Algorithms
Volume39
Issue number3
DOIs
StatePublished - Oct 2011
Externally publishedYes

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

Fingerprint Dive into the research topics of 'Hypergraph list coloring and Euclidean Ramsey theory'. Together they form a unique fingerprint.

Cite this