Name
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\approx 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.APPROX-RANDOM.2019.48 | APPROX-RANDOM |
Field | DocType | Citations |
Combinatorics,Mathematics | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charilaos Efthymiou | 1 | 209 | 15.44 |
| andreas galanis | 2 | 68 | 15.13 |
| Thomas P. Hayes | 3 | 659 | 54.21 |
| Daniel Stefankovic | 4 | 243 | 28.65 |
| Eric Vigoda | 5 | 747 | 76.55 |