Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings (Q1775018): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jda.2004.05.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2062105278 / rank | |||
Normal rank |
Revision as of 02:29, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings |
scientific article |
Statements
Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings (English)
0 references
4 May 2005
0 references
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)\).
0 references
randomized algorithm
0 references
Markov chain
0 references
Monte Carlo method
0 references
coloring
0 references
torpid mixing
0 references