Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings (Q1775018): Difference between revisions

As in the related paper by \textit{E. Vigoda} [J.\ Math.\ Phys.\ 41, 1555--1569 (2000; Zbl 0978.60083)] the authors sample uniformly at random from the set of proper vertex \(k\)-colourings of a graph. Two algorithms are considered: \textit{R. J. Glauber} dynamics [J.\ Math.\ Phys.\ 4, 294--307 (1963; Zbl 0145.24003)] and the WSK algorithm introduced by \textit{Wang, Swendsen} and \textit{Kotecký} [Phys.\ Rev.\ Lett.\ 63, 109--112 (1989) and Phys.\ Rev.\ B 42, 2465--2474 (1990)]. Such an algorithm is rapidly mixing if the mixing time of the Markov chain is polynomial in the number \(n\) of vertices, and torpidly mixing if it is exponential in \(n^{\epsilon}\) for some \(\epsilon>0\). There is an infinite family of 3-colourable planar graphs such that the WSK algorithm is torpidly mixing for every fixed \(k \geq 3\). There is a constant \(k_0\) and an infinite family of graphs with maximum degree \(\Delta\) such that the WSK algorithm is not ergodic for every \(k\) with \(k_0 \leq k \leq \Delta/2\). And there is an infinite family of bipartite graphs with maximum degree \(\Delta\) such that the WSK algorithm is torpidly mixing when \(3 \leq k < \Delta/(20\log\Delta)\).