### Abstract

Original language | English |
---|---|

Pages (from-to) | 1895–1915 |

Number of pages | 21 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 29 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Oct 2015 |

### Fingerprint

### Keywords

- approximate counting
- MCMC
- strong spatial mixing
- branching matrices
- linear programming

### Cite this

*SIAM Journal on Discrete Mathematics*,

*29*(4), 1895–1915. https://doi.org/10.1137/140976923

}

*SIAM Journal on Discrete Mathematics*, vol. 29, no. 4, pp. 1895–1915. https://doi.org/10.1137/140976923

**Improved bounds on the phase transition for the hard-core model in 2 dimensions.** / Vera, Juan C.; Vigoda, E.; Yang, L.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - Improved bounds on the phase transition for the hard-core model in 2 dimensions

AU - Vera, Juan C.

AU - Vigoda, E.

AU - Yang, L.

PY - 2015/10/1

Y1 - 2015/10/1

N2 - For the hard-core lattice gas model defined on independent sets weighted by an activity $\lambda$, we study the critical activity $\lambda_c(\mathbb{Z}^2)$ for the uniqueness/nonuniqueness threshold on the 2-dimensional integer lattice $\mathbb{Z}^2$. The conjectured value of the critical activity is approximately 3.796. Until recently, the best lower bound followed from algorithmic results of Weitz [Proceedings of the $38$th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 140--149]. Weitz presented a fully polynomial-time approximation scheme for approximating the partition function for graphs of constant maximum degree $\Delta$ when $\lambda<\lambda_c(\mathbb{T}_\Delta)$, where $\mathbb{T}_\Delta$ is the infinite, regular tree of degree $\Delta$. His result established a certain decay of correlations property called strong spatial mixing (SSM) on $\mathbb{Z}^2$ by proving that SSM holds on its self-avoiding walk tree $T_{\mathrm{saw}}^\sigma(\mathbb{Z}^2)$, where $\sigma=(\sigma_v)_{v\in \mathbb{Z}^2}$ and $\sigma_v$ is an ordering on the neighbors of vertex $v$. As a consequence he obtained that $\lambda_c(\mathbb{Z}^2)\geq\lambda_c( \mathbb{T}_4) = 1.675$. Restrepo et al. [Probab. Theory Related Fields, 156 (2013), pp. 75--99] improved Weitz's approach for the particular case of $\mathbb{Z}^2$ and obtained that $\lambda_c(\mathbb{Z}^2)>2.388$. In this paper, we establish an upper bound for this approach, by showing that, for all $\sigma$, SSM does not hold on $T_{\mathrm{saw}}^\sigma(\mathbb{Z}^2)$ when $\lambda>3.4$. We also present a refinement of the approach of Restrepo et al. which improves the lower bound to $\lambda_c(\mathbb{Z}^2)>2.48$.

AB - For the hard-core lattice gas model defined on independent sets weighted by an activity $\lambda$, we study the critical activity $\lambda_c(\mathbb{Z}^2)$ for the uniqueness/nonuniqueness threshold on the 2-dimensional integer lattice $\mathbb{Z}^2$. The conjectured value of the critical activity is approximately 3.796. Until recently, the best lower bound followed from algorithmic results of Weitz [Proceedings of the $38$th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 140--149]. Weitz presented a fully polynomial-time approximation scheme for approximating the partition function for graphs of constant maximum degree $\Delta$ when $\lambda<\lambda_c(\mathbb{T}_\Delta)$, where $\mathbb{T}_\Delta$ is the infinite, regular tree of degree $\Delta$. His result established a certain decay of correlations property called strong spatial mixing (SSM) on $\mathbb{Z}^2$ by proving that SSM holds on its self-avoiding walk tree $T_{\mathrm{saw}}^\sigma(\mathbb{Z}^2)$, where $\sigma=(\sigma_v)_{v\in \mathbb{Z}^2}$ and $\sigma_v$ is an ordering on the neighbors of vertex $v$. As a consequence he obtained that $\lambda_c(\mathbb{Z}^2)\geq\lambda_c( \mathbb{T}_4) = 1.675$. Restrepo et al. [Probab. Theory Related Fields, 156 (2013), pp. 75--99] improved Weitz's approach for the particular case of $\mathbb{Z}^2$ and obtained that $\lambda_c(\mathbb{Z}^2)>2.388$. In this paper, we establish an upper bound for this approach, by showing that, for all $\sigma$, SSM does not hold on $T_{\mathrm{saw}}^\sigma(\mathbb{Z}^2)$ when $\lambda>3.4$. We also present a refinement of the approach of Restrepo et al. which improves the lower bound to $\lambda_c(\mathbb{Z}^2)>2.48$.

KW - approximate counting

KW - MCMC

KW - strong spatial mixing

KW - branching matrices

KW - linear programming

UR - http://epubs.siam.org/doi/abs/10.1137/140976923

U2 - 10.1137/140976923

DO - 10.1137/140976923

M3 - Article

VL - 29

SP - 1895

EP - 1915

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 4

ER -