@inproceedings{1f4dde4472464661aecfffb4e73f2bc8,
title = "Improved strong spatial mixing for colorings on trees",
abstract = "Strong spatial mixing (SSM) is a form of correlation decay that has played an essential role in the design of approximate counting algorithms for spin systems. A notable example is the algorithm of Weitz (2006) for the hard-core model on weighted independent sets. We study SSM for the q-colorings problem on the infinite (d+1)-regular tree. Weak spatial mixing (WSM) captures whether the influence of the leaves on the root vanishes as the height of the tree grows. Jonasson (2002) established WSM when q > d + 1. In contrast, in SSM, we first fix a coloring on a subset of internal vertices, and we again ask if the influence of the leaves on the root is vanishing. It was known that SSM holds on the (d + 1)-regular tree when q > αd where α ≈ 1.763... is a constant that has arisen in a variety of results concerning random colorings. Here we improve on this bound by showing SSM for q > 1.59d. Our proof establishes an L2 contraction for the BP operator. For the contraction we bound the norm of the BP Jacobian by exploiting combinatorial properties of the coloring of the tree.",
keywords = "Colorings, Phase transitions, Regular tree, Spatial mixing",
author = "Charilaos Efthymiou and Andreas Galanis and Hayes, \{Thomas P.\} and Daniel {\v S}tefankovi{\v c} and Eric Vigoda",
note = "Publisher Copyright: {\textcopyright} Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel {\v S}tefankovi{\v c}, and Eric Vigoda.; 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019 ; Conference date: 20-09-2019 Through 22-09-2019",
year = "2019",
month = sep,
doi = "10.4230/LIPIcs.APPROX-RANDOM.2019.48",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Dimitris Achlioptas and Vegh, \{Laszlo A.\}",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019",
}