{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T07:39:16Z","timestamp":1780472356985,"version":"3.54.1"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T00:00:00Z","timestamp":1652400000000},"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":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show that the diameter of a uniformly drawn spanning tree of a simple connected graph on <jats:italic>n<\/jats:italic> vertices with minimal degree linear in <jats:italic>n<\/jats:italic> is typically of order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000062_inline1.png\"\/><jats:tex-math>\n$\\sqrt{n}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. A byproduct of our proof, which is of independent interest, is that on such graphs the Cheeger constant and the spectral gap are comparable.<\/jats:p>","DOI":"10.1017\/s0963548322000062","type":"journal-article","created":{"date-parts":[[2022,5,13]],"date-time":"2022-05-13T07:16:02Z","timestamp":1652426162000},"page":"1010-1030","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["The diameter of the uniform spanning tree of dense graphs"],"prefix":"10.1017","volume":"31","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Asaf","family":"Nachmias","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matan","family":"Shalev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2022,5,13]]},"reference":[{"key":"S0963548322000062_ref12","doi-asserted-by":"publisher","DOI":"10.1214\/154957805100000140"},{"key":"S0963548322000062_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"S0963548322000062_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989404"},{"key":"S0963548322000062_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"},{"key":"S0963548322000062_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"S0963548322000062_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990534"},{"key":"S0963548322000062_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"S0963548322000062_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-020-00999-2"},{"key":"S0963548322000062_ref11","first-page":"557","article-title":"Bounds on the","volume":"309","author":"Lawler","year":"1988","journal-title":"Trans. Am. Math. Soc."},{"key":"S0963548322000062_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0071532"},{"key":"S0963548322000062_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990534"},{"key":"S0963548322000062_ref14","unstructured":"[14] Levin, D. A. and Peres, Y. (2017) Markov Chains and Mixing Times, American Mathematical Society, Providence, RI. Second edition of [ MR2466937], With contributions by Elizabeth L. Wilmer, With a chapter on \u201cCoupling from the past\u201d by James G. Propp and David B. Wilson. Available at https:\/\/pages.uoregon.edu\/dlevin\/MARKOV\/mcmt2e.pdf."},{"key":"S0963548322000062_ref9","unstructured":"[9] Kolchin, V. F. (1986) Random Mappings, Translation Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York,. Translated from the Russian, With a foreword by S. R. S. Varadhan."},{"key":"S0963548322000062_ref17","unstructured":"[17] Peres, Y. and Revelle, D. (2004) Scaling limits of the uniform spanning tree and loop-erased random walk onfinite graphs, arXiv Mathematics e-prints, available at math\/0410430."},{"key":"S0963548322000062_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129716"},{"key":"S0963548322000062_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488611"},{"key":"S0963548322000062_ref15","volume-title":"Vol. 42 of Cambridge Series in Statistical and Probabilistic Mathematics","author":"Lyons","year":"2016"},{"key":"S0963548322000062_ref13","doi-asserted-by":"publisher","DOI":"10.5802\/afst.1112"},{"key":"S0963548322000062_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000639"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000062","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,13]],"date-time":"2022-10-13T04:52:15Z","timestamp":1665636735000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000062\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,13]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["S0963548322000062"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000062","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,13]]},"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"}}]}}