Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

Strong spatial mixing (SSM) is an important and widely studied quantitative notion of "correlation decay" for a variety of natural distributions arising in statistical physics, probability theory, and theoretical computer science. One of the most widely studied such distributions is the uniform distribution over proper q-colorings on a maximum degree Δ graph, μ. Provided that q greater than or equal to Δ+1, any such graph has at least one proper q-coloring that can be identified via e.g. a greedy search. It is a longstanding folklore conjecture that whenever q satisfies this minimal inequality, μ exhibits SSM and the correlations between the colors of vertices in a sample from μ decay exponentially fast in the graph distance between the vertices. However, even the specialization of this basic question to bounded-degree trees has remained wide open, highlighting how much there still is to learn about random colorings.

Apart from the nice structural consequences of SSM, notions of correlation decay (even restricted to trees) are of significant interest in the theoretical computer science community; it is widely believed that as long as SSM holds on bounded-degree trees with q

 colors, one could obtain an efficient sampler for q-colorings on all bounded-degree graphs via simple Markov chain algorithms. 

We essentially resolve the SSM conjecture on trees, holds for random q-colorings on trees of maximum degree Δ whenever q greater than or equal to Δ+3. In the algorithmic direction, we use SSM on trees to establish optimal mixing of the Glauber dynamics (a classical Markov chain) for sampling q-colorings on graphs of maximum degree Δ and girth g whenever q greater than or equal to Δ+3.

Joint work with Zongchen Chen, Kuikui Liu, and Ankur Moitra.