Palette Sparsification for General Uniform Hypergraphs

Abstract

We prove a palette sparsification theorem for general $r$-uniform hypergraphs. For all sufficiently large $n$, every $r\ge 3$, and every $\alpha \ge 7.1$, we show that an $n$-vertex $r$-uniform hypergraph of maximum degree $\Delta$ is w.h.p. colorable from independently sampled lists of size $O(\sqrt{\log n})$ drawn from an ambient palette of size $\lceil \alpha {\Delta }^{1/(r-1)}\rceil$. The $\sqrt{\log n}$ dependence is asymptotically tight.

9 pages