Strong Spatial Mixing with Fewer Colors for Lattice Graphs

DOI10.1137/S0097539704445470zbMath1091.60013MaRDI 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)

zbMATH Keywords

spin system; antiferromagnetic Potts model; proper graph coloring; rapid mixing; lattice geometry; strong spatial mixing; recursive coupling construction

Mathematics Subject Classification ID

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

60C05: Combinatorial probability

60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

05C15: Coloring of graphs and hypergraphs

68W20: Randomized algorithms

Related Items

Correlation decay and deterministic FPTAS for counting colorings of a graph, Sampling colourings of the triangular lattice, On systematic scan for sampling H-colorings of the path, Rapid mixing of Gibbs sampling on graphs that are sparse on average, Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice, A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID