Mixing properties of colorings of the ℤ^d lattice

2019/03/27 by Noga Alon, Alon, Noga, Raimundo Briceño +7 · 1 citation
Computer Science · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics #Mathematical Dynamics and Fractals #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1903.11685

openalex publication_date 2019/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study and classify proper q-colorings of the \mathbb Z^d lattice, identifying three regimes where different combinatorial behavior holds: (1) When q≤ d+1, there exist frozen colorings, that is, proper q-colorings of \mathbb Z^d which cannot be modified on any finite subset. (2) We prove a strong list-coloring property which implies that, when q≥ d+2, any proper q-coloring of the boundary of a box of side length n ≥ d+2 can be extended to a proper q-coloring of the entire box. (3) When q≥ 2d+1, the latter holds for any n ≥ 1. Consequently, we classify the space of proper q-colorings of the \mathbb Z^d lattice by their mixing properties.

Cited by

• Long-range order in discrete spin systems

Related

• Three lectures on random proper colorings of ℤ^d
• Rigidity of proper colorings of ℤ^d
• Strong spatial mixing of q-colorings on Bethe lattices
• Recoloring bounded treewidth graphs
• Ramsey theory over partitions II: Negative Ramsey relations and pump-up theorems