{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T20:08:46Z","timestamp":1758398926917},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the \u2018winding\u2019 technology devised by McQuillan [CoRR abs\/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514\u2013527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.<\/jats:p>","DOI":"10.1017\/s0963548321000080","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T10:43:31Z","timestamp":1618224211000},"page":"905-921","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Heinrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"S0963548321000080_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00056-6"},{"key":"S0963548321000080_ref7","doi-asserted-by":"publisher","DOI":"10.1063\/1.1704825"},{"key":"S0963548321000080_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000390"},{"key":"S0963548321000080_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"S0963548321000080_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2020.124671"},{"key":"S0963548321000080_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch38"},{"key":"S0963548321000080_ref24","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"S0963548321000080_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"S0963548321000080_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516520"},{"key":"S0963548321000080_ref2","unstructured":"[2] Bencs, F. , Csikv\u00e1ri, P. and Regts, G. (2020) Some applications of Wagner\u2019s weighted subgraph counting polynomial. arXiv:2012.00806."},{"key":"S0963548321000080_ref16","doi-asserted-by":"publisher","DOI":"10.1063\/1.1703953"},{"key":"S0963548321000080_ref19","unstructured":"[19] McQuillan, C. (2013) Approximating Holant problems by winding. CoRR, abs\/1301.2880."},{"key":"S0963548321000080_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"S0963548321000080_ref8","volume-title":"Statistical Mechanics of Lattice Systems","author":"Friedli","year":"2018"},{"key":"S0963548321000080_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90144-5"},{"key":"S0963548321000080_ref22","doi-asserted-by":"publisher","DOI":"10.1143\/ptp\/6.3.306"},{"key":"S0963548321000080_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9671-7"},{"key":"S0963548321000080_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/9781107477063"},{"key":"S0963548321000080_ref3","first-page":"14","article-title":"On the complexity of the maximum cut problem","volume":"7","author":"Bodlaender","year":"2000","journal-title":"Nordic J. Comput."},{"key":"S0963548321000080_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20002"},{"key":"S0963548321000080_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<229::AID-RSA3>3.0.CO;2-X"},{"key":"S0963548321000080_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"S0963548321000080_ref6","doi-asserted-by":"crossref","unstructured":"[6] Chen, Z. , Liu, K. and Vigoda, E. (2020) Rapid mixing of Glauber dynamics up to uniqueness via contraction. CoRR, abs\/2004.09083.","DOI":"10.1109\/FOCS46700.2020.00124"},{"key":"S0963548321000080_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9626-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T15:51:43Z","timestamp":1634313103000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000080\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,12]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["S0963548321000080"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000080","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,12]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}