Abstract
The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree Δ ≥ 3, is a well known computationally challenging problem. More concretely, let \({\lambda_c(\mathbb{T}_\Delta)}\) denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite Δ-regular tree; recent breakthrough results of Weitz (Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 140–149, 2006) and Sly (Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287–296, 2010) have identified \({\lambda_c(\mathbb{T}_\Delta)}\) 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 \({\mathbb{Z}^2}\) , and provide a new lower bound for the uniqueness threshold, in particular taking it well above \({\lambda_c(\mathbb{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 \({\mathbb{Z}^2}\) we prove that strong spatial mixing holds for all λ < 2.3882, improving upon the work of Weitz that held for λ < 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alm S.E.: Upper bounds for the connective constant of self-avoiding walks. Combin. Probab. Comput. 4(2), 115–136 (1993)
Arnon, D.S., Collins, G.E., McCallum, S.: Cylindrical algebraic decomposition I: the basic algorithm. SIAM J. Comput. 865–877 (1984)
Baxter R.J., Enting I.G., Tsang S.K.: Hard-square lattice gas. J. Stat. Phys. 22(4), 465–489 (1980)
Beffara, V., Duminil-Copin, H.: The self-dual point of the two-dimensional random cluster model is critical for q ≥ 1. Probab. Theory Relat. Fields. Preprint available from the arXiv at: http://arxiv.org/abs/1006.5073
van den Berg J., Ermakov A.: A new lower bound for the critical probability of site percolation on the square lattice. Random Struct. Algorithms 8(3), 199–212 (1996)
van den Berg J., Steif J.E.: Percolation and the hard-core lattice gas model. Stochastic Processes Appl. 49(2), 179–197 (1994)
Brightwell G.R., Häggström O., Winkler P.: Nonmonotonic behavior in hard-core and Widom–Rowlinson models. J. Stat. Phys. 94(3), 415–435 (1999)
Cesi F.: Quasi–factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probab. Theory Relat. Fields 120(4), 569–584 (2001)
Dobrushin R.L.: The problem of uniqueness of a Gibbsian random field and the problem of phase transitions. Funct. Anal. Appl. 2(4), 302–312 (1968)
Dobrushin R.L., Shlosman S.B.: Constructive unicity criterion. In: Fritz, J., Jaffe, A., Szasz, D. (eds) Statistical Mechanics and Dynamical Systems, pp. 347–370. Birkhäuser, New York (1985)
Dyer M.E., Sinclair A., Vigoda E., Weitz D.: Mixing in time and space for lattice spin systems: a combinatorial view. Random Struct. Algorithms 24(4), 461–479 (2004)
Galanis, A., Ge, Q., Štefankovič, D., Vigoda, E., Yang, L.: Improved inapproximability results for counting independent sets in the hard-core model. In: Proocedings of the 15th International Workshop, RANDOM, pp. 567–578 (2011)
Gaunt D.S., Fisher M.E.: Hard-sphere lattice gases. I. Plane-square lattice. J. Chem. Phys. 43(8), 2840–2863 (1965)
Georgii H.-O.: Gibbs Measures and Phase Transitions. de Gruyter, Berlin (1988)
Goldberg L., Martin R., Paterson M.: Strong spatial mixing for lattice graphs with fewer colours. SIAM J. Comput. 35(2), 486–517 (2005)
Greenhill C.: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complex. 9(1), 52–72 (2000)
Jerrum M.R., Valiant L.G., Vazirani V.V.: Random generation of combinatorial structures from a uniform distribution distribution. Theor. Comput. Sci. 43(2-3), 169–186 (1986)
Kelly F.P.: Loss networks. Ann. Appl. Probab. 1(3), 319–378 (1991)
Levin D.A., Peres Y., Wilmer E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2008)
Lyons R.: The Ising model and percolation on trees and tree-like graphs. Commun. Math. Phys. 125(2), 337–353 (1989)
Martinelli, F.: Lectures on Glauber dynamics for discrete spin models. In: Lectures on Probability Theory and Statistics (Saint-Flour, 1997), Lecture Notes in Mathematics, vol. 1717, pp. 93–191 (1998)
Martinelli F., Olivieri E.: Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Commun. Math. Phys. 161(3), 447–486 (1994)
Martinelli F., Olivieri E.: Approach to equilibrium of Glauber dynamics in the one phase region. II. The general case. Commun. Math. Phys. 161(3), 487–514 (1994)
Onsager L.: Crystal statistics. I. A two-dimensional model with an order–disorder transition. Phys. Rev. Lett. 65(3–4), 117–149 (1944)
Pönitz A., Tittman P.: Improved upper bounds for self-avoiding walks in \({\mathbb{Z}^d}\) . Electr. J. Combin. 7(1), R21 (2000)
Rácz Z.: Phase boundary of Ising antiferromagnets near H = H c and T = 0: results from hard-core lattice gas calculations. Phys. Rev. B 21(9), 4012–4016 (1980)
Radulescu, D.C.: A computer-assisted proof of uniqueness of phase for the hard-square lattice gas model in two dimensions. PhD dissertation, Rutgers University, New Brunswick, NJ, USA (1997)
Radulescu D.C., Styer D.F.: The Dobrushin–Shlosman phase uniqueness criterion and applications to hard squares. J. Stat. Phys. 49(1–2), 281–295 (1987)
Randall, D.: Slow mixing of Glauber dynamics via topological obstructions. In: Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 870–879 (2006)
Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287–296 (2010)
Štefankovič D., Vempala S., Vigoda E.: Adaptive simulated annealing: a near-optimal connection between sampling and counting. J. ACM 56(3), 1–36 (2009)
Tarski A.: A decision method for elementary algebra and geometry, 2nd edn. University of California Press, California (1951)
Valiant L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)
Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 140–149 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by NSF grants CCF-0830298 and CCF-0910584. Jinwoo Shin was supported by the Algorithms and Randomness Center at Georgia Technology.
Electronic Supplementary Material
The Below is the Electronic Supplementary Material.
Rights and permissions
About this article
Cite this article
Restrepo, R., Shin, J., Tetali, P. et al. Improved mixing condition on the grid for counting and sampling independent sets. Probab. Theory Relat. Fields 156, 75–99 (2013). https://doi.org/10.1007/s00440-012-0421-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-012-0421-8