Online minimum spanning tree constant

Definitions and mathematical statement

For $n\ge2$, let $K_n$ be the complete graph on $[n]$, and assign its edges independent uniform random weights in $[0,1]$. Present all $\binom n2$ edges in a uniformly random order independent of the weights. At each presentation, an online algorithm sees the edge's endpoints and weight and must immediately accept or reject it, with that decision irrevocable.

An admissible strategy bases its decisions only on observations already made and its own independent randomization, and must end with a spanning tree almost surely. A spanning tree is a connected acyclic subgraph containing all $n$ vertices. Its cost is the sum of the weights of its $n-1$ accepted edges. Define \[ c_n=\inf_{\mathcal A}\mathbb E\left[ \sum_{e\text{ accepted by }\mathcal A}w_e\right], \] where the infimum ranges over all admissible strategies; no computational running-time restriction is imposed.

Prove that $c_n$ converges to a finite constant as $n\to\infty$, and determine that constant. An exact characterization of the limit must identify the optimum over strategies, rather than only the cost of a proposed rule.

The random presentation order is part of the primary source's combinatorial model and is specified here explicitly. It is neither increasing order of edge weights nor an adversarial order. The quantity is an optimal expected cost; a strategy may react to previous observations, but cannot inspect future weights or later reverse rejected decisions.

Short English statement

What is the limiting optimal expected cost of constructing a spanning tree when randomly ordered weighted edges must be accepted or rejected online?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 9700039 (AMR-096-0039), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Aldous - Open problems, online_zeta3.html. Original source indexed by AMR-096-0039. https://www.stat.berkeley.edu/~aldous/Research/OP/index.html.
• S3 D. Aldous, O. Angel and N. Berestycki, Online Random Weight Minimal Spanning Trees and a Stochastic Coalescent,2008 draft, combinatorial model. https://www.stat.berkeley.edu/~aldous/Research/OP/Beres2008.pdf.