Sampling colourings of the triangular lattice
From MaRDI portal
Publication:2904597
DOI10.1002/RSA.20386zbMATH Open1245.05049arXiv0706.0489OpenAlexW2021813581MaRDI QIDQ2904597FDOQ2904597
Authors: Markus Jalsenius 
Publication date: 14 August 2012
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0706.0489
Recommendations
Cites Work
- Random generation of combinatorial structures from a uniform distribution
- Title not available (Why is that?)
- 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
- Combinatorial criteria for uniqueness of Gibbs measures
- Mixing in time and space for lattice spin systems: A combinatorial view
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
- Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
- Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2
- A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID
- On Approximately Counting Colorings of Small Degree Graphs
- Dobrushin Conditions and Systematic Scan
- Very rapidly mixing Markov chains for \(2\Delta\)-colorings and for independent sets in a graph with maximum degree 4
- Dobrushin Conditions for Systematic Scan with Block Dynamics
Cited In (7)
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
- Random sampling of 3‐colorings in ℤ2
- Title not available (Why is that?)
- Sampling Eulerian orientations of triangular lattice graphs
- Rapid mixing for lattice colourings with fewer colours
- Sampling on lattices with free boundary conditions using randomized extensions
- Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
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)
