论文标题
从布尔域之外的光谱独立性快速混合
Rapid mixing from spectral independence beyond the Boolean domain
论文作者
论文摘要
我们将光谱独立性的概念（由Anari，Liu和Oveis Gharan [alo20]）从布尔域引入到一般离散域。该属性表征具有有限相关性的分布，这意味着相应的Glauber动力学正在迅速混合。 作为一个具体的应用，我们表明，用于取样适当$ q $彩色的Glauber动态在多项式时间中混合了无三角形图的家族，最高度$δ$提供$ q \ ge（α^*+Δ$任何常数。这是在该制度中使用可能无限$δ$采样适当$ q $颜色的第一种有效算法。我们建立光谱独立性的主要工具是Goldberg，Martin和Paterson [GMP05]的递归耦合。
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper $q$-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree $Δ$ provided $q\ge (α^*+δ)Δ$ where $α^*\approx 1.763$ is the unique solution to $α^*=\exp(1/α^*)$ and $δ>0$ is any constant. This is the first efficient algorithm for sampling proper $q$-colourings in this regime with possibly unbounded $Δ$. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].
