{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T08:46:45Z","timestamp":1649148405317},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T00:00:00Z","timestamp":1277856000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>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\u2013contraction relations and are new examples of the V-function, which was introduced by Tutte (<jats:italic>Proc. Cambridge Philos. Soc.<\/jats:italic><jats:bold>43<\/jats:bold>, 1947, p. 26). For these polynomials, we discuss the interpretations of special values and then obtain the bound on the number of sub-coregraphs,<jats:italic>i.e.<\/jats:italic>, spanning subgraphs with no vertices of degree one. It is proved that the polynomial of one variable is equal to the monomer\u2013dimer 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.<\/jats:p>","DOI":"10.1017\/s0963548310000258","type":"journal-article","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T10:04:46Z","timestamp":1277892286000},"page":"299-320","source":"Crossref","is-referenced-by-count":3,"title":["New Graph Polynomials from the Bethe Approximation of the Ising Partition Function"],"prefix":"10.1017","volume":"20","author":[{"given":"Y.","family":"WATANABE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"FUKUMIZU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,6,30]]},"reference":[{"key":"S0963548310000258_ref18","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.152.190"},{"key":"S0963548310000258_ref29","first-page":"2017","article-title":"Graph zeta function in the Bethe free energy and loopy belief propagation","volume":"22","author":"Watanabe","year":"2009","journal-title":"Adv. Neural Information Processing Systems"},{"key":"S0963548310000258_ref30","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/42\/4\/045001"},{"key":"S0963548310000258_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/49.661103"},{"key":"S0963548310000258_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"S0963548310000258_ref26","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1989-0955462-3"},{"key":"S0963548310000258_ref5","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1988"},{"key":"S0963548310000258_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.02.021"},{"key":"S0963548310000258_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548310000258_ref33","first-page":"689","article-title":"Generalized belief propagation","volume":"13","author":"Yedidia","year":"2001","journal-title":"Adv. Neural Information Processing Systems"},{"key":"S0963548310000258_ref2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1935.0122"},{"key":"S0963548310000258_ref23","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1017\/S0963548300004612","article-title":"Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions","volume":"10","author":"Sokal","year":"2001","journal-title":"Combin. Probab. Comput."},{"key":"S0963548310000258_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01342928"},{"key":"S0963548310000258_ref22","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1017\/S0963548307008589","article-title":"The k-core and branching processes","volume":"17","author":"Riordan","year":"2007","journal-title":"Combin. Probab. Comput."},{"key":"S0963548310000258_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(71)90066-9"},{"key":"S0963548310000258_ref25","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1996.0050"},{"key":"S0963548310000258_ref7","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/12\/P12012"},{"key":"S0963548310000258_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003447"},{"key":"S0963548310000258_ref11","volume-title":"Structural Analysis of Complex Networks","author":"Ellis-Monaghan","year":"2010"},{"key":"S0963548310000258_ref10","doi-asserted-by":"publisher","DOI":"10.1080\/00018736000101189"},{"key":"S0963548310000258_ref8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.065102"},{"key":"S0963548310000258_ref32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.404"},{"key":"S0963548310000258_ref3","doi-asserted-by":"publisher","DOI":"10.2307\/1999405"},{"key":"S0963548310000258_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02095993"},{"key":"S0963548310000258_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511752506"},{"key":"S0963548310000258_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2006.09.001"},{"key":"S0963548310000258_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.005"},{"key":"S0963548310000258_ref14","first-page":"1987","article-title":"Truncating the loop series expansion for belief propagation","volume":"8","author":"G\u00f3mez","year":"2007","journal-title":"J. Machine Learning Research"},{"key":"S0963548310000258_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01877590"},{"key":"S0963548310000258_ref27","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100023173"},{"key":"S0963548310000258_ref9","first-page":"P06009","article-title":"Loop series for discrete statistical models on graphs","volume":"6","author":"Chertkov","year":"2006","journal-title":"J. Statist. Mech: Theory Exp."},{"key":"S0963548310000258_ref20","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl","year":"1988"},{"key":"S0963548310000258_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050203"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T08:10:08Z","timestamp":1591431008000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000258\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,30]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["S0963548310000258"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000258","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,30]]}}}