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\ge 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