Noise Sensitivity of the Minimum Spanning Tree of the Complete Graph

arXiv2306.07357MaRDI QIDQ6510539FDOQ6510539

Authors: Omer Israeli, Yuval Peled 

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 $varepsilongg{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 $varepsilonll{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 seen in the scaling limit, e.g., whether the diameter exceeds its median. The noise threshold of $n^{-1/3}$ coincides with the critical window of the ErdH{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.

This page was built for publication: Noise Sensitivity of the Minimum Spanning Tree of the Complete Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510539)