Noise Sensitivity of the Minimum Spanning Tree of the Complete Graph

Omer Israeli, Yuval Peled

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 gra…