Rapid Mixing for Colorings via Spectral Independence
Rapid Mixing for Colorings via Spectral Independence
复制标题
DOI：
10.1137/1.9781611976465.94
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Zongchen Chen;Andreas Galanis;Daniel Stefankovic;Eric Vigoda
中科院分区：
文献类型：
--
作者：
Zongchen Chen;Andreas Galanis;Daniel Stefankovic;Eric Vigoda
Anari等人（2020）的光谱独立方法利用了Alev和Lau（2020）的高维扩展器的最新结果，并为加权独立集定义的硬核模型建立了快速混合的Glauber动力学。我们发展了光谱无关的着色方法，并获得了相应计数/采样问题的新算法结果。设$\alpha^*\approx 1.763$表示$\exp(1/x)=x$的解，设$\alpha>\alpha^*$。证明了对于任意最大度为$\Delta$的无三角形图$G=(V,E)$，对于所有$q\geq\alpha\Delta+1$, $q$ -着色剂的Glauber动力学混合时间在$n=|V|$是多项式，且多项式的指数与$\Delta$和$q$无关。相比之下，先前的着色近似计数结果适用于类似的$q$范围（在$\Delta$中渐近），但具有较大的周长要求或运行时间，其中多项式指数依赖于$\Delta$和$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 $\alpha^*\approx 1.763$ denote the solution to $\exp(1/x)=x$ and let $\alpha>\alpha^*$. We prove that, for any triangle-free graph $G=(V,E)$ with maximum degree $\Delta$, for all $q\geq\alpha\Delta+1$, the mixing time of the Glauber dynamics for $q$-colorings is polynomial in $n=|V|$, with the exponent of the polynomial independent of $\Delta$ and $q$. In comparison, previous approximate counting results for colorings held for a similar range of $q$ (asymptotically in $\Delta$) but with larger girth requirement or with a running time where the polynomial exponent depended on $\Delta$ 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.