{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T06:02:10Z","timestamp":1771480930593,"version":"3.50.1"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T00:00:00Z","timestamp":1652227200000},"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":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The random-cluster model is a unifying framework for studying random graphs, spin systems and electrical networks that plays a fundamental role in designing efficient Markov Chain Monte Carlo (MCMC) sampling algorithms for the classical ferromagnetic Ising and Potts models. In this paper, we study a natural non-local Markov chain known as the <jats:italic>Chayes\u2013Machta (CM) dynamics<\/jats:italic> for the mean-field case of the random-cluster model, where the underlying graph is the complete graph on <jats:italic>n<\/jats:italic> vertices. The random-cluster model is parametrised by an <jats:italic>edge probability p<\/jats:italic> and a <jats:italic>cluster weight q<\/jats:italic>. Our focus is on the critical regime: <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000037_inline1.png\"\/><jats:tex-math>\n$p = p_c(q)$\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=\"S0963548322000037_inline2.png\"\/><jats:tex-math>\n$q \\in (1,2)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000037_inline3.png\"\/><jats:tex-math>\n$p_c(q)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the threshold corresponding to the order\u2013disorder phase transition of the model. We show that the mixing time of the CM dynamics is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000037_inline4.png\"\/><jats:tex-math>\n$O({\\log}\\ n \\cdot \\log \\log n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in this parameter regime, which reveals that the dynamics does not undergo an exponential slowdown at criticality, a surprising fact that had been predicted (but not proved) by statistical physicists. This also provides a nearly optimal bound (up to the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000037_inline5.png\"\/><jats:tex-math>\n$\\log\\log n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> factor) for the mixing time of the mean-field CM dynamics in the only regime of parameters where no non-trivial bound was previously known. Our proof consists of a multi-phased coupling argument that combines several key ingredients, including a new local limit theorem, a precise bound on the maximum of symmetric random walks with varying step sizes and tailored estimates for critical random graphs. In addition, we derive an improved comparison inequality between the mixing time of the CM dynamics and that of the local Glauber dynamics on general graphs; this results in better mixing time bounds for the local dynamics in the mean-field setting.<\/jats:p>","DOI":"10.1017\/s0963548322000037","type":"journal-article","created":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T04:46:05Z","timestamp":1652244365000},"page":"924-975","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["The critical mean-field Chayes\u2013Machta dynamics"],"prefix":"10.1017","volume":"31","author":[{"given":"Antonio","family":"Blanca","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alistair","family":"Sinclair","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xusheng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,5,11]]},"reference":[{"key":"S0963548322000037_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20868"},{"key":"S0963548322000037_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/19-AAP1505"},{"key":"S0963548322000037_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-011-0353-8"},{"key":"S0963548322000037_ref7","unstructured":"[7] Blanca, A. and Sinclair, A. (2015) Dynamics for the mean-field random-cluster model. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pp. 528\u2013543."},{"key":"S0963548322000037_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0725-1"},{"key":"S0963548322000037_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20088"},{"key":"S0963548322000037_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020405"},{"key":"S0963548322000037_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-016-2759-8"},{"key":"S0963548322000037_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.129"},{"key":"S0963548322000037_ref20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.118"},{"key":"S0963548322000037_ref30","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.58.86"},{"key":"S0963548322000037_ref23","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/058"},{"key":"S0963548322000037_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32891-9"},{"key":"S0963548322000037_ref31","doi-asserted-by":"publisher","DOI":"10.1137\/120864003"},{"key":"S0963548322000037_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04093-z"},{"key":"S0963548322000037_ref24","author":"Long","year":"2011","journal-title":"A power law of order 1\/4 for critical mean-field Swendsen-Wang dynamics"},{"key":"S0963548322000037_ref28","doi-asserted-by":"publisher","DOI":"10.1137\/1136086"},{"key":"S0963548322000037_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch37"},{"key":"S0963548322000037_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01213683"},{"key":"S0963548322000037_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(97)00637-7"},{"key":"S0963548322000037_ref22","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"S0963548322000037_ref15","unstructured":"[15] Galanis, A. , \u0160tefankovi\u010d, D. and Vigoda, E. (2015) Swendsen-Wang algorithm on the mean-field Potts model. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pp. 815\u2013828."},{"key":"S0963548322000037_ref29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010306"},{"key":"S0963548322000037_ref27","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1994-1138950-5"},{"key":"S0963548322000037_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0031-8914(72)90045-6"},{"key":"S0963548322000037_ref11","doi-asserted-by":"publisher","DOI":"10.24033\/asens.2485"},{"key":"S0963548322000037_ref21","unstructured":"[21] Janson, S. , \u0141uczak, T. and Ruci\u0143ski, A. (2011) Random Graphs, Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc."},{"key":"S0963548322000037_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1941-0003498-3"},{"key":"S0963548322000037_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S0963548322000037_ref13","volume-title":"Cambridge Series in Statistical and Probabilistic Mathematics","author":"Durrett","year":"2010"},{"key":"S0963548322000037_ref32","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"S0963548322000037_ref16","unstructured":"[16] Garoni, T. (2015) Personal communication."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,13]],"date-time":"2022-10-13T04:52:26Z","timestamp":1665636746000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000037\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,11]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["S0963548322000037"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000037","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,11]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. 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"}]}}