Intuition for minimum spanning tree result

Question

Let K$_ n$ denote the complete graph on n vertices. To each edge in K$_n$ independently assign a weight drawn from the uniform distribution on [0,1]$\,$. Finally, define MST(n) to be the expected value of the minimum spanning tree of K$_ n$ under these conditions. For example, one immediately sees that MST(2) = 1/2 and slightly less immediately that MST(3) = 3/4 . A remarkable theorem due to Frieze states that MST(n) approaches the limiting value $\zeta(3)$ = 1.202... $\,$ as n approaches infinity.

Questions:$\,$ 1) Are there any heuristic arguments that make it plausible a priori that MST(n) will remain bounded?$\;$ 2) If one only wishes to show that MST(n) = O(1)$\,$, is there a simple proof for just that much?

Thanks

Answer 1

Bounded: A tree on $n$ vertices has $n-1$ edges. (Each node except the root has exactly one edge connecting it to a subtree containing the root.) Consequently, $\mathrm{MST}(n) < (n-1) \max([0,1]) = n-1$.

Still thinking if there's a short $O(1)$ argument.

Answer 2

For boundedness, this isn't a proof (lots of handwaving near the end) but I think it gives a pretty convincing heuristic. Here when I use expressions like "$n/2$ vertices" it should be understood that I really mean $n/2 + O(1)$.

Let's look for a MST of the following type: a path of length $n/2$ with the remaining $n/2$ vertices adjacent to some vertex on the path. Basically it looks more like a cactus than a tree :).

The expected minimum of $n$ independent uniform elements from $[0,1]$ is about $1/n$ (I believe it's precisely $1/(n+1)$, so if we start from vertex $1$ and add an edge from the pool of vertices not yet in the path, then the expected total weight of the path will be about

$$\frac1n + \frac1{n-1} + \cdots + \frac1{n/2} = O(1),$$ since there are only $n/2$ terms of size at most $2/n$.

Now, for the remaining $n/2$ vertices we want to find the cheapest way to connect to the initial path. The catch here is that a priori any vertex not already on the path was not the cheapest neighbour of anything on the path. So it's more fair to model a given vertex $v$ as follows: take the $n/2$ edges from $v$ to the path, and filter out the ones that are smaller than about $2/n$. There should still be about $n/2 - O(1)$ edges remaining, randomly distributed in $[2/n,1]$. The expected minimum of these is roughly $4/n + O(1/n^2)$. Summing this up over all $n/2$ remaining vertices also gives $O(1)$.

So then both the backbone of the cactus and all of the spines have expected total weight $O(1)$.