License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.48
URN: urn:nbn:de:0030-drops-112630
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11263/
Efthymiou, Charilaos ;
Galanis, Andreas ;
Hayes, Thomas P. ;
Stefankovic, Daniel ;
Vigoda, Eric
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>alpha d where alpha ~~ 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 L^2 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.
BibTeX - Entry
@InProceedings{efthymiou_et_al:LIPIcs:2019:11263,
author = {Charilaos Efthymiou and Andreas Galanis and Thomas P. Hayes and Daniel Stefankovic and Eric Vigoda},
title = {{Improved Strong Spatial Mixing for Colorings on Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {48:1--48:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11263},
URN = {urn:nbn:de:0030-drops-112630},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.48},
annote = {Keywords: colorings, regular tree, spatial mixing, phase transitions}
}
Keywords: |
|
colorings, regular tree, spatial mixing, phase transitions |
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) |
Issue Date: |
|
2019 |
Date of publication: |
|
17.09.2019 |