Strong spatial mixing and rapid mixing with five colours for the Kagome lattice

DOI10.1112/S1461157000001492zbMATH Open1232.05079arXivmath-ph/0701043OpenAlexW2963197402MaRDI QIDQ3091978FDOQ3091978

Markus Jalsenius

Publication date: 15 September 2011

Published in: LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Abstract: We consider proper 5-colourings of the kagome lattice. Proper q-colourings correspond to configurations in the zero-temperature q-state anti-ferromagnetic Potts model. Salas and Sokal have given a computer assisted proof of strong spatial mixing on the kagome lattice for q>=6 under any temperature, including zero temperature. It is believed that there is strong spatial mixing for q>=4. Here we give a computer assisted proof of strong spatial mixing for q=5 and zero temperature. It is commonly known that strong spatial mixing implies that there is a unique infinite-volume Gibbs measure and that the Glauber dynamics is rapidly mixing. We give a proof of rapid mixing of the Glauber dynamics on any finite subset of the vertices of the kagome lattice, provided that the boundary is free (not coloured). The Glauber dynamics is not necessarily irreducible if the boundary is chosen arbitrarily for q=5 colours. The Glauber dynamics can be used to uniformly sample proper 5-colourings. Thus, a consequence of rapidly mixing Glauber dynamics is that there is fully polynomial randomised approximation scheme for counting the number of proper 5-colourings.

Full work available at URL: https://arxiv.org/abs/math-ph/0701043

Recommendations

• Rapid mixing for lattice colourings with fewer colours
• Sampling colourings of the triangular lattice
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Mixing of the Glauber dynamics for the ferromagnetic Potts model

zbMATH Keywords

Gibbs measureGlauber dynamicsKagome latticestrong spatial mixing5-colourings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Classical equilibrium statistical mechanics (general) (82B05)

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Geometric bounds for eigenvalues of Markov chains
• Gibbs measures and phase transitions
• Improved bounds for sampling colorings
• 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
• Comparison theorems for reversible Markov chains
• Analyzing Glauber dynamics by comparison of Markov chains
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Combinatorial criteria for uniqueness of Gibbs measures
• Markov chain comparison
• Mixing in time and space for lattice spin systems: A combinatorial view
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Very rapidly mixing Markov chains for \(2\Delta\)-colorings and for independent sets in a graph with maximum degree 4

Cited In (4)

• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Finitary codings for spatial mixing Markov random fields
• Sampling colourings of the triangular lattice

This page was built for publication: Strong spatial mixing and rapid mixing with five colours for the Kagome lattice

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