Palette Sparsification for General Uniform Hypergraphs

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 $\mathrm{\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 {\mathrm{\Delta }}^{1\mathrm{/}(r-1)}\rceil$. The $\sqrt{\log n}$ dependence is asymptotically tight.