Improved mixing condition on the grid for counting and sampling independent sets (Q1955841): Difference between revisions

The authors study phase transitions for sampling weighted (by an activity \(\lambda\)) independent sets of the two-dimensional integer lattice, and their paper is based upon the work by Weitz who derived some results on the counting of independent sets up to the tree threshold. This problem has many practical applications and is involved, for instance, in the computational complexity of the partition function in physics. The background is based on weak and strong spatial mixing, and on self-avoiding walk tree representation. Strong spatial mixing (SSM) and weak spatial mixing (WSM) are defined, which can be understood by the following intuition. If a pair of boundary configurations on a subset \(S\) agrees at some vertices in \(S\), then those vertices encourage \(v\) to agree. The contribution of the paper is a criterion which achieves better bounds (than those of Weitz) on SSM for trees when the trees have extra structure. The relation with the Ising model is outlined in the conclusion.