2
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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? . $\endgroup$ – Frank Feb 26 '17 at 5:43
  • $\begingroup$ 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. $\endgroup$ – Frank Feb 26 '17 at 5:46
  • $\begingroup$ The same arguments should work in all $L^p$ metrics. $\endgroup$ – Yuval Filmus Feb 26 '17 at 9:12
  • $\begingroup$ How do I derive and find the constant factor(s) for the expected weight of a minimum spanning tree? Thank you $\endgroup$ – Frank Feb 26 '17 at 9:42
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 26 '17 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.