Strong spatial mixing of $q$-colorings on Bethe lattices

Abstract

We investigate the problem of strong spatial mixing of $q$-colorings on Bethe lattices. By analyzing the sum-product algorithm we establish the strong spatial mixing of $q$-colorings on $(b+1)$-regular Bethe lattices, for $q \geq 1+\lceil 1.764b \rceil$. We also establish the strong spatial mixing of $q$-colorings on binary trees, for $q=4$.

We correct a mistake in our arguments and use $\ell_1$-norm instead of $\ell_\infty$-norm