The ACO Seminar (2023–2024)

We show that the following holds for each $\varepsilon >0$. For $G$ an $n$-vertex graph of maximum degree $D$, lists $S_v$ ($v\in V(G)$), and $L_v$ chosen uniformly from the subsets of $S_v$ of size $(1+\varepsilon)\ln n$ (independent of other choices), \[ \mathbb{P}(\mbox{$G$ admits a proper coloring $\sigma$ with $\sigma_v\in L_v$ $\forall v$}) \rightarrow 1 \,\,\,\, \mbox{(as $D\rightarrow \infty$).} \] When each $S_v= \{1,\ldots, D+1\}$ $\forall v$, this is an asymptotically optimal version of the ``palette sparsification'' theorem of Assadi, Chen and Khanna. Joint with Charles Kenney.