## 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**