《Discrete Mathematics》：Palette sparsification for graphs with sparse neighborhoods
编辑推荐：
Assadi、Chen和Khanna的一个开创性调色板稀疏化（palette sparsification）结果表明，在每一个最大度为Δ的n顶点图中，从{1,…,Δ+1}中为每个顶点采样Θ(log n)种颜色几乎必然允许从采样颜色中获得一个正常着色。Alon和
Assadi、Chen和Khanna的一个开创性调色板稀疏化（palette sparsification）结果表明，在每一个最大度为Δ的n顶点图中，从{1,…,Δ+1}中为每个顶点采样Θ(log n)种颜色几乎必然允许从采样颜色中获得一个正常着色。Alon和Assadi扩展了这项工作，证明了无三角形图的O(Δ/log Δ)-着色的类似结果。除了从组合学角度看是有趣的结果外，他们的结果在不同计算模型中的图着色算法设计中有各种应用。在本工作中，研究人员关注局部稀疏图，即具有稀疏邻域的图。研究人员称图G=(V,E)是k-局部稀疏的，如果对于每个顶点v∈V，子图G[N(v)]至多包含k条边。Alon、Krivelevich和Sudakov的一个著名结果表明此类图是O(Δ/log(Δ/k))-可着色的。对于任意α∈(0,1)和k?Δ^{2α}，设G是一个k-局部稀疏图。对于q=Θ(Δ/log(Δ^{α}/k))，研究人员表明每个顶点采样O(Δ^{α}+log n)种颜色足以从采样颜色中获得G的一个正常q-着色。设置k=1可恢复上述Alon和Assadi关于无三角形图的结果。研究人员在更一般的对应着色（correspondence coloring）设置中建立了这一结果，其中结构约束施加在对应覆盖（correspondence cover）上而非底层图上。这一概念近年来引起了广泛兴趣。证明中的一个关键要素是一个命题，该命题确定了对应覆盖H上使G允许正常H-着色的充分条件。该结果改进了Anderson、Kuchukova和作者最近的工作，并具有独立的研究价值。
研究背景方面，图着色是组合数学与理论计算机科学的核心问题之一。经典贪心算法可在O(nΔ)时间内获得最大度为Δ的图的(Δ+1)-着色，但面对大规模图数据时，即使在流式模型、单机内存受限、多机并行等场景下，处理全部边集的计算代价仍然过高，这促使研究人员设计亚线性算法。Assadi、Chen和Khanna首次研究了(Δ+1)-着色问题的亚线性算法，其核心是一个调色板稀疏化定理：从[Δ+1]中为每个顶点独立均匀采样Θ(log n)种颜色构成列表，则图几乎必然允许从这些列表中正常着色。该结果的意义在于将着色问题归约为边数更少的冲突图上的列表着色问题。此后，Kahn和Kenney将采样量收紧至(1+o(1))log n。Alon和Assadi进一步证明了无三角形图在q=9Δ/log(Δ^{α})时的调色板稀疏化结果，Anderson、Bernshteyn和Dhawan则将之推广到K_{1,s,t}-自由图。然而，对于Alon、Krivelevich和Sudakov所刻画的k-局部稀疏图——其色数为O(Δ/log(Δ/k))——此前尚无调色板稀疏化结果。本文正是为填补这一空白而开展研究。
研究人员证明了本文的主要定理（Theorem 1.4）：对任意ε>0和γ∈(0,1)，存在常数C>0，使得对所有α∈(0,1)存在Δ?，当Δ≥Δ?、1≤k≤Δ^{2αγ}、q=4(1+γ+ε)Δ/log(Δ^{α}/k)、s≥Δ^{α}+C log n时，对n顶点k-局部稀疏图G的每个顶点独立均匀采样[q]中大小为s的集合L(v)，则以至少1?1/n的概率存在正常着色φ满足φ(v)∈L(v)。这是该问题的首个调色板稀疏化定理；取k=1并令γ任意小可恢复K_{1,s,t}-自由图的结果并改进q的常数因子。该定理实际上在对应着色设置下成立（Theorem 2.4、Theorem 2.5），约束施加于对应覆盖。证明的关键是Proposition 1.5（及其对应着色版本Proposition 2.3）：在颜色-度（color–degree）设定下，若每个顶点v和颜色c满足deg_L(v,c)≤d、|E(G[N_L(v,c)])|≤k且|L(v)|≥4(1+γ)d/log(d/k)，则G允许正常L-着色。该命题改进了Anderson、Kuchukova和作者此前结果中k的范围与列表下界常数。
技术方法上，研究人员主要采用以下关键手段：（1）将调色板稀疏化归约为颜色-度设定下的列表/对应着色问题，通过对采样列表进一步筛选，保留颜色度不超过?(Δ^{α})的颜色构成新列表L′(v)，并验证其满足Proposition 1.5的条件；（2）利用负相关随机变量的Chernoff型不等式（Theorem 2.7，Panconesi–Srinivasan）界定|L(v)?L′(v)|的规模；（3）在Proposition 1.5的证明中采用R?dl nibble方法的一个变体，即Wasteful Coloring Procedure，迭代地构造部分对应着色并缩小列表；（4）运用Lovász Local Lemma完成迭代终止后的收尾着色（Proposition 4.1）。本研究为理论证明，不涉及样本队列或实验数据。
研究结果方面，第一，调色板稀疏化定理（Theorem 2.5/Theorem 1.4）：通过Lemma 3.1证明对每个顶点v，筛选后的集合S′(v)以高概率满足|S′(v)|≥(1?γ*)s，进而验证筛选后的对应覆盖H′满足Proposition 2.3的全部条件，从而得出采样O(Δ^{α}+log n)种颜色即足以获得正常q-着色。第二，颜色-度设定下的列表着色命题（Proposition 1.5）：通过对Wasteful Coloring Procedure输出的"良性"分析，证明在颜色度、局部稀疏性与列表规模三个条件下图允许正常列表着色，该结果具有独立价值。第三，对应着色版本（Proposition 2.3）：将上述命题推广到对应覆盖上，把此前Theorem 2.2中k的范围从k≤d^{1/5}扩展至k≤d^{2γ}，并将列表下界常数从8改进为4.4（取γ=1/10）。第四，Wasteful Coloring Procedure的"良性"输出引理（Lemma 4.2）：通过Lemma 4.4、Lemma 4.5、Lemma 4.8、Lemma 4.10分别控制保留颜色数、保留边数期望、保留且未着色边数以及参数δ′(v)，结合Lovász Local Lemma证明存在使d′/?′显著下降的部分着色。第五，迭代终止（Lemma 4.11、Lemma 4.12）：证明参数序列在i*≤?16μ log(d/k)/log log(d/k)?步内达到d_{i*}≤?_{i*}/100，此时列表规模至少为对应覆盖最大度的8倍，由Proposition 4.1完成着色。
讨论部分，作者指出本文结果适用于k?Δ2的范围；当k=Θ(Δ2)时最坏情形为完全图，问题退化为已被广泛研究的(Δ+1)-着色调色板稀疏化，而Proposition 1.5的证明要求k?d2，故如何将结果扩展到全部1≤k≤(Δ2)范围尚不清晰（Question 1）。作者还提出两个未来方向：其一，针对(k,r)-局部稀疏图（每个邻域子图至多含k个K_r副本）的色数上界O(Δ/log Δ · max{r log log Δ, log(k/r)})，能否获得相应的调色板稀疏化结果，即使k=1时亦未知（Question 2）；其二，Alon和Assadi曾研究(Δ+1)-着色的局部版本，即每个顶点从[deg(v)+1]中取色，能否将本文主要结果推广到局部设定，该问题即使对无三角形图也未知（Question 3）。研究结论部分译为：在本工作中，研究人员考虑了最大度为Δ的k-局部稀疏图的O(Δ/log(Δ/k))-着色问题的调色板稀疏化。在实现这一目标的过程中，研究人员在颜色-度设定下为局部稀疏图的列表着色（及对应着色）提供了改进的界，这具有独立的研究价值。
