标题： 调色板稀疏化的渐近性 显示英文标题

标题： Asymptotics for Palette Sparsification

摘要： 结果表明，以下结论对每个$\varepsilon>0$均成立。 对于最大度数为$D$的$G$顶点图$n$，其“列表”$L_v$（$v \in V(G)$）独立且均匀地从$\{1, ..., D+1\}$的 ($(1+\varepsilon)\ln n$)-子集中选取，当$D \to \infty$趋于无穷时，\[ G \text{ admits a proper coloring } \sigma \text{ with } \sigma_v \in L_v \forall v \]的概率趋于 1。 这是近期 Assadi、Chen 和 Khanna 的“调色板稀疏化”定理的一个渐近最优版本。 显示英文摘要

摘要： It is shown that the following holds for each $\varepsilon>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+\varepsilon)\ln n$)-subsets of $\{1, ..., D+1\}$, \[ G \text{ admits a proper coloring } \sigma \text{ with } \sigma_v \in L_v \forall v \] with probability tending to 1 as $D \to \infty$. This is an asymptotically optimal version of a recent "palette sparsification" theorem of Assadi, Chen, and Khanna.