Random minimal spanning tree and percolation on the N-cube

The N-cube is a graph with 2^N vertices and N2^N−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 N⁻¹2^N ∑^∞_i=1 i⁻³ as N→∞. Asymptotics are also given for the local structure of T and for the distribution of its kth largest edge weight, k fixed. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 63–82, 1998