Rapid mixing for lattice colourings with fewer colours

DOI10.1088/1742-5468/2005/10/P10012zbMath1459.82023arXivcond-mat/0508737MaRDI QIDQ4968808

Frank Van Bussel, Mike Molloy, Moore, Cristopher, Demetrios Achlioptas

Publication date: 9 July 2019

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0508737

zbMATH Keywords

analysis of algorithms

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15)

Related Items

Proper -colorings of are Bernoulli ⋮ Structure and eigenvalues of heat-bath Markov chains ⋮ Sparse analytic hierarchy process: an experimental analysis ⋮ Finitary codings for spatial mixing Markov random fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric bounds for eigenvalues of Markov chains
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Comparison theorems for reversible Markov chains
• Internal diffusion-limited aggregation: parallel algorithms and complexity
• Antiferromagnetic Potts models on the square lattice: A high-precision Monte Carlo study
• A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models
• Improved bounds for sampling colorings
• Analyzing Glauber dynamics by comparison of Markov chains
• Markov Chain Algorithms for Planar Lattice Structures
• On Approximately Counting Colorings of Small Degree Graphs
• A more rapidly mixing Markov chain for graph colorings
• Random sampling of 3‐colorings in ℤ²
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields