The online MST of the randomly-weighted complete graph

To edges \(e\) of the complete n-vertex graph assign i.i.d. weights \(w_e\) distributed uniformly on \( [0,1] \). A celebrated result of Frieze asserts that the weight \(X_n\) of the minimal spanning tree (MST) satisfies \( \mathbb{E} X_n \to \zeta(3) = 1.20 \ldots \). Consider the corresponding online problem in which edges are presented one by one, and we must decide then whether to accept the edge for our spanning tree.

Problem. Prove that under the optimal strategy (for minimizing mean cost) the mean cost \( \mathbb{E} Y_n \) converges to some limit constant, and determine that constant.

This incomplete 2008 draft by Aldous-Angel-Berestycki provides numerical bounds and a conjectured expression for the limit in terms of a PDE on the infinite simplex, but we do not have a rigorous proof that the limit exists.

History. Mentioned to many people since 2008 but not posted here until 2018.

Back to Open Problem list