# 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

## 1 Answer

The following is based on J. Michael Steele's paper proving the rigorous bound.

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})$.

• Thank you for your incredible answer. Could I apply it to a complete graph on n vertices where the weight of each edge is a real number chose uniformly randomly in the closed interval [0,1] to obtain the result Ω(n(d−1)/d) where d = 2 and we use the concept of Manhattan distance? Also, why are not eight independent pseudorandom generators needed for the unit cube case. In addition, how do I empirically prove on an Ubuntu Linux 16.04 Dell computer that its cache of size X megabytes has a positive effect on speeding up the generation of random 131072 vertex graphs repeatedly? . – Frank Feb 26 '17 at 5:43
• I just approved your answer and awarded you 1 reputation point which is well deserved. In retrospect, I should have taken Princeton's acceptance offer when I was 17. – Frank Feb 26 '17 at 5:46
• The same arguments should work in all $L^p$ metrics. – Yuval Filmus Feb 26 '17 at 9:12
• How do I derive and find the constant factor(s) for the expected weight of a minimum spanning tree? Thank you – Frank Feb 26 '17 at 9:42
• That's apparently complicated – an explicit constant is not known. You can estimate it experimentally, though perhaps there are better ways. I suggest taking a look at Steele's paper. – Yuval Filmus Feb 26 '17 at 13:27