English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 verticesare given a uniform measure, the MST converges in distribution in theGromov-Hausdorff-Prokhorov (GHP) topology. We prove that if the weight of eachedge 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 everyproperty of the MST seen in the scaling limit, e.g., whether the diameterexceeds its median. The noise threshold of $n^{-1/3}$ coincides with thecritical window of the Erd\H{o}s-R\'enyi random graphs. In fact, these resultsfollow from an analog theorem we prove regarding the minimum spanning forest ofcritical random graphs.

Noise Sensitivity of the Minimum Spanning Tree of the Complete Graph