论文标题
完美采样$ k \ geq（8/3 +o（1））δ$ - 色
Perfectly Sampling $k\geq (8/3 +o(1))Δ$-Colorings in Graphs
论文作者
论文摘要
我们提出了一种随机算法，该算法将最高$ $ $δ$的$ n $顶点上的无向图$ g $和许多颜色$ k \ geq（8/3 +o_Δ（1））Δ$和返回 - 预期的时间$ \ tilde $ \ tilde {o}（nδ^^$ g。完美地统一了$ g $的所有合适的$ k $颜色。值得注意的是，我们的采样器以$ k =3δ$打破了障碍物，在最近的Bhandari和Chakraborty [STOC 2020]中遇到的障碍。我们还素描如何修改我们的方法，以放宽$ k $的限制到$ k \ geq（8/3-ε_0）δ$的绝对常数$ε_0> 0 $。 就像在Bhandari和Chakraborty的工作以及Huber的开创性工作[Stoc 1998]一样，我们的采样器基于过去的耦合[Propp＆Wilson，Random Struct。算法，1995]和边界链方法[Huber，Stoc 1998; Häggström＆Nelander，Scand。 J. Statist。，1999]。我们的创新包括一个新型的边界链常规，灵感来自Jerrum对Glauber动力学的分析[Random Struct。算法，1995年]，以及使用算法Lovász局部引理的界限的预处理程序[Moser＆Tardos，J.Acm，2010]。
We present a randomized algorithm which takes as input an undirected graph $G$ on $n$ vertices with maximum degree $Δ$, and a number of colors $k \geq (8/3 + o_Δ(1))Δ$, and returns -- in expected time $\tilde{O}(nΔ^{2}\log{k})$ -- a proper $k$-coloring of $G$ distributed perfectly uniformly on the set of all proper $k$-colorings of $G$. Notably, our sampler breaks the barrier at $k = 3Δ$ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also sketch how to modify our methods to relax the restriction on $k$ to $k \geq (8/3 - ε_0)Δ$ for an absolute constant $ε_0 > 0$. As in the work of Bhandari and Chakraborty, and the pioneering work of Huber [STOC 1998], our sampler is based on Coupling from the Past [Propp&Wilson, Random Struct. Algorithms, 1995] and the bounding chain method [Huber, STOC 1998; Häggström&Nelander, Scand. J. Statist., 1999]. Our innovations include a novel bounding chain routine inspired by Jerrum's analysis of the Glauber dynamics [Random Struct. Algorithms, 1995], as well as a preconditioning routine for bounding chains which uses the algorithmic Lovász Local Lemma [Moser&Tardos, J.ACM, 2010].
