Sampling colourings of the triangular lattice

DOI10.1002/RSA.20386MaRDI QIDQ2904597zbMATH OpenOpenAlexFDO

Authors Markus Jalsenius

Publication date 14 August 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

samplingMarkov chainscountingtriangular latticecolourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We show that the Glauber dynamics on proper 9-colourings of the triangular lattice is rapidly mixing, which allows for efficient sampling. Consequently, there is a fully polynomial randomised approximation scheme (FPRAS) for counting proper 9-colourings of the triangular lattice. Proper colourings correspond to configurations in the zero-temperature anti-ferromagnetic Potts model. We show that the spin system consisting of proper 9-colourings of the triangular lattice has strong spatial mixing. This implies that there is a unique infinite-volume Gibbs distribution, which is an important property studied in statistical physics. Our results build on previous work by Goldberg, Martin and Paterson, who showed similar results for 10 colours on the triangular lattice. Their work was preceded by Salas and Sokal's 11-colour result. Both proofs rely on computational assistance, and so does our 9-colour proof. We have used a randomised heuristic to guide us towards rigourous results.

Recommendations

• Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
• Random sampling of 3‐colorings in ℤ²
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Rapid mixing for lattice colourings with fewer colours
• On Approximately Counting Colorings of Small Degree Graphs

Cites work

• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID
• 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
• Combinatorial criteria for uniqueness of Gibbs measures
• Dobrushin Conditions and Systematic Scan
• Dobrushin Conditions for Systematic Scan with Block Dynamics
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Improved bounds for sampling colorings
• Mixing in time and space for lattice spin systems: A combinatorial view
• On Approximately Counting Colorings of Small Degree Graphs
• Random generation of combinatorial structures from a uniform distribution
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
• Very rapidly mixing Markov chains for \(2\Delta\)-colorings and for independent sets in a graph with maximum degree 4

Cited in

(7)

• scientific article; zbMATH DE number 2151247 (Why is no real title available?)
• Sampling on lattices with free boundary conditions using randomized extensions
• Sampling Eulerian orientations of triangular lattice graphs
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
• Rapid mixing for lattice colourings with fewer colours
• Random sampling of 3‐colorings in ℤ²

This page was built for publication: Sampling colourings of the triangular lattice

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