Systematic scan for sampling colorings

DOI10.1214/105051605000000683zbMath1095.60024arXivmath/0603323OpenAlexW2014487253WikidataQ56323916 ScholiaQ56323916MaRDI QIDQ2494577

Leslie Ann Goldberg, Mark R. Jerrum, Martin Dyer

Publication date: 29 June 2006

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0603323

zbMATH Keywords

graph homomorphismsPotts modelGlauber dynamicsmixing timespin systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Related Items

Randomly coloring planar graphs with fewer colors than the maximum degree, Fixed Precision MCMC Estimation by Median of Products of Averages, Can extra updates delay mixing?, What can be sampled locally?, Hit and run as a unifying device, A general lower bound for mixing of single-site dynamics on graphs, On systematic scan for sampling H-colorings of the path, A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID, Frozen colourings of bounded degree graphs, Matrix norms and rapid mixing for spin systems, The Glauber dynamics for edge‐colorings of trees, Dobrushin Conditions and Systematic Scan, Frozen (Δ + 1)-colourings of bounded degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Geometric bounds for eigenvalues of Markov chains
• Markov chain comparison
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Comparison theorems for reversible Markov chains
• Mixing times of lozenge tiling and card shuffling Markov chains
• A uniqueness condition for Gibbs measures, with application to the 2- dimensional Ising antiferromagnet
• Coordinate selection rules for Gibbs sampling
• Convergence properties of the Gibbs sampler for perturbations of Gaussians
• Weighted sums of certain dependent random variables
• An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings
• On Markov Chains for Randomly H-Coloring a Graph
• Markov Chain Algorithms for Planar Lattice Structures
• On Counting Independent Sets in Sparse Graphs
• Some Inequalities for Reversible Markov Chains
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• Random sampling of 3‐colorings in ℤ²
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Time-Dependent Statistics of the Ising Model
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques