# Expected weight of euclidean minimum spanning tree on a unit square

Suppose I randomly generate $n$ points from the unit square $[0,1]^2$, form a complete graph in which the weight of each edge is just the Euclidean distance between its endpoints, and compute the minimum spanning tree. I noticed empirically that the expected weight scales like $\sqrt{n}$. Using only back of the envelope arguments, how could I derive the $\sqrt{n}$ asymptotic behavior?

When I repeated the experiment in the unit cube $[0,1]^3$, the expected weight scaled like $n^{2/3}$, and when I repeated it on the unit hypercube $[0,1]^4$, the expected weight scaled like $n^{3/4}$. How could I derive this asymptotic behavior?

• I have no idea what you meant by "each of the 8 random generators are independent of each other", so I just deleted it. – Yuval Filmus Feb 26 '17 at 2:35
• @Yuval Filmus, Thank you for your very professional edit. – Frank Feb 26 '17 at 5:56

The pigeonhole principle shows that out of any $n$ points in $[0,1]^d$, there are two at distance at most $O(n^{1/d})$, say at most $c_d n^{1/d}$; the idea is to divide $[0,1]^d$ into small enough boxes, and find a box containing two points. Construct a spanning tree by repeatedly adding an edge corresponding to the two closest points and throwing out one of them. This spanning tree has cost at most $$c_d (n^{1/d} + (n-1)^{1/d} + \cdots + 2^{1/d}) \leq c_d \int_2^{n+1} x^{1/d} \, dx = O(n^{(d-1)/d}).$$
For the lower bound, a similar argument dividing $[0,1]^d$ into small boxes shows that for any $\epsilon > 0$, with probability $1-\epsilon$ there are only $\epsilon n$ many edges whose weight is $O_\epsilon(n^{1/d})$, and so with constant probability any spanning tree has cost $\Omega_\epsilon(n^{(d-1)/d})$. With more work, it follows that the expected weight of a minimum spanning tree is $\Omega(n^{(d-1)/d})$.
• The same arguments should work in all $L^p$ metrics. – Yuval Filmus Feb 26 '17 at 9:12