MATH Seminar
| Title: List Colorings of Dense Hypergraphs |
|---|
| Seminar: Combinatorics |
| Speaker: Alexander Kostochka of The University of Illinois at Urbana-Champaign |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2011-02-25 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: The {\em list chromatic number} $\chi_{\ell}(G)$ of a hypergraph $G=(V,E)$ is the minimum integer $s$ such that for every assignment of a list $L_v$ of $s$ colors to each vertex $v$ of $G$, there is a vertex coloring of $G$ in which the color of each vertex is in its list and there are no monochromatic edges. In nineties, Alon showed that the list chromatic number of every graph with average degree $d$ is at least $(0.5-o(1))\log_2 d$. In this talk, we discuss two related results by Alon and the speaker on list coloring of uniform hypergraphs. The first of them states that for $r\geq 3$, every $r$-uniform hypergraph in which at least half of the $(r-1)$-vertex subsets are contained in at least $d$ edges has list chromatic number at least $ \frac{\ln d}{(20r)^3}$. When $r$ is fixed, this is sharp up to a constant factor. In particular, $n$-vertex $r$-uniform hypergraphs may have average degree about $(n/r)^{r-2}$ and still be $2$-list-colorable. The second result concerns {\em simple} Â hypergraphs, that is, the hypergraphs in which any two distinct edges have at most one vertex in common. It is proved that for every fixed $r$, all $r$-uniform hypergraphs with high average degree have ``high" list chromatic number. The result implies 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$. |
See All Seminars