Coloring Hypergraphs from Random Lists

Abstract

We introduce and study problems on coloring hypergraphs from randomly chosen color lists. Let $H=H(n)$ be an $r$-uniform hypergraph on $n$ vertices where each vertex is assigned a list of colors of size $k$ chosen independently and uniformly at random from all $k$-subsets of a set of colors of size $\sigma=\sigma(n)$. We prove a number of results concerning the probability of the existence of a list coloring of $H$ from the random lists. One such result is that for fixed $r$, $k$ and growing $n$, if $\sigma = \omega\left(n^{\frac{1}{k^2(r-1)}}\Delta^{\frac{1}{k(r-1)}}\right)$, and $H(n)$ has maximum degree $\Delta = O\left(n^{\frac{k-1}{k^2(k^2+k) r(r - 1)}}\right)$, then with probability tending to $1$, as $n \to \infty$, $H$ has a proper coloring from the random lists. The bound on $\sigma$ is tight. We also prove analogous results for hypergraphs of bounded maximum degree and complete hypergraphs where the size $k$ of the random lists either is constant or an increasing function of $n$. In particular, for the complete $r$-uniform hypergraph $K_n^r$, if $\sigma = \lceil n/(r-1) \rceil$, then the property of being colorable from random lists of size $k$ has a sharp threshold at $k(n) = \frac{\log n}{r-1}$.