Random minimal spanning tree and percolation on the N-cube
By Mathew D. Penrose.
The N-cube is a graph with 2N vertices
and N2N-1 edges.
Suppose independent uniform random edge-weights are assigned,
and let T be the spanning tree of minimal (total) weight.
Then the weight of T is asymptotic to
(1/N)2N
(sumi>0i-3)
as N tends to infinity.
Asymptotics are also given for the local structure of T,
and for the distribution of its k-th largest edge-weight,
k fixed.
Random Structures and Algorithms 12, 63-82 (1998).