Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-02T21:37:13.787Z Has data issue: false hasContentIssue false
  • English
  • Français

New Graph Polynomials from the Bethe Approximation of the Ising Partition Function

Published online by Cambridge University Press:  30 June 2010

Y. WATANABE  and
K. FUKUMIZU
Y. WATANABE
Affiliation:
The Institute of Statistical Mathematics, 10-3 Midori-cho, Tachikawa, Tokyo 190-8562, Japan (e-mail: [email protected], [email protected])
K. FUKUMIZU
Affiliation:
The Institute of Statistical Mathematics, 10-3 Midori-cho, Tachikawa, Tokyo 190-8562, Japan (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce two graph polynomials and discuss their properties. One is a polynomial of two variables whose investigation is motivated by the performance analysis of the Bethe approximation of the Ising partition function. The other is a polynomial of one variable that is obtained by the specialization of the first one. It is shown that these polynomials satisfy deletion–contraction relations and are new examples of the V-function, which was introduced by Tutte (Proc. Cambridge Philos. Soc.43, 1947, p. 26). For these polynomials, we discuss the interpretations of special values and then obtain the bound on the number of sub-coregraphs, i.e., spanning subgraphs with no vertices of degree one. It is proved that the polynomial of one variable is equal to the monomer–dimer partition function with weights parametrized by that variable. The properties of the coefficients and the possible region of zeros are also discussed for this polynomial.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 2 , March 2011 , pp. 299 - 320
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Andrén, D. and Markström, K. (2009) The bivariate Ising polynomial of a graph. Discrete Appl. Math. 157 2515–2524.CrossRefGoogle Scholar
[2]Bethe, H. A. (1935) Statistical theory of superlattices. Proc. Royal Soc. London A 150 552–75.Google Scholar
[3]Bollobás, B. (1984) The evolution of random graphs. Trans. Amer. Math. Soc. 286 257–274.CrossRefGoogle Scholar
[4]Bollobás, B. (1998) Modern Graph Theory, Springer.CrossRefGoogle Scholar
[5]Bollobás, B., Pebody, L. and Riordan, O. (2000) Contraction–deletion invariants for graphs. J. Combin. Theory Ser. B 80 320–345.CrossRefGoogle Scholar
[6]Bollobás, B. and Riordan, O. (1999) A Tutte polynomial for coloured graphs. Combin. Probab. Comput. 8 45–93.CrossRefGoogle Scholar
[7]Chernyak, V. Y. and Chertkov, M. (2008) Fermions and loops on graphs II: A monomer–dimer model as a series of determinants. J. Statist. Mech. 12 P12012.CrossRefGoogle Scholar
[8]Chertkov, M. and Chernyak, V. Y. (2006) Loop calculus in statistical physics and information science. Phys. Rev. E 73 65102.CrossRefGoogle ScholarPubMed
[9]Chertkov, M. and Chernyak, V. Y. (2006) Loop series for discrete statistical models on graphs. J. Statist. Mech: Theory Exp. 6 P06009.Google Scholar
[10]Domb, C. (1960) On the theory of cooperative phenomena in crystals. Adv. Physics 9 149–244.CrossRefGoogle Scholar
[11]Ellis-Monaghan, J. and Merino, C. (2010) Graph polynomials and their applications I: The Tutte polynomial. In Structural Analysis of Complex Networks, Birkhäuser, Boston.Google Scholar
[12]Fortuin, C. M. and Kasteleyn, P. W. (1972) On the random-cluster model I: Introduction and relation to other models. Physica 57 536–564.CrossRefGoogle Scholar
[13]Godsil, C. D. and Gutman, I. (1981) On the theory of the matching polynomial. J. Graph Theory 5 137–144.CrossRefGoogle Scholar
[14]Gómez, V., Mooij, J. M. and Kappen, H. J. (2007) Truncating the loop series expansion for belief propagation. J. Machine Learning Research 8 1987–2016.Google Scholar
[15]Heilmann, O. J. and Lieb, E. H. (1972) Theory of monomer–dimer systems. Comm. Math. Phys. 25 190–232.CrossRefGoogle Scholar
[16]Loebl, M. (2007) Chromatic polynomial, q-binomial counting and colored Jones function. Adv. Math. 211 546–565.CrossRefGoogle Scholar
[17]McEliece, R. J., MacKay, D. J. C. and Cheng, J. F. (1998) Turbo decoding as an instance of Pearl's ‘belief propagation’ algorithm. IEEE J. Sel. Areas Comm. 16 140–52.CrossRefGoogle Scholar
[18]Nagle, J. F. (1966) New series-expansion method for the dimer problem. Phys. Rev. 152 190–197.CrossRefGoogle Scholar
[19]Nagle, J. F. (1971) A new subgraph expansion for obtaining coloring polynomials for graphs. J. Combin. Theory Ser. B 10 42–59.CrossRefGoogle Scholar
[20]Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan-Kaufmann.Google Scholar
[21]Pittel, B. and Wormald, N. C. (2005) Counting connected graphs inside-out. J. Combin. Theory Ser. B 93 127–172.CrossRefGoogle Scholar
[22]Riordan, O. (2007) The k-core and branching processes. Combin. Probab. Comput. 17 111–136.CrossRefGoogle Scholar
[23]Sokal, A. D. (2001) Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combin. Probab. Comput. 10 41–77.CrossRefGoogle Scholar
[24]Stallings, J. R. (1983) Topology of finite graphs. Invent. Math. 71 551–565.CrossRefGoogle Scholar
[25]Stark, H. M. and Terras, A. A. (1996) Zeta functions of finite graphs and coverings. Adv. Math. 121 124–165.CrossRefGoogle Scholar
[26]Traldi, L. (1989) A dichromatic polynomial for weighted graphs and link polynomials. Proc. Amer. Math. Soc. 106 279–286.CrossRefGoogle Scholar
[27]Tutte, W. T. (1947) A ring in graph theory. Proc. Cambridge Philos. Soc. 43 26–44.CrossRefGoogle Scholar
[28]van der Waerden, B. L. (1941) Die lange Reichweite der regelmässigen Atomanordnung in Mischkristallen. Z. Physik A: Hadrons and Nuclei 118 473–488.CrossRefGoogle Scholar
[29]Watanabe, Y. and Fukumizu, K. (2009) Graph zeta function in the Bethe free energy and loopy belief propagation. Adv. Neural Information Processing Systems 22 2017–2025.Google Scholar
[30]Watanabe, Y. and Fukumizu, K. (2009) Loop series expansion with propagation diagrams. J. Phys. A: Math. and Theor. 42 045001.CrossRefGoogle Scholar
[31]Welsh, D. J. A. (1993) Complexity: Knots, Colourings and Counting, Cambridge University Press.CrossRefGoogle Scholar
[32]Yang, T. D. and Lee, C. N. (1952) Statistical theory of equations of state and phase transitions I: Theory of condensation. Phys. Rev. 87 404–409.CrossRefGoogle Scholar
[33]Yedidia, J. S., Freeman, W. T. and Weiss, Y. (2001) Generalized belief propagation. Adv. Neural Information Processing Systems 13 689–95.Google Scholar