{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q870089","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q870089","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q870089","kernelVersion":"v1","immutable":true,"modified":"2026-01-12T19:26:42Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q870089","name":"The lower tail of the random minimum spanning tree","headline":"The lower tail of the random minimum spanning tree","description":"scientific article; zbMATH DE number 5132861","url":"https://portal.mardi4nfdi.de/entity/Q870089","datePublished":"2007-03-12","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q452815"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q161296"}],"comment":"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)\\)."},"provenance":{"prov:generatedAtTime":"2026-01-12T19:26:42Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}