Loading…
Noise Sensitivity of the Minimum Spanning Tree of the Complete Graph
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...
Saved in:
Published in: | arXiv.org 2024-03 |
---|---|
Main Authors: | , |
Format: | Article |
Language: | English |
Subjects: | |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | 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ő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. |
---|---|
ISSN: | 2331-8422 |
DOI: | 10.48550/arxiv.2306.07357 |