Asymptotics for Palette Sparsification

It is shown that the following holds for each $\epsilon >0$. For $G$ an $n$-vertex graph of maximum degree $D$ and “lists” $L_v$ ($v\in V(G)$) chosen independently and uniformly from the ($(1+\epsilon )\ln n$)-subsets of $\{1,\mathrm{.}\mathrm{.}\mathrm{.},D+1\}$, $$G\text{ admits a proper coloring }\sigma \text{ with }{\sigma }_v\in L_v\mathrm{\forall }v$$ with probability tending to 1 as $D\to \mathrm{\infty }$. This is an asymptotically optimal version of a recent “palette sparsification” theorem of Assadi, Chen, and Khanna.