Noise sensitivity of the minimum spanning tree of the complete graph

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 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 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ős-Rényi random graphs. In fact, these results follow from an analog theorem we prove regarding the minimum spanning forest of critical random graphs.