{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:55Z","timestamp":1747173535654,"version":"3.40.5"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give algorithms for approximating the partition function of the ferromagnetic <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000087_inline1.png\"\/><jats:tex-math>\n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-color Potts model on graphs of maximum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000087_inline2.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our primary contribution is a fully polynomial-time approximation scheme for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000087_inline3.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-regular graphs with an expansion condition at low temperatures (that is, bounded away from the order-disorder threshold). The expansion condition is much weaker than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models; we use extremal graph theory and applications of Karger\u2019s algorithm to count cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We also obtain efficient algorithms in the Gibbs uniqueness region for bounded-degree graphs. While our high-temperature proof follows more standard polymer model analysis, our result holds in the largest-known range of parameters <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000087_inline4.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000087_inline5.png\"\/><jats:tex-math>\n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548324000087","type":"journal-article","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T08:43:29Z","timestamp":1712306609000},"page":"487-517","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for the ferromagnetic Potts model on expanders"],"prefix":"10.1017","volume":"33","author":[{"given":"Charlie","family":"Carlson","sequence":"first","affiliation":[]},{"given":"Ewan","family":"Davies","sequence":"additional","affiliation":[]},{"given":"Nicolas","family":"Fraiman","sequence":"additional","affiliation":[]},{"given":"Alexandra","family":"Kolla","sequence":"additional","affiliation":[]},{"given":"Aditya","family":"Potukuchi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3762-8865","authenticated-orcid":false,"given":"Corrine","family":"Yap","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"key":"S0963548324000087_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90204-7"},{"key":"S0963548324000087_ref36","first-page":"56","article-title":"On the number of independent sets in extenders","volume":"13","author":"Sapozhenko","year":"2001","journal-title":"Diskretnaya Matematika"},{"key":"S0963548324000087_ref37","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"S0963548324000087_ref39","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"S0963548324000087_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-020-00956-9"},{"key":"S0963548324000087_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20536"},{"key":"S0963548324000087_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/18M1219722"},{"key":"S0963548324000087_ref19","doi-asserted-by":"publisher","DOI":"10.1137\/140997580"},{"key":"S0963548324000087_ref12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.38.2009"},{"key":"S0963548324000087_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"S0963548324000087_ref33","first-page":"60","article-title":"Problem 28","volume":"10","author":"Mantel","year":"1907","journal-title":"Wiskundige Opgaven"},{"key":"S0963548324000087_ref35","first-page":"42","article-title":"On the number of connected subsets with given cardinality of the boundary in bipartite graphs","volume":"45","author":"Sapozhenko","year":"1987","journal-title":"Metody Diskretnogo Analiza"},{"key":"S0963548324000087_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20569"},{"key":"S0963548324000087_ref27","unstructured":"[27] Karger, D. R. (1993) Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201993, USA, January 1993. Society for Industrial and Applied Mathematics, pp. 21-30."},{"key":"S0963548324000087_ref8","unstructured":"[8] Coulson, M., Davies, E., Kolla, A., Patel, V. and Regts, G. (2020) Statistical physics approaches to Unique Games. In 35th Computational Complexity Conference (CCC 2020), Vol. 169 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, pp. 13:1\u201313:27."},{"key":"S0963548324000087_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51829-9"},{"key":"S0963548324000087_ref7","unstructured":"[7] Carlson, C. , Davies, E. and Kolla, A. (2020) Efficient algorithms for the Potts model on small-set expanders."},{"key":"S0963548324000087_ref34","unstructured":"[34] Potukuchi, A. and Yepremyan, L. (2021) Enumerating independent sets in Abelian Cayley graphs. arXiv, abs\/2109.06152."},{"key":"S0963548324000087_ref21","unstructured":"[21] Helmuth, T. , Jenssen, M. and Perkins, W. (2020) Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs."},{"key":"S0963548324000087_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"S0963548324000087_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.24"},{"key":"S0963548324000087_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04093-z"},{"key":"S0963548324000087_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3470865"},{"key":"S0963548324000087_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371660"},{"year":"1980","author":"Kleitman","key":"S0963548324000087_ref30"},{"year":"2005","author":"Sokal","key":"S0963548324000087_ref38"},{"key":"S0963548324000087_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211762"},{"key":"S0963548324000087_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"S0963548324000087_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651334"},{"key":"S0963548324000087_ref28","volume-title":"The Art of Computer Programming","volume":"1-3","author":"Knuth","year":"1998"},{"key":"S0963548324000087_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20968"},{"key":"S0963548324000087_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384271"},{"key":"S0963548324000087_ref15","first-page":"1","article-title":"Optimal bounds for the \n\n\n\n$k$\n\n\n-cut problem","volume":"69","author":"Gupta","year":"2021","journal-title":"ACM J. ACM (JACM)"},{"key":"S0963548324000087_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01247839"},{"key":"S0963548324000087_ref23","article-title":"Algorithmic Pirogov\u2013Sinai theory","author":"Helmuth","year":"2019","journal-title":"Prob. Theory Relat. Fields"},{"key":"S0963548324000087_ref22","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548324000087_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/19M1286669"},{"key":"S0963548324000087_ref25","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12331"},{"key":"S0963548324000087_ref3","unstructured":"[3] Blanca, A. , Cannon, S. and Perkins, W. (2022) Fast and perfect sampling of subgraphs and polymer systems."},{"key":"S0963548324000087_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-023-04644-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T16:08:28Z","timestamp":1728403708000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000087\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,5]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["S0963548324000087"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000087","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,4,5]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}