{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:56Z","timestamp":1747173536669,"version":"3.40.5"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T00:00:00Z","timestamp":1716422400000},"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,11]]},"abstract":"Abstract<\/jats:title>We study the noise sensitivity of the minimum spanning tree (MST) of the \n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex complete graph when edges are assigned independent random weights. It is known that when the graph distance is rescaled by \n$n^{1\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and vertices are given a uniform measure, the MST converges in distribution in the Gromov\u2013Hausdorff\u2013Prokhorov (GHP) topology. We prove that if the weight of each edge is resampled independently with probability \n$\\varepsilon \\gg n^{-1\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then the pair of rescaled minimum spanning trees \u2013 before and after the noise \u2013 converges in distribution to independent random spaces. Conversely, if \n$\\varepsilon \\ll n^{-1\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the GHP distance between the rescaled trees goes to \n$0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in probability. This implies the noise sensitivity and stability for every property of the MST that corresponds to a continuity set of the random limit. The noise threshold of \n$n^{-1\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> coincides with the critical window of the Erd\u0151s-R\u00e9nyi random graphs. In fact, these results follow from an analog theorem we prove regarding the minimum spanning forest of critical random graphs.<\/jats:p>","DOI":"10.1017\/s0963548324000129","type":"journal-article","created":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T05:29:41Z","timestamp":1716442181000},"page":"708-723","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Noise sensitivity of the minimum spanning tree of the complete graph"],"prefix":"10.1017","volume":"33","author":[{"given":"Omer","family":"Israeli","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1516-1918","authenticated-orcid":false,"given":"Yuval","family":"Peled","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,5,23]]},"reference":[{"volume-title":"Probability Theory: An Analytic View, 2nd ed","year":"2011","author":"Stroock","key":"S0963548324000129_ref25"},{"key":"S0963548324000129_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20122"},{"key":"S0963548324000129_ref1","unstructured":"[1] Addario-Berry, L. (2013). The local weak limit of the minimum spanning tree of the complete graph, arXiv: Probability."},{"key":"S0963548324000129_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v15-772"},{"key":"S0963548324000129_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-022-2354-y"},{"key":"S0963548324000129_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316962"},{"key":"S0963548324000129_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90058-7"},{"key":"S0963548324000129_ref21","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"S0963548324000129_ref15","doi-asserted-by":"publisher","DOI":"10.1063\/1.2982848"},{"key":"S0963548324000129_ref17","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"S0963548324000129_ref9","unstructured":"[9] Broutin, N. and Marckert, J.-F. (2023). Convex minorant trees associated with brownian paths and the continuum limit of the minimum spanning tree, arXiv preprint arXiv: 2307.12260."},{"key":"S0963548324000129_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1024404421"},{"key":"S0963548324000129_ref2","unstructured":"[2] Addario-Berry, L. , Broutin, N. and Goldschmidt, C. (2009) The continuum limit of critical random graphs."},{"key":"S0963548324000129_ref6","unstructured":"[6] Angel, O. and S\u00e9nizergues, D. (2023). The scaling limit of the root component in the wired minimal spanning forest of the poisson weighted infinite tree, arXiv preprint arXiv: 2312.14640."},{"key":"S0963548324000129_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070406"},{"key":"S0963548324000129_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1132"},{"key":"S0963548324000129_ref12","first-page":"245","article-title":"Random trees and applications","volume":"2","author":"Gall","year":"2005","journal-title":"Probab. Surv."},{"key":"S0963548324000129_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698830"},{"key":"S0963548324000129_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139924160"},{"key":"S0963548324000129_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOP959"},{"key":"S0963548324000129_ref11","unstructured":"[11] Frilet, N. (2021). Metric coalescence of homogeneous and inhomogeneous random graphs. Theses, Universit\u00e9 Grenoble Alpes [2020-\u2026]."},{"key":"S0963548324000129_ref20","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1994-1138950-5"},{"key":"S0963548324000129_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00224-7"},{"key":"S0963548324000129_ref23","doi-asserted-by":"publisher","DOI":"10.1214\/17-AAP1357"},{"key":"S0963548324000129_ref24","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1472"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T13:25:02Z","timestamp":1731331502000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000129\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,23]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["S0963548324000129"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000129","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,5,23]]},"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"}]}}