Improved mixing condition on the grid for counting and sampling independent sets

Restrepo, Ricardo; Shin, Jinwoo; Tetali, Prasad; Vigoda, Eric; Yang, Linji
June 2013
Probability Theory & Related Fields;Jun2013, Vol. 156 Issue 1/2, p75
Academic Journal
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 λ, 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, ) and Sly (Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287-296, ) 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.


Related Articles

  • Study of the Critical Behavior of Nonequilibrium Systems: Application to Driven Diffusive Lattice Gases. Saracco, Gustavo P.; Albano, Ezequiel V. // AIP Conference Proceedings;2003, Vol. 661 Issue 1, p90 

    Due to the fact that there is not a standard theory for non-equilibrium behavior, it is useful to gain insight on these systems studying some archetypical models, such as the non-equilibrium lattice gas knew as the KLS model (Katz, Lebowitz and Spohn; Phys. Rev. B 28, 1665 (1983)). The KLS model...

  • Study of a First-Order Irreversible Phase Transition in the Yaldran-Khan Catalyzed Reaction Model. Loscar, E. S.; Albano, E. V. // AIP Conference Proceedings;2003, Vol. 661 Issue 1, p266 

    In this work is studied using the constant coverage (CC) ensemble and performing epidemic simulations the first-order irreversible phase transitions (IPT) of the Yaldran-Khan model for the CO + NO reaction [1]. The CC method allow the study of hysteretic effects close to coexistence as well as...

  • Discontinuous phase transition in a dimer lattice gas. Dickman, Ronald // Journal of Chemical Physics;5/7/2012, Vol. 136 Issue 17, p174105 

    I study a dimer model on the square lattice with nearest neighbor exclusion as the only interaction. Detailed simulations using tomographic entropic sampling show that as the chemical potential is varied, there is a strongly discontinuous phase transition, at which the particle density jumps by...

  • Hard square lattice gas. Baram, Asher; Fixman, Marshall // Journal of Chemical Physics;8/15/1994, Vol. 101 Issue 4, p3172 

    It is shown that the fluid branch of the hard square lattice gas terminates at a finite activity zf. Estimates of zf indicate that it is identical to the termination activity of the solid branch zs, found by Baxter, Enting, and Tsang [J. Stat. Phys. 22, 465 (1980)] to be at zs=3.7962(1),...

  • On the constructive role of noise in stabilizing itinerant trajectories in chaotic dynamical systems. Kozma, Robert // Chaos;Sep2003, Vol. 13 Issue 3, p1078 

    Studies dynamical models of neural networks which exhibits phase transitions between states of various complexities. Usage of biologically motivated KIII model; Features of the KIII model; Role of additive noise in the development if itinerant trajectories.

  • Dynamics of a Peierls system in a light field. Semenov, A. L. // Journal of Experimental & Theoretical Physics;Dec99, Vol. 89 Issue 6, p1168 

    Equations describing the temporal dynamics of the order parameter Ξ(t) of a metal-semiconductor phase transition and the density n(t) of electron-hole pairs in a Peierls system in a light field are obtained on the basis of the Lagrange equation for the phonon mode and the Liouville equation...

  • Berezinskiı—Kosterlitz—Thouless phase transitions in two-dimensional systems with internal symmetries. Bulgadaev, S. A. // Journal of Experimental & Theoretical Physics;Dec99, Vol. 89 Issue 6, p1107 

    The Berezinski...-Kosterlitz-Thouless (BKT) phase transitions in two-dimensional systems with internal continuous Abelian symmetries are investigated. In order for phase transitions to occur, the kinetic part of the action of the system must have conformal invariance, and the vacuum manifold...

  • CORRIGENDUM: A universal transition in the robustness of evolving open systems.  // Scientific Reports;12/19/2014, p1 

    A correction to the article "A universal transition in the robustness of evolving open systems," by Takashi Shimada in the February 13, 2014 issue is presented.

  • Phase Transition and Level-Set Percolation for the Gaussian Free Field. Rodriguez, Pierre-François; Sznitman, Alain-Sol // Communications in Mathematical Physics;Jun2013, Vol. 320 Issue 2, p571 

    We consider level-set percolation for the Gaussian free field on $${\mathbb{Z}^{d}}$$, d ≥ 3, and prove that, as h varies, there is a non-trivial percolation phase transition of the excursion set above level h for all dimensions d ≥ 3. So far, it was known that the corresponding...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics