Rigidity of proper colorings of $\mathbb{Z}^d$

Understand

A proper $q$-coloring of a domain in $\mathbb{Z}^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 $\mathbb{Z}^d$ is replaced by $\mathbb{Z}^{d_1}\times\mathbb{T}^{d_2}$ with $d_1\ge 2$, $d=d_1+d_2$ sufficiently high and $\mathbb{T}$ a cycle of even length.