Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings

DOI10.1016/j.jda.2004.05.002zbMath1089.68135OpenAlexW2062105278MaRDI QIDQ1775018

Tomasz Łuczak, Eric Vigoda

Publication date: 4 May 2005

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2004.05.002

zbMATH Keywords

Monte Carlo methodMarkov chainrandomized algorithmcoloringtorpid mixing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Related Items

Connectedness of the graph of vertex-colourings ⋮ Sampling Eulerian orientations of triangular lattice graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison theorems for reversible Markov chains
• Antiferromagnetic Potts models on the square lattice: A high-precision Monte Carlo study
• A constrained Potts antiferromagnet model with an interface representation
• On Brooks' Theorem for Sparse Graphs
• Time-Dependent Statistics of the Ising Model