{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:27:55Z","timestamp":1740461275123,"version":"3.37.3"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T00:00:00Z","timestamp":1732579200000},"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":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, for generating a random independent set of a tree. Our focus is obtaining optimal convergence results for arbitrary trees. We consider the more general problem of sampling from the Gibbs distribution in the hard-core model where independent sets are weighted by a parameter <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline1.png\"\/><jats:tex-math>\n$\\lambda \\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>; the special case <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline2.png\"\/><jats:tex-math>\n$\\lambda =1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> corresponds to the uniform distribution over all independent sets. Previous work of Martinelli, Sinclair and Weitz (2004) obtained optimal mixing time bounds for the complete <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline3.png\"\/><jats:tex-math>\n$\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-regular tree for all <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline4.png\"\/><jats:tex-math>\n$\\lambda$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. However, Restrepo, Stefankovic, Vera, Vigoda, and Yang (2014) showed that for sufficiently large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline5.png\"\/><jats:tex-math>\n$\\lambda$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> there are bounded-degree trees where optimal mixing does not hold. Recent work of Eppstein and Frishberg (2022) proved a polynomial mixing time bound for the Glauber dynamics for arbitrary trees, and more generally for graphs of bounded tree-width.<\/jats:p><jats:p>We establish an optimal bound on the relaxation time (i.e., inverse spectral gap) of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline6.png\"\/><jats:tex-math>\n$O(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for the Glauber dynamics for unweighted independent sets on arbitrary trees. We stress that our results hold for arbitrary trees and there is no dependence on the maximum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline7.png\"\/><jats:tex-math>\n$\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Interestingly, our results extend (far) beyond the uniqueness threshold which is on the order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000348_inline8.png\"\/><jats:tex-math>\n$\\lambda =O(1\/\\Delta )$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our proof approach is inspired by recent work on spectral independence. In fact, we prove that spectral independence holds with a constant independent of the maximum degree for any tree, but this does not imply mixing for general trees as the optimal mixing results of Chen, Liu, and Vigoda (2021) only apply for bounded-degree graphs. We instead utilize the combinatorial nature of independent sets to directly prove approximate tensorization of variance via a non-trivial inductive proof.<\/jats:p>","DOI":"10.1017\/s0963548324000348","type":"journal-article","created":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T05:31:32Z","timestamp":1732599092000},"page":"259-275","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Optimal mixing via tensorization for random independent sets on arbitrary trees"],"prefix":"10.1017","volume":"34","author":[{"given":"Charilaos","family":"Efthymiou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas P.","family":"Hayes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,11,26]]},"reference":[{"key":"S0963548324000348_ref11","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00018"},{"key":"S0963548324000348_ref23","first-page":"32:1","volume-title":"APPROX-RANDOM","author":"Liu","year":"2021"},{"key":"S0963548324000348_ref30","doi-asserted-by":"publisher","DOI":"10.1137\/120885498"},{"key":"S0963548324000348_ref32","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"S0963548324000348_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516520"},{"key":"S0963548324000348_ref31","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"S0963548324000348_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451035"},{"key":"S0963548324000348_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20960"},{"key":"S0963548324000348_ref25","first-page":"191","volume-title":"Discrete Random Walks","author":"Martin","year":"2003"},{"key":"S0963548324000348_ref6","unstructured":"6. Caputo, P. (2023) Lecture notes on Entropy and Markov Chains. Preprint, available from: http:\/\/www.mat.uniroma3.it\/users\/caputo\/entropy.pdf."},{"key":"S0963548324000348_ref24","first-page":"631","volume-title":"Randomization and Approximation Techniques in Computer Science (RANDOM)","author":"Lucier","year":"2009"},{"key":"S0963548324000348_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/22M1474734"},{"key":"S0963548324000348_ref20","unstructured":"20. Efthymiou, C., Hayes, T. P., \u0160tefankovi\u010d, D. and Vigoda, E., (2023). Optimal mixing via tensorization for random independent sets on arbitrary trees. arXiv preprint arXiv:2307.07727, version 2."},{"key":"S0963548324000348_ref27","unstructured":"27. Martinelli, F. , Sinclair, A. and Weitz, D. (2004) Fast mixing for independent sets, colorings and other models on trees. pp. 456\u2013465, In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM."},{"key":"S0963548324000348_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0369-4"},{"key":"S0963548324000348_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.145"},{"key":"S0963548324000348_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238235"},{"key":"S0963548324000348_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04237-1"},{"key":"S0963548324000348_ref9","unstructured":"9. Chen, X. , Yang, X. , Yin, Y. , and Zhang, X. . Spectral independence beyond total influence on trees and related graphs. arXiv preprint arXiv:2404.04668, 2024."},{"key":"S0963548324000348_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00023"},{"key":"S0963548324000348_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20006"},{"key":"S0963548324000348_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00125"},{"key":"S0963548324000348_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.178"},{"key":"S0963548324000348_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/16-EJP3552"},{"key":"S0963548324000348_ref19","unstructured":"19. Eppstein, D. and Frishberg, D. (2023) Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs, pp. 30:1\u201330:13, In Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC), vol. 283. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik."},{"key":"S0963548324000348_ref7","first-page":"691","article-title":"Approximate tensorization of entropy at high temperature. Annales de la Facult\u00e9 des sciences de Toulouse","volume":"24","author":"Caputo","year":"2015","journal-title":"Math\u00e9matiques"},{"key":"S0963548324000348_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.179"},{"key":"S0963548324000348_ref28","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/063\/12"},{"key":"S0963548324000348_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"S0963548324000348_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-007-0131-9"},{"key":"S0963548324000348_ref22","doi-asserted-by":"publisher","DOI":"10.1214\/105051607000000104"},{"key":"S0963548324000348_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00062"},{"key":"S0963548324000348_ref15","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00053"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:38:48Z","timestamp":1740400728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000348\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,26]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["S0963548324000348"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000348","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,11,26]]},"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"}}]}}