Rigidity of proper colorings of ℤ^d

2018/08/10 by Ron Peled, Peled, Ron, Yinon Spinka +1 · 1 citation
Mathematics · #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1808.03597

Abstract

A proper q-coloring of a domain in ℤ^d is a function assigning one of q colors to each vertex of the domain such that adjacent vertices are colored differently. Sampling a proper q-coloring uniformly at random, does the coloring typically exhibit long-range order? It has been known since the work of Dobrushin that no such ordering can arise when q is large compared with d. We prove here that long-range order does arise for each q when d is sufficiently high, and further characterize all periodic maximal-entropy Gibbs states for the model. Ordering is also shown to emerge in low dimensions if the lattice ℤ^d is replaced by ℤ^d₁×\mathbbT^d₂ with d₁≥ 2, d=d₁+d₂ sufficiently high and \mathbbT a cycle of even length. The results address questions going back to Berker--Kadanoff (1980), Kotecký (1985) and Salas--Sokal (1997).

Cited by

• Entropy methods in combinatorics

Related

• Three lectures on random proper colorings of ℤ^d
• Mixing properties of colorings of the ℤ^d lattice
• Gibbs Rapidly Samples Colorings of G(n,d/n)
• Phase coexistence and torpid mixing in the 3-coloring model on Z^d
• Long-range order in discrete spin systems