Phase coexistence and torpid mixing in the 3-coloring model on Z^d

DOI10.1137/12089538XMaRDI QIDQ5499734zbMATH OpenOpenAlexFDO

Authors David Galvin, Dana Randall, Gregory B. Sorkin, J. Kahn

Publication date 31 July 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

3-coloringPeierls argumentphase coexistencePotts modeltorpid mixing

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: We show that for all sufficiently large d, the uniform proper 3-coloring model (in physics called the 3-state antiferromagnetic Potts model at zero temperature) on Z^d admits multiple maximal-entropy Gibbs measures. This is a consequence of the following combinatorial result: if a proper 3-coloring is chosen uniformly from a box in Z^d, conditioned on color 0 being given to all the vertices on the boundary of the box which are at an odd distance from a fixed vertex v in the box, then the probability that v gets color 0 is exponentially small in d. The proof proceeds through an analysis of a certain type of cutset separating v from the boundary of the box, and builds on techniques developed by Galvin and Kahn in their proof of phase transition in the hard-core model on Z^d. Building further on these techniques, we study local Markov chains for sampling proper 3-colorings of the discrete torus Z^d_n. We show that there is a constant ho approx 0.22 such that for all even n geq 4 and d sufficiently large, if M is a Markov chain on the set of proper 3-colorings of Z^d_n that updates the color of at most ho n^d vertices at each step and whose stationary distribution is uniform, then the mixing time of M (the time taken for M to reach a distribution that is close to uniform, starting from an arbitrary coloring) is essentially exponential in n^{d-1}.

Recommendations

• Torpid mixing of local Markov chains on 3-colorings of the discrete torus
• Random sampling of 3‐colorings in ℤ²
• scientific article; zbMATH DE number 2151247
• Rigidity of 3-colorings of the discrete torus
• Systematic scan for sampling colorings

Cites work

• H-coloring tori
• A survey on the use of Markov chains to randomly sample colourings
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Analyzing Glauber dynamics by comparison of Markov chains
• Bound on the mass gap for finite volume stochastic Ising models at low temperature
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Edge-isoperimetric inequalities in the grid
• Entropy-driven phase transition in low-temperature antiferromagnetic Potts models
• Gibbs measures and dismantlable graphs
• Gibbs measures and phase transitions
• Graph homomorphisms and phase transitions
• High-dimensional Lipschitz functions are typically flat
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 4160792 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303576 (Why is no real title available?)
• scientific article; zbMATH DE number 3210966 (Why is no real title available?)
• scientific article; zbMATH DE number 3294019 (Why is no real title available?)
• scientific article; zbMATH DE number 3076589 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Markov chain algorithms for planar lattice structures
• Non-uniqueness of measures of maximal entropy for subshifts of finite type
• On Counting Independent Sets in Sparse Graphs
• On Ising's model of ferromagnetism
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• Random sampling of 3‐colorings in ℤ²
• Sampling 3-colourings of regular bipartite graphs
• Sampling independent sets in the discrete torus
• The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
• Torpid mixing of local Markov chains on 3-colorings of the discrete torus

Cited in

(13)

• Rigidity of 3-colorings of the discrete torus
• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• Tunneling behavior of Ising and Potts models in the low-temperature regime
• Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)
• Entropy-driven phase transition in low-temperature antiferromagnetic Potts models
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Torpid mixing of local Markov chains on 3-colorings of the discrete torus
• The growth constant of odd cutsets in high dimensions
• Random sampling of 3‐colorings in ℤ²
• Proper -colorings of are Bernoulli
• Correlation decay and the absence of zeros property of partition functions
• Homomorphisms from the torus
• Three-coloring statistical model with domain wall boundary conditions: trigonometric limit

This page was built for publication: Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)

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