Current browse context:
math.PR
Change to browse by:
References & Citations
Mathematics > Probability
Title: Noise Sensitivity of the Minimum Spanning Tree of the Complete Graph
(Submitted on 12 Jun 2023 (v1), last revised 27 Mar 2024 (this version, v3))
Abstract: We study the noise sensitivity of the minimum spanning tree (MST) of the $n$-vertex complete graph when edges are assigned independent random weights. It is known that when the graph distance is rescaled by $n^{1/3}$ and vertices are given a uniform measure, the MST converges in distribution in the Gromov-Hausdorff-Prokhorov (GHP) topology. We prove that if the weight of each edge is resampled independently with probability $\varepsilon\gg n^{-1/3}$, then the pair of rescaled minimum spanning trees -- before and after the noise -- converges in distribution to independent random spaces. Conversely, if $\varepsilon\ll n^{-1/3}$, the GHP distance between the rescaled trees goes to $0$ 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^{-1/3}$ coincides with the critical window of the Erd\H{o}s-R\'enyi random graphs. In fact, these results follow from an analog theorem we prove regarding the minimum spanning forest of critical random graphs.
Submission history
From: Yuval Peled [view email][v1] Mon, 12 Jun 2023 18:28:03 GMT (18kb)
[v2] Wed, 5 Jul 2023 01:03:30 GMT (18kb)
[v3] Wed, 27 Mar 2024 09:25:31 GMT (28kb)
Link back to: arXiv, form interface, contact.