Mathematics – Probability

Scientific paper

[
0.00
] – not rated yet
Voters
0
Comments 0

2011-05-04

Mathematics

Probability

Corrected a few small typos in earlier version

Scientific paper

We study the hard-core model defined on independent sets, where each independent set I in a graph G is weighted proportionally to $\lambda^{|I|}$, for a positive real parameter $\lambda$. For large $\lambda$, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree $D\ge 3$, is a well known computationally challenging problem. More concretely, let $\lambda_c(T_D)$ denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite D-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified $\lambda_c(T_D)$ as a threshold where the hardness of estimating the above partition function undergoes a computational transition. We focus on the well-studied particular case of the square lattice $\integers^2$, and provide a new lower bound for the uniqueness threshold, in particular taking it well above $\lambda_c(T_4)$. Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to $\integers^2$ we prove that strong spatial mixing holds for all $\lambda<2.3882$, improving upon the work of Weitz that held for $\lambda<27/16=1.6875$. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution.

**Restrepo Ricardo**

Mathematics – Probability

Scientist

**Shin Jinwoo**

Computer Science – Networking and Internet Architecture

Scientist

**Tetali Prasad**

Mathematics – Probability

Scientist

**Vigoda Eric**

Biology – Quantitative Biology – Populations and Evolution

Scientist

**Yang Linji**

Mathematics – Probability

Scientist

No associations

LandOfFree

If you have personal experience with

Improved Mixing Condition on the Grid for Counting and Sampling Independent Setsdoes not yet have a rating. At this time, there are no reviews or comments for this scientific paper.Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets will most certainly appreciate the feedback.

Profile ID: LFWR-SCP-O-689962

Use Google custom search:

All data on this website is collected from public sources.
Our data reflects the most accurate information available at the time of publication.