Strong Spatial Mixing with Fewer Colors for Lattice Graphs

Recursively-constructed couplings have been used in the past for mixing on trees. We show how to extend this technique to nontree-like graphs such as lattices. Using this method, we obtain the following general result. Suppose that G is a triangle-free graph and that for some ° ≥ 3, the maximum degree of G is at most °. We show that the spin system consisting of q-colorings of G has strong spatial mixing, provided q > α °-γ, where α≈ 1.76322 is the solution to α^α=e, and γ = 4α³-6α²-3α+4/2(α²-1)≈ 0.47031. Note that we have no additional lower bound on q or °. This is important for us because our main objective is to have results which are applicable to the lattices studied in statistical physics, such as the integer lattice ᵈ and the triangular lattice. For these graphs (in fact, for any graph in which the distance-k neighborhood of a vertex grows subexponentially in k), strong spatial mixing implies that there is a unique infinite-volume Gibbs measure. That is, there is one macroscopic equilibrium rather than many. Our general result gives, for example, a ``hand proof' of strong spatial mixing for 7-colorings of triangle-free 4-regular graphs. (Computer-assisted proofs of this result were provided by Salas and Sokal [J. Stat. Phys., 86 (1997), pp.\ 551--579] (for the rectangular lattice) and by Bubley, Dyer, Greenhill, and Jerrum [SIAM J. Comput., 29 (1999), pp.\ 387--400].) It also gives a hand proof of strong spatial mixing for 5-colorings of triangle-free 3-regular graphs. (A computer-assisted proof for the special case of the hexagonal lattice was provided earlier by Salas and Sokal [J. Stat. Phys., 86 (1997), pp.\ 551--579].) Toward the end of the paper we show how to improve our general technique by considering the geometry of the lattice. The idea is to construct the recursive coupling from a system of recurrences rather than from a single recurrence. We use the geometry of the lattice to derive the system of recurrences. This gives us an analysis with a horizon of more than one level of induction, which leads to improved results. We illustrate this idea by proving strong spatial mixing for $q=10$ on the lattice ³. Finally, we apply the idea to the triangular lattice, adding computational assistance. This gives us a (machine-assisted) proof of strong spatial mixing for $10$-colorings of the triangular lattice. (Such a proof for $11$ colors was given by Salas and Sokal [J. Stat. Phys., 86 (1997), pp.\ 551--579].) For completeness, we also show that our strong spatial mixing proof implies rapid mixing of Glauber dynamics for sampling proper colorings of neighborhood-amenable graphs. (It is known that strong spatial mixing often implies rapid mixing, but existing proofs seem to be written for ᵈ.) Thus our strong spatial mixing results give rapid