The lower tail of the random minimum spanning tree
Summary: Consider a complete graph \(K_n\) where the edges have costs given by independent random variables, each distributed uniformly between 0 and 1. The cost of the minimum spanning tree in this graph is a random variable which has been the subject of much study. This note considers the large deviation probability of this random variable. Previous work has shown that the log-probability of deviation by \(\varepsilon\) is \(-\Omega(n)\), and that for the log-probability of \(Z\) exceeding \(\zeta(3)\) this bound is correct; \(\log \text{Pr}[Z \geq \zeta(3) + \varepsilon] = -\Theta(n)\). The purpose of this note is to provide a simple proof that the scaling of the lower tail is also linear, \(\log \text{Pr}[Z \leq \zeta(3) - \varepsilon] = -\Theta(n)\).
This page was built for publication: The lower tail of the random minimum spanning tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870089)
