Successive minimum spanning trees. Issue 1 (22nd September 2021) - Janson, Svante; Sorkin, Gregory B.
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.