{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T08:33:46Z","timestamp":1771490026616,"version":"3.50.1"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T00:00:00Z","timestamp":1758240000000},"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":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The hard-core model has as its configurations the independent sets of some graph instance\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline2.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The probability distribution on independent sets is controlled by a \u2018fugacity\u2019\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline3.png\"\/>\n                        <jats:tex-math>$\\lambda \\gt 0$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , with higher\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline4.png\"\/>\n                        <jats:tex-math>$\\lambda$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    leading to denser configurations. We investigate the mixing time of Glauber (single-site) dynamics for the hard-core model on restricted classes of bounded-degree graphs in which a particular graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline5.png\"\/>\n                        <jats:tex-math>$H$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is excluded as an induced subgraph. If\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline6.png\"\/>\n                        <jats:tex-math>$H$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a subdivided claw then, for all\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline7.png\"\/>\n                        <jats:tex-math>$\\lambda$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , the mixing time is\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline8.png\"\/>\n                        <jats:tex-math>$O(n\\log n)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline9.png\"\/>\n                        <jats:tex-math>$n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is the order of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline10.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . This extends a result of Chen and Gu for claw-free graphs. When\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline11.png\"\/>\n                        <jats:tex-math>$H$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a path, the set of possible instances is finite. For all other\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline12.png\"\/>\n                        <jats:tex-math>$H$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , the mixing time is exponential in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline13.png\"\/>\n                        <jats:tex-math>$n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    for sufficiently large\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline14.png\"\/>\n                        <jats:tex-math>$\\lambda$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , depending on\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline15.png\"\/>\n                        <jats:tex-math>$H$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and the maximum degree of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325100163_inline16.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1017\/s0963548325100163","type":"journal-article","created":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:32:06Z","timestamp":1758267126000},"page":"803-814","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Glauber dynamics for the hard-core model on bounded-degree \n\n$H$\n-free graphs"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0863-7279","authenticated-orcid":false,"given":"Mark","family":"Jerrum","sequence":"first","affiliation":[{"name":"University of London"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,9,19]]},"reference":[{"key":"S0963548325100163_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/20M1347747"},{"key":"S0963548325100163_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/105051607000000104"},{"key":"S0963548325100163_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.06.001"},{"key":"S0963548325100163_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"S0963548325100163_ref26","doi-asserted-by":"publisher","DOI":"10.1063\/1.533198"},{"key":"S0963548325100163_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"S0963548325100163_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00290-1"},{"key":"S0963548325100163_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/20M136685X"},{"key":"S0963548325100163_ref27","first-page":"749","article-title":"Disagreement percolation in the study of Markov fields","volume":"22","author":"van den Berg","year":"1994","journal-title":"Ann. Probab."},{"key":"S0963548325100163_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"key":"S0963548325100163_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"S0963548325100163_ref10","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00023"},{"key":"S0963548325100163_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.61"},{"key":"S0963548325100163_ref8","unstructured":"[8] Bencs, F. (2019) Graphs, Groups and Measures (PhD thesis). Central European University."},{"key":"S0963548325100163_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9243-7"},{"key":"S0963548325100163_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451035"},{"key":"S0963548325100163_ref18","volume-title":"Statistical mechanics of lattice systems","author":"Friedli","year":"2018"},{"key":"S0963548325100163_ref20","volume-title":"Lectures in Mathematics ETH Z\u00fcrich","author":"Jerrum","year":"2003"},{"key":"S0963548325100163_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/20M1367696"},{"key":"S0963548325100163_ref23","unstructured":"[23] Matthews, J. (2008) Markov Chains for Sampling Matchings. PhD thesis. School of Informatics, University of Edinburgh. http:\/\/hdl.handle.net\/1842\/3072."},{"key":"S0963548325100163_ref21","volume-title":"Markov chains and mixing times, With a chapter by James G","author":"Levin","year":"2009"},{"key":"S0963548325100163_ref5","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2024.199.1.4"},{"key":"S0963548325100163_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1453"},{"key":"S0963548325100163_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548321000080"},{"key":"S0963548325100163_ref7","first-page":"81","article-title":"Asymptotically optimal switching circuits","volume":"17","author":"Bassalygo","year":"1981","journal-title":"Probl. Peredachi Informat."},{"key":"S0963548325100163_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(94)90132-5"},{"key":"S0963548325100163_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.178"},{"key":"S0963548325100163_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/20M1333778"},{"key":"S0963548325100163_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00471-X"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325100163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:04:46Z","timestamp":1763543086000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325100163\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,19]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["S0963548325100163"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325100163","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. 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, provided the original article 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"}]}}