Sequential cavity method for computing limits of the log-partition function for lattice models

ABSTRACT

One of the key computational problems in combinatorics/statistical physics is the problem of computing limits of the log-partition functions for various statistical mechanics models on lattices. In combinatorics this limit corresponds to the exponent of various arrangements on lattices, for example the exponents of the number of independent sets, proper colorings or matchings on a lattice. In statistical physics this limit is called free energy.

We propose a new method, sequential cavity, which beats the best known existing methods, such as transfer matrix method, in obtaining sharper bounds on the limits of the log-partition function for two models: independent sets (hard-core) and matchings (monomer-dimer). Our method is based on a surprisingly simple representation of the log-partition function limit in terms of a certain marginal probability of a suitably modified lattice, and using recent deterministic approximation counting algorithms for these two models. Our method also has a provably better theoretical performance compared with the transfer matrix method.

REFERENCES

• 1: David J. Aldous, The ζ (2) limit in the random assignment problem, Random Structures & Algorithms, v.18 n.4, p.381-418, July 2001 [doi>10.1002/rsa.1015]
• 2: {Bax68} R. J. Baxter, Dimers on a rectangular lattice, J. Math Phys. 9 (1968), 650--654.
• 3: {Bax80} R. J. Baxter, Hard hexagons: Exact solution, J. Phys. A 13 (1980), L61--L70.
• 4: {Bax99} R. J. Baxter, Planar lattice gases with nearest-neighbor exclusion, Annals of combinatorics 3 (1999), 191--203.
• 5: Mohsen Bayati , David Gamarnik , Dimitriy Katz , Chandra Nair , Prasad Tetali, Simple deterministic approximation algorithms for counting matchings, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250809]
• 6: {BMP99} J. Bertoin, F. Martinelli, and Y. Peres, Lectures on probability theory and statistics: Ecole d'Ete de Probabilites de Saint-Flour XXVII, Springer, 1999.
• 7: Neil J. Calkin , Herbert S. Wilf, The Number of Independent Sets in a Grid Graph, SIAM Journal on Discrete Mathematics, v.11 n.1, p.54-60, Feb. 1998 [doi>10.1137/S089548019528993X]
• 8: Shmuel Friedland , Leonid Gurvits, Lower bounds for partial matchings in regular bipartite graphs and applications to the monomer–dimer entropy, Combinatorics, Probability and Computing, v.17 n.3, p.347-361, May 2008 [doi>10.1017/S0963548307008747]
• 9: {Fis61} M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Physics Review 124 (1961), 16641672.
• 10: {FP05} S. Friedland and U. N. Peled, Theory of computation of multidimensional entropy with an application to monomer-dimer entropy, Advances in applied mathematics 34 (2005), 486--522.
• 11: {Geo88} H. O. Georgii, Gibbs measures and phase transitions, de Gruyter Studies in Mathematics 9, Walter de Gruyter & Co., Berlin, 1988.
• 12: David Gamarnik , Dmitriy Katz, Correlation decay and deterministic FPTAS for counting list-colorings of a graph, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1245-1254, January 07-09, 2007, New Orleans, Louisiana
• 13: {GK08} D. Gamarnik and D. Katz, Sequential cavity method for computing free energy and surface pressure, http://arxiv.org/abs/0807.1551 (2008).
• 14: {Ham66a} J. M. Hammersley, Existence theorems and Monte Carlo methods for the monomer-dimer problem, F. N. David (Ed.), Research Papers in Statistics: Festschrift for J. Neyman, Wiley, London, 1966, p. 125146.
• 15: {Ham66b} J. M. Hammersley, An improved lower bound for the multidimensional dimer problem, Proc. Cambridge Philos. Soc. 64 (1966), 455463.
• 16: {HL72} O. J. Heilman and E. H. Lieb, Theory of monomerdimer systems, Comm. Math. Phys. 25 (1972), 190--232.
• 17: {HM70} J. M. Hammersley and V. Menon, A lower bound for the monomer-dimer problem, J. Inst. Math. Appl. 6 (1970), 341364.
• 18: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 19: {Kas61} P. W. Kasteleyn, The statistics of dimers on a lattice I: The number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209--1225.
• 20: {KRS96} C. Kenyon, D. Randall, and A. Sinclair, Approximating the number of monomer-dimer coverings of a lattice, J. Statist. Phys. 83 (1996), 637659.
• 21: {MP87} M. Mezard and G. Parisi, On the solution of the random link matching problem, J. Physique 48 (1987), 1451--1459.
• 22: {MP03} M. Mezard and G. Parisi, The cavity method at zero temperature, Journal of Statistical Physics 111 (2003), no. 1--2, 1--34.
• 23: {RBMM04} O. Rivoire, G. Biroli, O. C. Martin, and M. Mezard, Glass models on Bethe lattices, Eur. Phys. J. B 37 (2004), 55--78.
• 24: {Sim93} B. Simon, The statistical mechanics of lattice gases, Vol. I, Princeton Series in Physics, Princeton University Press, Princeton, NJ, 1993.
• 25: {TF61} H. N. V. Temperley and M. E. Fisher, Dimer problem in statistical mechanics - an exact result, Philosophical Magazine 6 (1961), 10611063.
• 26: Dror Weitz, Counting independent sets up to the tree threshold, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132538]

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics