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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-03
Main Authors: Israeli, Omer, Peled, Yuval
Format: Article
Language:English
Subjects:
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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