Strong Spatial Mixing with Fewer Colors for Lattice Graphs

DOI10.1137/S0097539704445470zbMath1091.60013OpenAlexW2113770815MaRDI QIDQ5470700

Leslie Ann Goldberg, Russell Martin, Mike S. Paterson

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539704445470

zbMATH Keywords

spin systemantiferromagnetic Potts modelproper graph coloringrapid mixinglattice geometrystrong spatial mixingrecursive coupling construction

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Related Items (21)

Spatial mixing and the connective constant: optimal bounds ⋮ The topological strong spatial mixing property and new conditions for pressure approximation ⋮ Sampling colourings of the triangular lattice ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing ⋮ Perfect sampling from spatial mixing ⋮ Correlation decay and deterministic FPTAS for counting colorings of a graph ⋮ Unnamed Item ⋮ Rigidity of proper colorings of \(\mathbb{Z}^d \) ⋮ Online Edge Coloring via Tree Recurrences and Correlation Decay ⋮ Improved mixing condition on the grid for counting and sampling independent sets ⋮ Strong spatial mixing in homomorphism spaces ⋮ On systematic scan for sampling H-colorings of the path ⋮ Rapid mixing of Gibbs sampling on graphs that are sparse on average ⋮ A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID ⋮ Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice ⋮ Finitary codings for spatial mixing Markov random fields ⋮ Randomly coloring constant degree graphs ⋮ A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold ⋮ Dynamic Sampling from Graphical Models ⋮ Strong spatial mixing of list coloring of graphs

This page was built for publication: Strong Spatial Mixing with Fewer Colors for Lattice Graphs