论文标题
通过光谱独立性快速混合着色
Rapid Mixing for Colorings via Spectral Independence
论文作者
论文摘要
Anari等人的光谱独立方法。 （2020年）利用了Alev和Lau（2020）高维膨胀物的最新结果，并为在加权独立集中定义的硬核模型建立了Glauber动力学的快速混合。我们开发着色素的光谱独立方法，并为相应的计数/采样问题获得新的算法结果。 令$α^*\大约1.763 $表示解决方案$ \ exp（1/x）= x $，让$α>α^*$。我们证明，对于任何无三角形的图$ g =（v，e）$，最高度$δ$，对于所有$ q \geqαδ+1 $，Glauber Dynamics的混合时间$ q $ -olorings in $ n = | v | $ in polynomial in $ n = | v | $，具有$ $ $ $δ$和$δ$的指数。相比之下，以类似$ q $（$δ$渐近的范围）持有的着色结果，但有较大的周长要求或多项式指数依赖于$δ$和$ q $（指数级）的运行时间。使用光谱独立方法研究着色的另一个特征是，它避免了由耦合参数或传递到复杂平面引起的先前方法中的许多技术并发症。运行时间的关键改进基于相对简单的组合参数，然后将其转换为光谱范围。
The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber dynamics for the hard-core model defined on weighted independent sets. We develop the spectral independence approach for colorings, and obtain new algorithmic results for the corresponding counting/sampling problems. Let $α^*\approx 1.763$ denote the solution to $\exp(1/x)=x$ and let $α>α^*$. We prove that, for any triangle-free graph $G=(V,E)$ with maximum degree $Δ$, for all $q\geqαΔ+1$, the mixing time of the Glauber dynamics for $q$-colorings is polynomial in $n=|V|$, with the exponent of the polynomial independent of $Δ$ and $q$. In comparison, previous approximate counting results for colorings held for a similar range of $q$ (asymptotically in $Δ$) but with larger girth requirement or with a running time where the polynomial exponent depended on $Δ$ and $q$ (exponentially). One further feature of using the spectral independence approach to study colorings is that it avoids many of the technical complications in previous approaches caused by coupling arguments or by passing to the complex plane; the key improvement on the running time is based on relatively simple combinatorial arguments which are then translated into spectral bounds.
