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