pith. sign in

arxiv: 1208.5170 · v2 · pith:A6KDOM3Enew · submitted 2012-08-25 · 🧮 math.CO

On the length of a random minimum spanning tree

classification 🧮 math.CO
keywords edgefraclengthminimumspanningtreecitecomplete
0
0 comments X
read the original abstract

We study the expected value of the length $L_n$ of the minimum spanning tree of the complete graph $K_n$ when each edge $e$ is given an independent uniform $[0,1]$ edge weight. We sharpen the result of Frieze \cite{F1} that $\lim_{n\to\infty}\E(L_n)=\z(3)$ and show that $\E(L_n)=\z(3)+\frac{c_1}{n}+\frac{c_2+o(1)}{n^{4/3}}$ where $c_1,c_2$ are explicitly defined constants.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.