Counting independent sets up to the tree threshold

ABSTRACT

Consider the problem of approximately counting weighted independent sets of a graph G with activity λ, i.e., where the weight of an independent set I is λ^|I|. We present a novel analysis yielding a deterministic approximation scheme which runs in polynomial time for any graph of maximum degree Δ and λ< λ_c=(Δ-1)^Δ-1/(Δ-2)^Δ. This improves on the previously known general bound of λ ≤ (2 ‾ Δ-2). The new regime includes the interesting case of λ=1 (uniform weights) and Δ ≤ 5. The previous bound required Δ ≤ 4 for uniform approximate counting and there is evidence that for Δ ≥ 6 the problem is hard. Note that λ_c is the critical activity for uniqueness of the Gibbs measure on the regular tree of degree Δ, i.e., for λ ≤ λ_c the probability that the root is in the independent set is asymptotically independent of the configuration on the leaves far below. Indeed, our analysis is focused on establishing decay of correlations with distance in the above weighted distribution. We show that on any graph of maximum degree Δ correlations decay with distance at least as fast as they do on the regular tree of the same degree. This resolves an open conjecture in statistical physics. Our comparison of a general graph with the tree uses an algorithmic argument yielding the approximation scheme mentioned above. Also, by existing arguments, establishing decay of correlations for all graphs and λ<λ_c gives that the Glauber dynamics is rapidly mixing in this regime. However, the implication from decay of correlations to rapid mixing of the dynamics is only known to hold for graphs of subexponential growth, and hence, our result regarding the Glauber dynamics is limited to this class of graphs.

REFERENCES

• 1: J. van den Berg , A. Ermakov, A new lower bound for the critical probability of site percolation on the square lattice, Random Structures & Algorithms, v.8 n.3, p.199-212, May 1996 [doi>10.1002/(SICI)1098-2418(199605)8:3<199::AID-RSA4>3.0.CO;2-T]
• 2: J. van den Berg and J. Steif, "Percolation and the hard-core lattice gas model," Stochastic Processes and their Applications 49 (1994), pp. 179--197.
• 3: G. Brightwell, O. Häggström and P. Winkler, "Nonmonotonic behavior in hard-core and Widom-Rowlinson models," J. Stat. Physics 94 (1999), pp. 415--435.
• 4: F. Cesi, "Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields," Probability Theory and Related Fields 120 (2001), pp. 569--584.
• 5: R.L. Dobrushin, J. Kolafa, S.B. Shlosman, "Phase diagram of a two-dimensional Ising antiferromagnet (computer assisted proof)," Comm. Math. Phys. 102 (1985), pp. 89--103.
• 6: R.L. Dobrushin and S.B. Shlosman, "Constructive criterion for the uniqueness of a Gibbs field," in: J. Fritz, A. Jaffe, D. Szasz, Statistical mechanics and dynamical systems, Birkhauser, Boston (1985), pp. 347--370.
• 7: Martin Dyer , Alan Frieze , Mark Jerrum, On Counting Independent Sets in Sparse Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.210, October 17-18, 1999
• 8: Martin Dyer , Catherine Greenhill, On Markov chains for independent sets, Journal of Algorithms, v.35 n.1, p.17-49, April 2000 [doi>10.1006/jagm.1999.1071]
• 9: Martin Dyer , Alistair Sinclair , Eric Vigoda , Dror Weitz, Mixing in time and space for lattice spin systems: A combinatorial view, Random Structures & Algorithms, v.24 n.4, p.461-479, July 2004 [doi>10.1002/rsa.v24:4]
• 10: M. Fisher and M. Sykes, "Excluded volume problem and the Ising model of ferromagnetism," Physical Review 114 (1959), pp. 45--58.
• 11: Leslie Ann Goldberg , Russell Martin , Mike Paterson, Strong Spatial Mixing for Lattice Graphs with Fewer Colours, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.562-571, October 17-19, 2004 [doi>10.1109/FOCS.2004.63]
• 12: N. Halman, D. Klabjan, M. Mostagir, J. Orlin and D. Simchi-Levi, "A fully polynomial time approximation scheme for single-item stochastic lot-sizing problems with discrete demand," submitted for publication, 2006.
• 13: Tom Hayes , Eric Vigoda, Coupling with the stationary distribution and improved sampling for colorings and independent sets, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 14: F.P. Kelly, "Stochastic models of computer communication systems," Journal of the Royal Statistical Society B 47 (1985), pp. 379--395.
• 15: A.B. Kirillov, D.C. Radulescu and D.F. Styer, "Vassertein distances in two-state systems," J. Stat. Phys. 56 (1989), pp. 931--937.
• 16: Michael Luby , Eric Vigoda, Approximately counting up to four (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.682-687, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258663]
• 17: F. Martinelli and E. Olivieri, "Approach to equilibrium of Glauber dynamics in the one phase region I: The attractive case," Comm. Math. Phys. 161 (1994), pp. 447--486.
• 18: Fabio Martinelli , Alistair Sinclair , Dror Weitz, Fast mixing for independent sets, colorings and other models on trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 19: Dan Constantin Radulescu , Joel L. Lebowitz, A computer-assisted proof of uniqueness of phase for the hard-square lattice gas model in two dimensions, 1997
• 20: A. D. Scott and A. D. Sokal, "The repulsive lattice gas, the independent-set polynomial, and the Lovasz local lemma," J. Stat. Phys. 118 (2005), pp. 1151--1261.
• 21: A. D. Sokal, "A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models," Markov Process. Related Fields 7 (2001), pp. 21--38.
• 22: F. Spitzer, "Markov random fields on an infinite tree," Annals of Probability 3 (1975), pp. 387--398.
• 23: D.W. Stroock and B. Zegarlinski, "The logarithmic Sobolev inequality for discrete spin systems on a lattice," Comm. Math. Phys. 149 (1992), pp. 175--194.
• 24: E. Vigoda, "A note on the Glauber dynamics for sampling independent sets," Electronic Journal of Combinatorics 8(1) (2001).
• 25: Dror Weitz , Alistair Sinclair, Mixing in time and space for discrete spin systems, 2004

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Glauber dynamics, approximate counting, hard-core model, independent sets, strong spatial mixing