Mixing properties of colorings of the $\mathbb{Z}^d$ lattice
Noga Alon Raimundo Briceño Nishant Chandgotia Alexander Magazinov Yinon Spinka



We study and classify proper q-colorings of the ^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 ^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 ^d lattice by their mixing properties.

[
    [
    December 30, 2023
=====================







§ INTRODUCTION



A proper coloring of a graph G is an assignment of a color (say a number in ) to each vertex of G so that adjacent vertices are assigned different colors. For an integer q ≥ 2, a (proper) q-coloring of G is a proper coloring in which all colors belong to a fixed set of size q, e.g., {0,1,…,q-1}.

In this work, we mainly consider the d-dimensional integer lattice  for d ≥ 1. We view it both as the group and its Cayley graph with respect to the standard generators. Notice that, in this case, the number of neighbors of each vertex is 2d.


Our first result is about frozen q-colorings.
A q-coloring of ^d is frozen if any q-coloring of ^d which differs from it on finitely many sites is identical to it. The existence of a frozen q-coloring precludes the possibility of any reasonable mixing property.





There exist frozen q-colorings of ^d if and only if 2 ≤ q ≤ d+1.



Since there are no frozen q-colorings of ^d when q ≥ d+2, a natural question is how unconstrained are proper colorings in this regime.
In order to understand better what happens when q ≥ d+2, we show that a certain list-coloring property of large boxes in ^d holds. A consequence of this property will be that whenever q ≥ d+2, large boxes in ^d have the property that any partial proper q-coloring of their boundary can be extended to a proper q-coloring of (the interior of) the entire box. To state the list-coloring result precisely, we now introduce some definitions.

For a graph G and a function L: G→, we say that G is L-list-colorable if for any collection of sets – also called lists – {S_v}_v∈ G with |S_v| ≥ L(v), there exists a proper coloring f of G such that f(v) ∈ S_v for all v ∈ G.



Denote [n] := {1,…,n}. Depending on the context, [n]^d = {1,…,n}^d may also be interpreted as an induced subgraph of ^d.
Define L_n^d: [n]^d →{2,…,d+2} by

    L_n^d():=2 + |{1≤ k ≤ d :  1<|i_k|< n}|.


Our second result is the following.


The graph [n]^d is L_n^d-list-colorable whenever n ≥ d+2.


The above results have implications for the mixing properties of the set of all q-colorings. Specifically, we characterise when the set of q-colorings of ^d is topologically mixing, strongly irreducible, has the finite extension property and is topologically strong spatial mixing (see Section <ref> for definitions and results). Mixing properties have important consequences in statistical physics <cit.>, dynamical systems <cit.>, and the study of constrained satisfaction problems <cit.>. We discuss some of these aspects in Section <ref>. 


The rest of the paper is organized as follows.
Section <ref> is dedicated to frozen q-colorings and, in particular, contains the proof of Theorem <ref>. In addition, we also prove a result about non-existence of frozen q-colorings in general graphs satisfying appropriate expansion properties.
Section <ref> is dedicated to list-colorings and, in particular, contains the proof of Theorem <ref>. In Section <ref>, we introduce a hierarchy of mixing properties and, using the previous results, show that for a fixed dimension d, there exist two critical numbers of colors, namely q = d+1 and q = 2d, that determine three different mixing regimes.
Finally, in Section <ref>, we conclude with a discussion and open questions.


We end this section with some notation that will be used throughout the paper.
The set of edges of a graph G is denoted by _G. Given U, V⊂ G, we denote by (U,V) ⊂_G the set of edges between a vertex of U and a vertex of V.
Given a set U ⊂ G, we denote the external vertex boundary of U by

    ∂ U:={v ∈ G ∖ U : v is adjacent to some u ∈ U} .














§ FROZEN Q-COLORINGS



In this section, we prove Theorem <ref>. We split the proof into two parts: existence and non-existence of frozen q-colorings. Theorem <ref> is a direct consequence of Proposition <ref> and Corollary <ref> below. We begin with the existence of frozen q-colorings when q ≤ d+1. Many constructions have appeared in the past which are similar in principle (see, e.g., <cit.>).


There exist frozen q-colorings of ^d for any 2 ≤ q ≤ d+1.








First suppose that q = d+1 and let x∈{0,1, …, q-1}^^d be given by 

    x_:= ∑_k=1^d ki_k q    for all ∈ .


First, let us verify that x is a q-coloring. Indeed, for ∈ and e_k the unit vector in the kth direction (1 ≤ k ≤ d), we have that

    x_+ e_k= x_+k q .

In particular, x_+ e_k - x_ = k ≠ 0 q, and thus adjacent vertices have different colors.

Let us now show that x is frozen. Suppose that y is a q-coloring that differs from x on finitely many sites.
Among all  such that x_≠ y_, we choose one which maximizes ∑_k=1^d i_k. Then, for any 1 ≤ k ≤ d,

    y_ + e_k=x_+ e_k= x_+k q .

Therefore,

    {y_ + e_k :  1≤ k≤ d}={0,1, …, q-1}∖{x_} .

Since y is a proper q-coloring, it must be that y_=x_, contradicting the choice of .

Now, to deal with the case q < d+1, notice that by the previous construction, we already have a frozen q-coloring of ^q-1. Thus, it suffices to prove that we can always extend a frozen q-coloring x of ^r to ^r+1, as we may then proceed by induction on r.  Given a frozen q-coloring x of ^r, consider the q-coloring y of ^r+1 defined as

    y_(i_1,…,i_r+1) := x_(i_1,…,i_r-1,i_r + i_r+1),

which is clearly proper, since if (i_1,…,i_r+1) is adjacent to (j_1,…,j_r+1) in ^r+1, then (i_1,…,i_r-1,i_r+i_r+1) is adjacent to (j_1,…,j_r-1,j_r+j_r+1) in ^r. Notice that y is also frozen, since y restricted to ^r ×{i_r+1} can be seen as a translate of the frozen q-coloring x.


Next we prove that no frozen q-coloring exists when q ≥ d+2. While this follows from the list-coloring result given in Theorem <ref> (see also Theorem <ref>), we give a direct argument here which applies in greater generality. Let us now state the result precisely.

The edge-isoperimetric constant of a graph G is

    h(G) := inf_F |(F, G ∖ F)|/|F| ,

where the infimum is taken over all non-empty finite subsets of vertices F.
As for ^d, a q-coloring of G is frozen if any q-coloring of G which differs from it on finitely many sites is identical to it.


Let G be a graph of maximum degree Δ and q > 1/2Δ + 1/2 h(G) + 1. Then there do not exist frozen q-colorings of G.


Since, in the ^d case, Δ = 2d and h(^d) = 0 (e.g., consider sets of the form F = [n]^d for increasing n), we have the following corollary.


There do not exist frozen q-colorings of ^d for any q ≥ d+2.


Proposition <ref> is sharp in many cases, including ^d (Theorem <ref>), the triangular lattice (see Figure <ref>), the honeycomb lattice (trivially, since a 2-coloring of an infinite connected bipartite graph is always frozen), and regular trees (see <cit.>).



We remark that finite (non-empty) graphs never admit frozen q-colorings since the colors can always be permuted. Proposition <ref> is thus trivial for finite graphs. Nevertheless, our argument can provide meaningful information for finite graphs as well. Proposition <ref> is an immediate consequence of the following.

Given a subset F of vertices of G, we say that a q-coloring of G is frozen on F if any q-coloring of G which differs from it on a subset of F is identical to it. Thus, a q-coloring is frozen if and only if it is frozen on every finite set.







Let G be a graph, q ≥ 2, and F ⊂ G finite.
If (q - 1) |F| > |_F| + |(F, G∖ F)|, then no q-coloring of G is frozen on F.


Since 2|_F| + |(F, G∖ F)| equals the sum of the degrees of vertices in F, the following is an immediate corollary to Proposition <ref>.


Let G be a graph of maximum degree Δ, q ≥ 2, and F ⊂ G finite. If (q - 1 - Δ/2) |F| > 1/2 |(F, G∖ F)|, then no q-coloring of G is frozen on F.




Suppose towards a contradiction that there exists a q-coloring of G which is frozen on F.
Consider the restriction of the coloring to the finite graph G' := (F∪∂ F, _F ∪(F, G∖ F)). 
For distinct colors i and j, let G'_i,j be the subgraph of G' consisting of edges between vertices colored i and j.
A bi-color component is a connected component of any such G'_i,j.
Let  be the collection of bi-color components.
Note that the bi-color components partition the edges of G' so that ∑_A ∈ |_A| = |_F| + |(F, G∖ F)|.
Note also that, since the q-coloring is frozen on F, each A ∈ contains a vertex in ∂ F, as otherwise, the two colors in A could be swapped (contradicting that the coloring is frozen). Hence, each A ∈ contains at most |_A| vertices of F. Thus, we have

    ∑_A ∈ |A ∩ F| ≤∑_A ∈ |_A| = |_F| + |(F, G∖ F)| .


On the other hand, using again that the q-coloring is frozen on F (and hence also on each individual vertex in F), we see that each vertex in F is contained in exactly q-1 bi-color components, and it follows that ∑_A ∈ |A ∩ F| = (q-1) |F|. We thus conclude that (q - 1) |F| ≤ |_F| + |(F, G∖ F)|, contradicting the assumption.


We remark that the proof of Proposition <ref> shows something stronger, namely, that (under the assumption) any q-coloring of G can be modified by swapping the two colors of a bi-color component (a so-called Kempe chain move) contained in F.

We end this section with a short discussion about the existence of single-site frozen q-colorings, those which are frozen on every F having |F|=1.
Given a graph G of maximum degree Δ, it is clear that there do not exist single-site frozen q-colorings of G whenever q ≥Δ + 2. On the other hand, on ^d, it is straightforward to check that


    x_ := ∑_k=1^d ki_k 2d+1,     ∈^d ,

defines a single-site frozen (2d+1)-coloring of ^d. Similar constructions (like in the proof of Proposition <ref>) yield single-site frozen q-colorings of ^d for any 2 ≤ q ≤ 2d. Thus, single-site frozen q-colorings of ^d exist if and only if 2 ≤ q ≤ 2d+1.





§ LIST-COLORABILITY






In this section, we prove Theorem <ref>.
We will use the main result from <cit.>.
We say that a digraph D is L-list-colorable if the underlying undirected graph is such. Define L_D(v) := d^+_D(v)+1, where d^+_D(v) is the out-degree of v in D.
The following is <cit.> specialized to digraphs having no odd directed cycles (this special case also follows from Richardson's Theorem; see <cit.>).



A finite digraph D having no odd directed cycles is L_D-list-colorable.



Thus, Theorem <ref> allows to prove L-list-colorability of an undirected graph G by exhibiting an orientation of the edges of G so that the out-degree of any vertex v is strictly less than L(v). The following provides a sufficient (and in fact necessary) condition for such an orientation to exist (see the closely related <cit.>).


Let G be a finite bipartite graph and let L: G→ satisfy

    ∑_v∈ H (L(v)-1) ≥  |_H|     for any induced subgraph  H⊂ G .


Then G is L-list-colorable.


Denote G=(V,E) and consider the set 𝒱 := { (v,i) : v ∈ V, 1 ≤ i ≤ L(v)-1 } containing L(v)-1 copies of any vertex v.
Let 𝒢 be the bipartite graph with bipartition classes E and 𝒱 in which {e,(v,i)} is an edge in 𝒢 if and only if v is incident to e. For any F ⊂ E, letting H be the subgraph of G induced by the endpoints of F, we see that the number of neighbors of F is ∑_v ∈ H (L(v)-1) ≥ |_H| ≥ |F|.
Thus, by Hall's theorem, 𝒢 contains a matching of size |E|. Given such a matching, we obtain a digraph D on V by orienting each edge e ∈ E from the vertex it is matched to outwards. In this orientation of G, the out-degree of any vertex v is at most L(v)-1 so that L_D(v) ≤ L(v). Since G is bipartite, D has no odd directed cycles. It follows from Theorem <ref> that D (and hence also G) is L-list-colorable.


Let {K_t}_t=0^d be the level sets of L_n^d, that is, 

    K_t
      :   = {∈ [n]^d :  L_n^d()=t+2}
       = {∈ [n]^d  :  |{1≤ j ≤ d :  1<|i_j|<n}|=t}.


Let H be an induced subgraph of G. Denote H_t:=H∩ K_t for 0≤ t≤ d and H_-1:=∅. By Corollary <ref>, it suffices to show that

    ∑_t=0^d (t+1) |H_t|≥∑_t=0^d (|_H_t| + |(H_t, H_t-1)|).

We will in fact prove this inequality term-by-term, namely, that for any 0 ≤ t≤ d,

    (t+1) |H_t|≥ |_H_t| + |(H_t, H_t-1)|.

Since this is trivial for t=0 (the right-hand side is zero), we fix 1 ≤ t ≤ d and aim to show that (<ref>) holds for this t.



Write _v(G) for the degree of a vertex v in a graph G. Note that for all ∈ K_t, we have that _(K_t∪ K_t-1)=2t. Thus,

    2t|H_t|=∑_∈ H_t_(K_t∪ K_t-1).


The right-hand side counts the sum of the number of oriented edges (u,v) such that u ∈ H_t and v ∈ K_t∪ K_t-1. We thus see that

    2t|H_t|=2|_H_t|+|(H_t, K_t∖ H_t)|+ |(H_t, H_t-1)|+ |(H_t, K_t-1∖ H_t-1)|.


Hence, to obtain (<ref>), it suffices to show that

    2|H_t|+|(H_t, K_t∖ H_t)|+ |(H_t, K_t-1∖ H_t-1)|≥ |(H_t, H_t-1)|.


Since putting H_t-1=K_t-1 only increases the right-hand side and decreases the left-hand side, it suffices to prove that

    2|H_t|+|(H_t, K_t∖ H_t)|≥ |(H_t, K_t-1)|.


To prove this, we partition (H_t, K_t-1) into two sets, E_1 and E_2, and show that |E_1|≤ |(H_t, K_t∖ H_t)| and |E_2|≤ 2|H_t|.

Given e ∈(H_t, K_t-1), letting ∈ H_t and unit vector u be such that e={,+  u}, we denote the line in the box [n]^d in the direction e by

    (e)
      :=    {-m  u ∈ K_t : m ∈}
    
      =    {-m  u : m=0,…,n-3} .


We now partition (H_t, K_t-1) into the two sets

    E_1    :={e∈(H_t, K_t-1) : (e)⊄H_t },
    
     E_2    :={e∈(H_t, K_t-1) : (e)⊂ H_t }.
 

We begin by showing that |E_1|≤ |(H_t, K_t∖ H_t)|. To this end, it suffices to construct an injective map f: E_1→(H_t, K_t∖ H_t). For e ∈ E_1, define

    f(e):= {- (m-1) u, -m  u } ,

where ∈ H_t and unit vector u are such that e={,+ u}, and where m is the smallest positive integer such that -m  u ∈ K_t∖ H_t. It is straightforward to check that f is injective.

We now show that |E_2|≤ 2|H_t|. Denote the set of lines contained in H_t by

    ℒ_t:={(e)  :  e ∈ E_2} ,

and note that |E_2|=2|ℒ_t|.
Observe also that every vertex belongs to at most d lines and that each line in ℒ_t consists of exactly n-2 vertices of H_t. Thus,

    |ℒ_t|≤d |H_t|/n-2≤ |H_t| .



Let us make a remark about two aspects of the tightness of Theorem <ref>.
The first concerns the assumption that n ≥ d+2: We show in Section <ref> that [2]^2 is L_2^2-list-colorable (here 2=n<d+2=4), while [2]^3 is not L_2^3-list-colorable (here 2=n<d+2=5). Fixing d, the question of the `optimal' value of n such that [n]^d is L_n^d-list-colorable remains; the use of the word optimal is justified in the next proposition. The second aspect concerns the sizes of the lists: [n]^d may be L-list-colorable for functions L which are pointwise smaller-or-equal than L^d_n. For example, [n]^2 is min{L^2_n,3}-list-colorable; see Question <ref>.



Let n ≥ 2 and d ≥ 1. Suppose [n]^d is L_n^d-list-colorable. Then,


  * [n]^d-1 is L_n^d-1-list-colorable and

  * [n+1]^d is L_n+1^d-list-colorable.




Notice that the function L_n^d-1 is just the restriction L_n^d|_[n]^d-1×{1} after identifying [n]^d-1 with [n]^d-1×{1}. This proves the first part. 

For the second part, we start by coloring [n+1]^d∖ [n]^d and then using the given hypothesis to color the portion which is left, that is, [n]^d. In order to color [n+1]^d∖ [n]^d, we proceed by decomposing it into copies of [n]^k, where 0≤ k≤ d-1, and successively coloring them in increasing order of k (using the first part repeatedly).




§ MIXING PROPERTIES



In this section, we study various aspects of rigidity and mixing of X^d_q, the set of all proper q-colorings of ^d (the color set here is always taken to be {1,…,q}).
Let us discuss some consequences of the above theorems in terms of mixing properties. The space X^d_q is an instance of a so-called shift space <cit.>, and the following properties, which we define only for X^d_q, are applicable in this more general context (for a general introduction to mixing properties, we would refer the reader to <cit.> and in the context of graph homomorphisms to <cit.>).

Given nonempty sets U, V ⊂, we denote

    (U,V):=min_∈ U, ∈ V|-|_1.


Also, we denote by B_n^d the set {-n,…,n}^d.

Four important mixing properties (in increasing order of strength) are:



  * X^d_q is topologically mixing (TM) if for all U, V ⊂, there exists n ∈ such that for all ∈ for which d(U+, V)≥ n and x, y∈ X^d_q there exists z∈ X^d_q such that z|_U+=x|_U+ and z|_V = y|_V.


  * X^d_q is strongly irreducible (SI) with gap n if for all x, y∈ X^d_q and U, V ⊂ for which (U,V)≥ n, there exists z∈ X^d_q such that z|_U = x|_V and z|_U = y|_V.


  * X^d_q has the finite extension property (FEP) with distance n if for any U ⊆ and any coloring u of U, if u can be extended to a q-coloring of U + _n^d, then u can be extended to a q-coloring of ^d.


  * X^d_q is topologically strong spatial mixing (TSSM) with gap n if for all x, y∈ X^d_q and U, V, W ⊂ for which (U, V)≥ n and x|_W = y|_W, there exists z∈ X^d_q such that z|_U ∪ W=x|_U ∪ W and z|_V ∪ W=y|_V ∪ W.


The following implications hold:

    (TSSM)(FEP)(SI)(TM).

The first implication follows from <cit.> and the additional observation that though the FEP property in <cit.> is seemingly different from ours,  it is in fact equivalent (the gap might be different for the two definitions though). The other two implications are straightforward to verify.





A partial q-coloring of U is a q-coloring of a subset C of U, i.e., an assignment of colors in {1,…,q} to each vertex in C such that any pair of adjacent vertices in C have different colors. We call C the support of the partial q-coloring.

We say that X^d_q is n-fillable if any partial q-coloring of ∂ [n]^d with support C can be extended to a q-coloring of [n]^d ∪ C. Notice that X^d_q is 1-fillable if and only if given any q-coloring of the neighbors of a vertex, we can always extend it to the vertex itself, and this is true if and only if q ≥ 2d+1. In <cit.>, this last property was called single-site fillability (SSF) and used in the context of shift spaces.





If [n]^d is L_n^d-list-colorable, then X^d_q is n-fillable for q ≥ d+2. 




 
Fix q≥ d+2 and suppose that [n]^d is L_n^d-list-colorable. Let c be a partial q-coloring of ∂ [n]^d with support C. Now consider the lists
S:_n^d→ 2^{1, 2, …, q} given by 

    S():={1,2 …, q}∖{c_ : ∈ C∩∂{}}.


Then, clearly |S()|≥ L_n^d(). Since [n]^d is L_n^d-list-colorable, we have that c extends to a proper coloring of [n]^d ∪ C.


 For d=2 and q ≥ 4, n-fillability already followed from <cit.> and the analogous property for a 2 × 2 box is also true (see <cit.>). 

For q≤ d+1 and any n, we can also construct an explicit partial q-coloring of ∂ [n]^d which cannot be extended to a q-coloring of [n]^d. Observe that the frozen q-coloring x defined in the proof of Proposition <ref> has an additional property: Restricting x to the elements of ∂ [n]^d with at least one coordinate zero extends to a q-coloring of [n]^d in a unique manner. Now we let 

    C:={(i_1, …, i_d)∈∂ [n]^d : i_k=0 for some k }∪{(n+1,1, …, 1)}

and define c to be the q-coloring of C which coincides with x everywhere except at (n+1,1,…, 1), where it is equal to x_(n,1,…,1); it is clear that c cannot be extended to a coloring of [n]^d.
 
 Now we consider the following generalization to more general shapes.



If X^d_q is n-fillable, then for any subset U ⊆^d that can be written as a union of translations of [n]^d and any partial q-coloring c of ∂ U, there exists an extension of c to a q-coloring of U ∪ C, where C is the support of c.



Suppose that X^d_q is n-fillable for some n ∈. Consider any set F ⊂^d such that U = ⋃_j⃗∈ F (j⃗ + [n]^d). Without loss of generality, suppose that F is minimal, i.e., for every proper subset F', ⋃_j⃗∈ F' (j⃗ + [n]^d) is a proper subset of U.

Now, given an arbitrary i⃗∈ F, proceed by using the n-fillability property to find a coloring a of i⃗ + [n]^d and considering its boundary to be colored according to c restricted to C ∩∂(i⃗ + [n]^d). Next, iterate this process with U', C', and c', where U' is ⋃_j⃗∈ F ∖{i⃗} (j⃗ + [n]^d), C' is ∂ U', and c' is the restriction to C' of the concatenation of the partial colorings a and c. If F is finite, this process finishes in at most |F| steps, and if F is infinite, we can conclude by the compactness of {1,…,q}^U.





If X^d_q is (2n+1)-fillable, then it satisfies FEP with distance 2n.


In this proof, we suppress the d in the notation of _n^d. Consider U ⊆ and a coloring u of U that can be extended to a proper q-coloring u of U + _2n. 

Now, consider a family of vectors {k⃗_ℓ}_ℓ∈ in ^d such that {k⃗_ℓ + B_n}_ℓ∈ is a partition of ^d. For example, {nk⃗ + B_n}_k⃗∈^d would be enough. Let S ⊆ be the set of indices ℓ such that (k⃗_ℓ + B_n) ∩ U ≠∅.

Notice that U ⊆⋃_ℓ∈ S (k⃗_ℓ + _n) ⊆ U + B_2n. Indeed, if i⃗∈ U, then, since {k⃗_ℓ + B_n}_ℓ∈ is a partition of ^d, there exists (a unique) ℓ^*∈ S such that i⃗∈ (k⃗_ℓ^* + B_n). On the other hand, if i⃗∈ (k⃗_ℓ^* + B_n) for some ℓ^* ∈ S, then there exists j⃗∈ (k⃗_ℓ^* + B_n) ∩ U, so i⃗ - j⃗_∞≤ 2n. Therefore, i⃗∈ (j⃗ + B_2n) ⊆ U+ B_2n.

Finally, consider u' to be the restriction of u to ⋃_ℓ∈ S (k⃗_ℓ + B_n). Then, u' is a proper partial coloring and the complement of its support {k⃗_ℓ + B_n}_ℓ∈∖ S is a (disjoint) union of boxes B_n with perhaps partially defined colorings on its boundary (the restriction of u' to ∂ (k⃗_ℓ + B_n)). Then, observing that B_n is just a translation of [2n+1]^d, by Proposition <ref>, we conclude.


From what has been observed in <cit.>, it follows for X^d_q that FEP with distance 0 is equivalent to TSSM. Furthermore, it is easy to see that FEP with distance n implies SI with gap 2n. Considering all this, we have the following result.



Let d ≥ 1. Then,


  * For 3 ≤ q ≤ d+1,
X^d_q is TM, but not SI.


  * For d+2 ≤ q ≤ 2d, X^d_q is FEP, but not TSSM.

 
  * For 2d+1 ≤ q, X^d_q is TSSM.
 


In the following, ∈^d is called even or odd if the sum of its coordinates is even or odd, respectively. Let e_1,  e_2, …,  e_2d be the unit vectors in ^d, where e_i=- e_2d-i+1 for 1≤ i ≤ d.

We split the proof into the three cases in the statement.


  * Case 1: 3 ≤ q ≤ d+1. In <cit.>, it is shown that, for all d, X^d_q is topologically mixing if and only if q ≥ 3. However, X^d_q is not SI if q ≤ d+1. By Theorem <ref>, we have in fact that there exist frozen q-colorings, which is stronger, i.e., if X^d_q has a frozen q-coloring, then it cannot be SI: Let x be a frozen q-coloring and y any q-coloring which differs from x at 0.
Let n ≥ 1, U=∂ B_n and V={ 0}.
Observe that there does not exists a q-coloring z which agrees with x on U and y on V, while (U,V)=n.



  * Case 2: d+2 ≤ q ≤ 2d. By Proposition <ref>, X^d_q is n-fillable for q ≥ d+2. Therefore, by Proposition <ref>, X^d_q satisfies FEP with distance n. 


Fix n∈ and let S:=∂{m  e_1: m∈}, U:={(0,…, 0)}, and V:={n e_1}. Let x,y ∈ X^d_q be given by 

    x_:=
    m+ t (q-2)    if =m e_1+ e_t for 2≤ t ≤ 2d-1 and  m∈
    
    q-2    if ∉∂{m  e_1 :  m∈} is odd
    
    q-1    if ∉∂{m  e_1 :  m∈} is even

and

    y_:=
    m+ t (q-2)    if =m e_1+  e_t for 2≤ t ≤ 2d-1 and  m∈
    
    q-1    if ∉∂{m  e_1 :  m∈} is odd
    
    q-2    if ∉∂{m  e_1 :  m∈} is even.


Clearly x|_S= y|_S. Suppose that z∈ X^d_q is such that z|_U∪ S:=x|_U∪ S. We have that 

    z_(0, …, 0)=   x_(0, …, 0)   = q-1
    
    z_m e_1+  e_t=   x_m e_1+  e_t   =m+ t(q-2)

for 2≤ t ≤ 2d-1 and m∈. Since q≤ 2d, it follows that for all m∈,

    {z_m e_1+  e_t :  2≤ t ≤ 2d-1}={0, 1, …, q-3}

and hence z_m  e_1=x_m  e_1 for all m∈ and z|_V≠ y|_V. Since n was arbitrary, we have that X^d_q is not TSSM.



  * Case 3: 2d+1 ≤ q. In this case, X^d_q is 0-fillable and thus satisfies TSSM. 


 



§ DISCUSSION


 


 §.§ Gibbs measures and the influence of boundaries
 

One of the key motivations of this paper was to study the influence of a q-coloring of the boundary of a box on the colorings inside. Given n,d,q∈ and x ∈ X^d_q, let

    X_x, n, d, q:= {y∈ X^d_q : y|_^d∖ [n]^d=x|_^d∖ [n]^d}.


If X^d_q is SI, then there exists n_0∈ such that for all x∈ X^d_q and n≥ n_0,

    1	   ≥   lim_n→∞log |X_x,n,d,q|/log |{q-colorings of [n]^d}|
       ≥   lim_n→∞log |{q-colorings of [1+n_0,n-n_0]^d}|/log |{q-colorings of [n]^d}| = 1.


It is not difficult to prove that the limit

    lim_n→∞1/n^dlog|{q-colorings of [n]^d}|

exists for all d,q and is referred to as the entropy (of X^d_q), denoted by h_d,q. If the limit 

    lim_n→∞1/n^dlog |X_x,n,d,q|

exists, then it is denoted by h_x,d,q. 

By Theorem <ref>, (<ref>) and the calculation above, we have that for q≥ d+2, h_x,d,q=h_d,q for all x∈ X^d_q. If q≤ d+1, then there are frozen q-colorings x∈ X_d,q by Theorem <ref>. For such x, h_x,d,q=0.

 Given q ≤ d+1, what is the set of possible values h_x,d,q for x∈ X^d_q? Is it the entire interval [0,h_d,q]?


This has been established for q=3 in <cit.> using the “height function” formalism, which is missing for other values of q.

For q≥ d+2, one of the main questions that we would like to address is the following. Let μ_x, n,d, q denote the uniform measure on X_x,n,d,q.

 For what values of q and d does X^d_q have a unique Gibbs measure? In other words, do the measures μ_x,n,d,q converge weakly as n goes to infinity to the same limit for all x∈ X^d_q?


This has been proved in the case when q≥ 3.6 d <cit.> and we suspect that there exists a sequence q_d satisfying lim_d→∞q_d/d=1 such that it is true when q≥ q_d. Note that the existence of frozen colorings preclude the possibility of a unique Gibbs measure, so that Theorem <ref> implies that this does not hold when q ≤ d+1. We also mention that it has recently been shown <cit.> that there are multiple maximal-entropy Gibbs measures when d ≥ Cq^10log^3 q for some absolute constant C>0.








 §.§ Sampling a uniform q-coloring of [n]^d


Suppose that we are to sample a random coloring according to μ_x, n, d, q. One way to obtain an approximate such sample is by the Markov Chain Monte Carlo method: construct an ergodic Markov chain on X_x,n,d,q whose stationary distribution is μ_x, n, d, q, and run it for a long time. A common way to devise such a Markov chain is via the Metropolis–Hastings algorithm for an appropriate set of possible local changes. We mention a couple of such local changes, and address the corresponding ergodicity requirement, namely, whether one can transition between any two elements of X_x,n,d,q via the local changes. 

Let us fix d≥ 2 and q≥ 3 for the following discusssion. We refer to <cit.> for some more details.

A boundary pivot move is a pair (x,y) ∈ X_q^d × X_q^d such that they differ at most on a single site. We say that X^d_q has the boundary pivot property if for all x∈ X_q^d, n∈, and  y∈ X_x,n, d,q there exists a sequence of boundary pivot moves from x to y contained in X_x,n,d,q. It is well-known that X^d_q has the boundary pivot property when q=3 and it is quite easy to prove it for q≥ 2d+2 <cit.>. For d+2≤ q≤ 2d+1, a weaker property holds:  A boundary N-pivot move is a pair (x,y) ∈ X_q^d ×  X_q^d such that they differ at most on a translate of [N]^d. We say that X^d_q has the generalized boundary pivot property if there exists N∈ such that for all x∈ X_q^d, n∈, and y∈ X_x,n, d,q, there exists a sequence of boundary N-pivot moves from x to y contained in X_x,n,d,q. The space X_d^q has the generalized boundary pivot property – this is a consequence of the n-fillability property (which holds by Theorem <ref> and Proposition <ref>). The proof of this implication follows from the ideas in <cit.> (look also at the proof of <cit.> for similar proof).



For which q and d does X^d_q satisfy the generalized boundary pivot property?


We remark that we do not know of any value of (q,d) for which X^d_q does not satisfy the generalized boundary pivot property. To apply the generalized boundary pivot property, we will still need to be able to sample a uniform coloring on a smaller, but still ostensibly large, box. It will then help to know if another property holds in this case in which such a sampling is not necessary. A Kempe move is a pair (x,y) ∈ X^d_q × X^d_q such that y is obtained from x by swapping the colors on a bicolor component. We say that X^d_q is Kempe move connected if for all x∈ X^d_q, n∈, and y∈ X_x,n,d,q, there exists a sequence of Kempe moves from x to y contained in X_x,n,d,q.


For which q and d is X^d_q Kempe move connected?

Again, we are not aware of any (q,d) for which X^d_q is not Kempe move connected.




 §.§ Extension of a q-coloring of ∂ [n]^d to [n]^d for q≤ d+1


It was indicated after the end of the proof of Proposition <ref> that when 3≤ q≤ d+1, there exist q-colorings of ∂ [n]^d which do not have an extension into [n]^d.

 Characterise q-colorings of ∂ [n]^d which have an extension to [n]^d. What is the complexity of determining (in terms of n, q and d) whether an extension is possible?


For q=3, using the “height functions” formalism, the complexity is known to be of the order nlog n for d=2 (it follows from arguments very similar to those in  <cit.>) and n^2(d-1) for higher dimensions.





 §.§ Optimizing the parameters of list-colorability.

We would be interested to determine for which n and L it holds that [n]^d is L-list-colorable. We have shown that [n]^d is L-list-colorable when n ≥ d+2 and L = L^d_n, but we have not tried to optimize n or L. We raise two questions, one concerning the optimal n, and the other related to improving L.

It can be shown (e.g., by Theorem <ref>) that [2]^2 is L_2^2-list-colorable.



On the other hand, [2]^3 is not L^2_3-list-colorable. To see this, consider the lists S:[2]^3→ 2^{0,1,2,3} given by Figure <ref>. The two possible list-colorings of [2]^2×{1} are [ 1 0; 0 2 ] and [ 0 2; 1 0 ], which are incompatible with those of 
[2]^2×{2}, that are [ 1 2; 2 3 ] and [ 2 3; 1 2 ].





Recall that, due to Proposition <ref>, the property of being L^d_n-list-colorable is monotone in n, so it is natural to ask the following question.


What is the smallest n for which [n]^d is L^d_n-list-colorable?


Regarding improvements to the function L, we note that it might be possible to decrease L_n^d pointwise and still find that [n]^d is list-colorable.
For example, in dimension d=2, it is not hard to show using Theorem <ref>, that [n]^2 is L-list-colorable for the function L := min{L^2_n,3} (simply orient the external face in a cycle and all other edges in the positive direction; note that L=L^2_n ≡ 2 if n=2, but otherwise L ≠ L^2_n).



What is the smallest k for which [n]^d is min{L^d_n,k}-list-colorable for large enough n?



Other functions L which one may wonder about are the constant functions.
We say that G is k-list-colorable if it is L-list-colorable for the constant function L ≡ k.
Though k-list-colorability is slightly less related to mixing properties, it is still an interesting combinatorial problem.


What is the smallest k for which [n]^d is k-list-colorable for all n?


Using the Lovász local lemma, one may show that k ≥ Cd / log d suffices for some constant C>0 (this holds for any triangle-free graph with maximum degree d <cit.>; see also <cit.>).
We remark that this easily leads to a proof that X^d_q is 2-fillable when q ≥ d + Cd/log d, and that this approach to showing fillability can also be useful for proper colorings of other graphs besides ^d.





 
 
 



 

































§ ACKNOWLEDGEMENTS


The first author was supported by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation. The second author was supported by CONICYT/FONDECYT Postdoctorado 3190191 and ERC Starting Grants 678520 and 676970. The third author has been funded by the European Research Council starting grant 678520 (LocalOrder), ISF grant nos. 1289/17, 1702/17 and 1570/17. The fourth author has been funded by European Research Council starting grant 678520 (LocalOrder).

amsplain




