No CrossRef data available.
Article contents
New Graph Polynomials from the Bethe Approximation of the Ising Partition Function
Published online by Cambridge University Press: 30 June 2010
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2010
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
[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
You have
Access
- 3
- Cited by