Rapid mixing for lattice colourings with fewer colours

DOI10.1088/1742-5468/2005/10/P10012MaRDI QIDQ4968808zbMATH OpenFDO

Authors Mike Molloy, Cristopher Moore, Frank Van Bussel, D. 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

Coloring of graphs and hypergraphs (05C15) 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)

Abstract: We provide an optimally mixing Markov chain for 6-colorings of the square lattice on rectangular regions with free, fixed, or toroidal boundary conditions. This implies that the uniform distribution on the set of such colorings has strong spatial mixing, so that the 6-state Potts antiferromagnet has a finite correlation length and a unique Gibbs measure at zero temperature. Four and five are now the only remaining values of q for which it is not known whether there exists a rapidly mixing Markov chain for q-colorings of the square lattice.

Recommendations

• LATIN 2004: Theoretical Informatics
• Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
• Sampling colourings of the triangular lattice
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Random sampling of 3‐colorings in ℤ²

Cites work

• A more rapidly mixing Markov chain for graph colorings
• A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Analyzing Glauber dynamics by comparison of Markov chains
• Antiferromagnetic Potts models on the square lattice: A high-precision Monte Carlo study
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Comparison theorems for reversible Markov chains
• Geometric bounds for eigenvalues of Markov chains
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 1303576 (Why is no real title available?)
• scientific article; zbMATH DE number 1342087 (Why is no real title available?)
• scientific article; zbMATH DE number 2019632 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• Improved bounds for sampling colorings
• Internal diffusion-limited aggregation: parallel algorithms and complexity
• Markov chain algorithms for planar lattice structures
• On Approximately Counting Colorings of Small Degree Graphs
• Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields
• Random sampling of 3‐colorings in ℤ²
• Very rapidly mixing Markov chains for \(2\Delta\)-colorings and for independent sets in a graph with maximum degree 4

Cited in

(10)

• Sparse analytic hierarchy process: an experimental analysis
• Structure and eigenvalues of heat-bath Markov chains
• A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models
• Sampling colourings of the triangular lattice
• Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Mixing properties of colourings of the ℤ^d lattice
• LATIN 2004: Theoretical Informatics
• Proper -colorings of are Bernoulli
• Finitary codings for spatial mixing Markov random fields

This page was built for publication: Rapid mixing for lattice colourings with fewer colours

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968808)