Sampling Random Colorings of Sparse Random Graphs
Sampling Random Colorings of Sparse Random Graphs
复制标题
DOI：
10.1137/1.9781611975031.115
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
Charilaos Efthymiou;Thomas P. Hayes;Daniel Stefankovic;Eric Vigoda
中科院分区：
文献类型：
--
作者：
Charilaos Efthymiou;Thomas P. Hayes;Daniel Stefankovic;Eric Vigoda
我们研究称为格劳伯动力学的单点马尔可夫链的混合特性，用于对常数 $d$ 的稀疏随机图 $G(n,d/n)$ 的 $k$ 着色进行采样。一般图最著名的快速混合结果是输入图$G$的最大度$\Delta$，并且当所有$G$的$k>11\Delta/6$时成立。当周长 $\geq 5$ 和 $\Delta$ 足够大的图形 $k>\alpha\Delta$ 时，改进结果成立，其中 $\alpha\approx 1.7632\ldots$ 是 $\alpha=\exp(1/\alpha)$ 的根；通过更强的周长和最大度数假设进一步改进常数 $\alpha$ 保持。对于稀疏随机图，最大度是 $n$ 的函数，目标是获得预期度 $d$ 的结果。以下 $G(n,d/n)$ 的快速混合结果在选择足够大的常数 ~$d$ 的随机图时具有很高的概率。 Mossel 和 Sly (2009) 证明了常数 $k$ 的快速混合，而 Efthymiou (2014) 将其改进为 $k$ 与 $d$ 呈线性关系。 Yin 和Zhang (2016) 使用非 MCMC 方法将该条件改进为 $k>3d$。在这里，我们证明当 $k>\alpha d$ 时快速混合，其中 $\alpha\approx 1.7632\ldots$ 与上面的常数相同。此外，我们获得了格劳伯动力学的 $O(n^{3})$ 混合时间，而在之前的快速混合结果中，指数是 $d$ 中的递增函数。与之前随机图的结果一样，我们的证明分析了适当定义的块动力学以“隐藏”高度顶点。我们改进方法的一个新方面是利用所谓的局部均匀性特性来分析块动力学。为了分析“老化”阶段，我们证明了大区块中传播的分歧数量的集中不等式。
We study the mixing properties of the single-site Markov chain known as the Glauber dynamics for sampling $k$-colorings of a sparse random graph $G(n,d/n)$ for constant $d$. The best known rapid mixing results for general graphs are in terms of the maximum degree $\Delta$ of the input graph $G$ and hold when $k>11\Delta/6$ for all $G$. Improved results hold when $k>\alpha\Delta$ for graphs with girth $\geq 5$ and $\Delta$ sufficiently large where $\alpha\approx 1.7632\ldots$ is the root of $\alpha=\exp(1/\alpha)$; further improvements on the constant $\alpha$ hold with stronger girth and maximum degree assumptions. For sparse random graphs the maximum degree is a function of $n$ and the goal is to obtain results in terms of the expected degree $d$. The following rapid mixing results for $G(n,d/n)$ hold with high probability over the choice of the random graph for sufficiently large constant~$d$. Mossel and Sly (2009) proved rapid mixing for constant $k$, and Efthymiou (2014) improved this to $k$ linear in~$d$. The condition was improved to $k>3d$ by Yin and Zhang (2016) using non-MCMC methods. Here we prove rapid mixing when $k>\alpha d$ where $\alpha\approx 1.7632\ldots$ is the same constant as above. Moreover we obtain $O(n^{3})$ mixing time of the Glauber dynamics, while in previous rapid mixing results the exponent was an increasing function in $d$. As in previous results for random graphs our proof analyzes an appropriately defined block dynamics to "hide" high-degree vertices. One new aspect in our improved approach is utilizing so-called local uniformity properties for the analysis of block dynamics. To analyze the "burn-in" phase we prove a concentration inequality for the number of disagreements propagating in large blocks.