树上着色的强空间混合性及其算法应用

《Journal of the ACM》：Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

　　

摘要AI摘要

要查看此AI生成的摘要，您必须拥有高级访问权限。

了解更多登录

摘要

摘要

强空间混合（Strong Spatial Mixing, SSM）是统计物理、概率论和理论计算机科学中吉布斯分布相关衰减的一个重要量化概念。一个长期存在的猜想是：在Δ-正则树上，适当的q-着色均匀分布，只要q ≥ Δ + 1，就具有SSM性质。此外，人们普遍相信，只要SSM在有界度树上以q种颜色成立，就可以通过简单的马尔可夫链算法获得所有有界度图上q-着色的有效采样器。令人惊讶的是，这样一个基本问题即使在树上仍然未解，但这再次凸显了我们在随机着色方面仍有许多未知之处。

在本文中，我们证明了以下结果：

(1) 对于任意Δ ≥ 3，只要q ≥ Δ + 3，最大度为Δ的树上随机q-着色就具有SSM性质。因此我们几乎完全解决了上述猜想。我们的结果大幅改进了此前最佳界限，此前需要q ≥ 1.59Δ + γ^*，其中γ^* > 0为绝对常数。

(2) 对于任意Δ ≥ 3和$g={\mathrm{\Omega }}_{\mathrm{\Delta }}(1)$，我们证明了在最大度为Δ、围长为g的图上，只要q ≥ Δ + 3，q-着色的Glauber动力学的最优混合性质。我们的方法基于一种新的通用归约方法，将大围长图上的谱独立性归约为树上的SSM，该方法本身具有独立的研究价值。

利用相同的技术，我们还证明了反铁磁性Potts模型在树上弱空间混合（WSM）的近似最优界限，WSM是与SSM密切相关的概念。

AI摘要

AI生成摘要（实验性）

此摘要由自动化工具生成，未经文章作者撰写或审核。它旨在支持发现、帮助读者评估相关性，并协助相邻研究领域的读者理解该工作。它旨在补充作者提供的摘要，后者仍然是论文的主要摘要。完整文章仍然是权威的记录版本。点击此处了解更多。

点击此处对此摘要的准确性、清晰度和有用性进行评论。这将有助于改进和未来的重新生成版本。

要查看此AI生成的通俗语言摘要，您必须拥有高级访问权限。