Successive minimum spanning trees. Issue 1 (22nd September 2021)

• Record Type: Journal Article
• Authors: Janson, Svante; Sorkin, Gregory B.
• Is Part Of: Random structures & algorithms. Volume 61:Issue 1(2022)
• Page Start: 126
• Page End: 172
• Publication Date: 2021-09-22
• Subjects: discrete probability -- functional fixed point -- inhomogeneous random graph -- Kruskal's algorithm -- minimum spanning tree -- multi‐type branching process -- optimization in random structures -- robust optimization -- second‐cheapest structure; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21047
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In a complete graph K n with independent uniform ( 0, 1 ) (or exponential ( 1 ) ) edge weights, let T 1 be the minimum‐weight spanning tree (MST), and T k the MST after deleting the edges of all previous trees. We show that each tree's weight w ( T k ) converges in probability to a constant γ k, with 2 k − 2 k < γ k < 2 k + 2 k, and we conjecture that γ k = 2 k − 1 + o ( 1 ) . The problem is distinct from Frieze and Johansson's minimum combined weight μ k of k edge‐disjoint spanning trees; indeed, μ 2 < γ 1 + γ 2 . With an edge of weight w "arriving" at time t = n w, Kruskal's algorithm defines forests F k ( t ), initially empty and eventually equal to T k, each edge added to the first possible F k ( t ) . Using tools of inhomogeneous random graphs we obtain structural results including that the fraction of vertices in the largest component of F k ( t ) converges to some ρ k ( t ) . We conjecture that the functions ρ k tend to time translations of a single function.