  Strong spatial mixing (SSM) is an important quantitative notion of
correlation decay for Gibbs distributions arising in statistical physics,
probability theory, and theoretical computer science. A longstanding conjecture
is that the uniform distribution on proper $q$-colorings on a $\Delta$-regular
tree exhibits SSM whenever $q \ge \Delta+1$. Moreover, it is widely believed
that as long as SSM holds on bounded-degree trees with $q$ colors, one would
obtain an efficient sampler for $q$-colorings on all bounded-degree graphs via
simple Markov chain algorithms. It is surprising that such a basic question is
still open, even on trees, but then again it also highlights how much we still
have to learn about random colorings. In this paper, we show the following:
  (1) For any $\Delta \ge 3$, SSM holds for random $q$-colorings on trees of
maximum degree $\Delta$ whenever $q \ge \Delta + 3$. Thus we almost fully
resolve the aforementioned conjecture. Our result substantially improves upon
the previously best bound which requires $q \ge 1.59\Delta+\gamma^*$ for an
absolute constant $\gamma^* > 0$.
  (2) For any $\Delta\ge 3$ and girth $g = \Omega_\Delta(1)$, we establish
optimal mixing of the Glauber dynamics for $q$-colorings on graphs of maximum
degree $\Delta$ and girth $g$ whenever $q \ge \Delta+3$. Our approach is based
on a new general reduction from spectral independence on large-girth graphs to
SSM on trees that is of independent interest.
  Using the same techniques, we also prove near-optimal bounds on weak spatial
mixing (WSM), a closely-related notion to SSM, for the antiferromagnetic Potts
model on trees.
