Name
Abstract | ||
|---|---|---|
We consider spin systems on the integer lattice graph $mathbb{Z}^d$ with nearest-neighbor interactions. We develop a combinatorial framework for establishing that exponential decay with distance of spin correlations, specifically the strong spatial mixing condition (SSM), implies rapid mixing of a large class of Markov chains. As a first application of our method we prove that SSM implies $O(log n)$ mixing of systematic scan dynamics (under mild conditions) on an $n$-vertex $d$-dimensional cube of the integer lattice graph $mathbb{Z}^d$. Systematic scan dynamics are widely employed in practice but have proved hard to analyze. A second application of our technology concerns the Swendsen-Wang dynamics for the ferromagnetic Ising and Potts models. We show that SSM implies an $O(1)$ bound for the relaxation time (i.e., the inverse spectral gap). As a by-product of this implication we observe that the relaxation time of the Swendsen-Wang dynamics in square boxes of $mathbb{Z}^2$ is $O(1)$ throughout the subcritical regime of the $q$-state Potts model, for all $q ge 2$. We also use our combinatorial framework to give a simple coupling proof of the classical result that SSM entails optimal mixing time of the Glauber dynamics. Although our results in the paper focus on $d$-dimensional cubes in $mathbb{Z}^d$, they generalize straightforwardly to arbitrary regions of $mathbb{Z}^d$ and to graphs with subexponential growth. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Discrete Mathematics | Inverse,Discrete mathematics,Spin-½,Combinatorics,Exponential decay,Markov chain,Ising model,Spectral gap,Integer lattice,Mathematics,Potts model |
DocType | Volume | Citations |
Journal | abs/1612.01576 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Antonio Blanca | 1 | 14 | 9.74 |
| Pietro Caputo | 2 | 3 | 2.15 |
| Alistair Sinclair | 3 | 1506 | 308.40 |
| Eric Vigoda | 4 | 747 | 76.55 |