Hypergraph list coloring and Euclidean Ramsey Theory
Hypergraph list coloring and Euclidean Ramsey Theory
-
Noga Alon, Tel-Aviv University and IAS
Fine Hall 224
A hypergraph is simple if it has no two edges sharing more than a single vertex. It is $s$-list colorable 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. I will discuss a recent result, obtained jointly with A. Kostochka, that asserts that for any $r$ and $s$ there is a finite $d=d(r,s)$ so that any $r$-uniform simple hypergraph with average degree at least $d(r,s)$ is not $s$-list-colorable. This extends a similar result for graphs, and has some geometric Ramsey-type consequences.