THE MINIMAL SPANNING TREE IN A

COMPLETE GRAPH AND A FUNCTIONAL LIMIT

THEOREM FOR TREES IN A RANDOM GRAPH.

Svante Janson

Abstract. The minimal weight of a spanning tree in a complete graph K_{n} with independent, uniformly distributed random weights on the edges, is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.

1. Introduction and results

Assign random weights T_{ij}, 1 ≤ i < j ≤ n, to the edges of the complete graph K_{n} with vertex set {1, …, n}, and let W_{n} be the minimum weight of a spanning tree of K_{n}. We assume that the weights are independent and identically distributed, with a uniform distribution on [0, 1]. It was proved by Frieze [5] that

W_{n} → ζ(3) = ∑_{k=1}^{∞} k^{−3} = 1.202 …

in probability as n → ∞, see also Bollobs [3]. The main purpose of the present paper is to show that W_{n} has an asymptotic normal distribution.

Theorem 1. Let W_{n} be the weight of the minimal spanning tree. Then

n^{1/2}(W_{n} − ζ(3)) ⟶^{d} N(0, σ^{2})

with

σ^{2} = \frac{π^{4}}{45} − 2 ∑_{i=0}^{∞} ∑_{j=1}^{∞} ∑_{k=1}^{∞} \frac{(i + k − 1)! k^{k}(i + j)^{i−2}j}{i! k! (i + j + k)^{i+k+2}} .

Remark 1.1. We do not know whether there exists any simpler expression for σ^{2}. A numerical summation yields σ^{2} ≈ 1.6857.

As is well-known (and will be described in detail in Section 3), W_{n} is closely linked to properties of the number of components of a random graph, in particular the number of tree components. Our proof of Theorem 1 uses this, and is based on a functional limit theorem for component counts. We define a random graph process G_{n}(t) (where t ≥ 0 is interpreted as time) by taking the edge set of G_{n}(t) to be {ij : T_{ij} ≤ t}, with T_{ij} as above. Hence T_{ij} now is interpreted as the (random) time the edge ij appears. Note that

Typeset by AMS-TEX

Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine

Prepared on October 9, 1997

G_{n}(t) = K_{n} for t ≥ 1; hence all the evolution occurs on [0, 1], although we for convenience allow also t > 1. Define, for k ≥ 1 and 0 ≤ t < ∞,

μ_{k}(t) = \frac{k^{k−2}}{k!} t^{k−1}e^{−kt}

and, for k, l ≥ 1 and t, u ≥ 0,

σ_{kl}(t, u) = \{ \begin{matrix}(t − 1)klμ_{k}(t)μ_{l}(u), & k > l, t ≤ u, \\ (t − 1)klμ_{k}(t)μ_{l}(u) + e^{−k(u−t)}μ_{k}(t), & k = l, t ≤ u, \\ (t − 1)klμ_{k}(t)μ_{l}(u) + \frac{k^{k−1}}{k!(l−k)!}t^{k−1}(u − t)(lu − kt)^{l−k−1}e^{−lu}, & k < l, t ≤ u, \end{matrix}

and

σ_{kl}(t, u) = σ_{lk}(u, t), t > u.

Theorem 2. Let X_{kn}(t) be the number of isolated trees of order k in G_{n}(t). Then, for k ≥ 1,

\frac{X_{kn}(t/n) − E X_{kn}(t/n)}{\sqrt{n}} ⟶^{d} V_{k}(t)  (1.1)

and

\frac{X_{kn}(t/n) − nμ_{k}(t)}{\sqrt{n}} ⟶^{d} V_{k}(t)  (1.2)

as n → ∞, in D([0, ∞]), jointly for any finite set of k, where (V_{k}(t))_{k=1}^{∞} are continuous jointly Gaussian stochastic processes with V_{k}(0) = V_{k}(∞) = 0, E V_{k}(t) = 0, 0 ≤ t ≤ ∞, and covariance functions Cov(V_{k}(t), V_{l}(u)) = σ_{kl}(t, u).

The convergence here is in the Skorohod topology on D([0, ∞]), which can be obtained from the perhaps better know space D([0, 1]), see Billingsley [2], by a (monotone) change of parameter. For convergence to a continuous limit (the only case that really interests us), convergence in D([0, ∞]) is equivalent to uniform convergence. We refer to [2] for properties of the Skorohod topology and of convergence in distribution in it.

Theorem 2 implies, in particular, that (1.1) holds for every fixed t; this has been proven earlier, by different methods, by Barbour [1] (fixed k) and Pittel [10] (joint convergence for all k). Moreover, the cases k = 1 (isolated vertices) and k = 2 (isolated edges) were treated in [8, Sections 11 and 12].

Remark 1.2. Pittel [10, Theorem 1] also gives a similar (but somewhat different) limit theorem for the random graph G_{nm}, with m = [cn/2] for a fixed c > 0. This too follows by our method, more precisely by [8, Theorem 9(iv)] using [8, Proposition 4.2] and estimates from Section 2 below. We will not consider G_{nm} further in this paper.

Remark 1.3. Pittel [10] used his results on tree counts to prove asymptotic normality of the order of the giant component in a random graph G(n, c/n), c > 1. It should be possible to use our Theorem 2 to obtain a functional version of this, i.e. process convergence of the order of the giant component in G(n, t/n), t > 1, to a Gaussian stochastic process on (1, ∞), but some details remain to be verified and we leave this as a conjecture. (The same applies to the number of edges in the giant component of G(n, t/n) or the number of components of G(n, t/n).)

Remark 1.4. Results similar to Theorem 2 may be obtained by the same method for counts of specific types of trees, for example the numbers of isolated paths of different lengths in G_{n}(t).

Remark 1.5. Donald Knuth (personal communication) has recently suggested studying the minimum weight spanning pseudoforest for random weights as above, where a spanning pseudoforest is a subgraph of K_{n} with n edges and only unicyclic components. (See Gabow and Tarjan [6] for the problem of finding the minimum weight spanning pseudoforest for given (non-random) weights.) Let W′_{n} denote the minimum weight of a spanning pseudoforest. We will show in Section 3 that Theorem 1 holds also with W_{n} replaced by W′_{n}.

Acknowledgement

This research was done during a visit to IMA, Minneapolis. I thank Boris Pittel and other participants for stimulating discussions.

2. Proof of Theorem 2.

We begin by studying the first two moments of X_{kn}(t), but let us first introduce some notations. We let C_{1}, C_{2}, … denote universal constants whose values are unimportant (the industrious reader may substitute suitable numbers), while C(k) denotes a ”constant” that depends on k but not on any other variable. Similarly, O and o denote estimates that are uniform in all relevant variables, while f = O_{k}(g) means the same as |f| ≤ C(k)g. We let (n)_{k} = ∏_{1}^{k}(n − i + 1), the decreasing factorial, and observe for future use the following estimate.

Lemma 2.1. If 1 ≤ k ≤ n and n ≥ 4, then

(n)_{k} ≤ C_{1}(n − k/2 − 3/2)^{k}.

Proof. By the assumptions n − k/2 − 3/2 ≥ (n − 3)/2 ≥ n/8 > 0. By concavity of the logarithm (or because (n + 1 − i)(n − k + i) ≤ (n − k/2 + 1/2)^{2} by the conjugate rule),

ln(n)_{k} = ∑_{i=1}^{k} ln(n − i + 1) ≤ k ln(n − k/2 + 1/2)

and thus

\frac{(n)_{k}}{(n − k/2 − 3/2)^{k}} ≤ (\frac{n − k/2 + 1/2}{n − k/2 − 3/2})^{k} = (1 + \frac{2}{n − k/2 − 3/2})^{k}

≤ (1 + \frac{16}{n})^{k} ≤ e^{16k/n} ≤ e^{16}.

□

We introduce some more notation. Let T_{kn} be the set of trees of order k in the complete graph K_{n}; by Cayley’s theorem [4],

|T_{kn}| = \binom{n}{k}k^{k−2} = \frac{k^{k−2}}{k!} n^{k}(1 + O_{k}(n^{−1})).

For each α ∈ T_{kn}, let I_{α}(t) be the indicator that is 1 if α is an isolated tree in G_{n}(t), and 0 otherwise. Hence

X_{kn}(t) = ∑_{α∈T_{kn}} I_{α}(t).

The expectation E I_{α}(t) = P(I_{α}(t) = 1) is the same for each α ∈ T_{kn}. We denote it by p_{kn}(t), and it is easily seen that, for 1 ≤ k ≤ n and 0 ≤ t ≤ 1,

E I_{α}(t) = p_{kn}(t) = t^{k−1}(1 − t)^{(n−k)k+\binom{k}{2}−k+1}, α ∈ T_{kn}.

Hence, for 0 ≤ t ≤ 1,

E X_{kn}(t) = |T_{kn}|p_{kn}(t) = \binom{n}{k}k^{k−2}t^{k−1}(1 − t)^{nk−k^{2}/2−3k/2+1}.

We state this formula together with two useful estimates derived from it as a lemma.

Lemma 2.2.

(i) If 0 ≤ t ≤ 1, then

E X_{kn}(t) = \binom{n}{k}k^{k−2}t^{k−1}(1 − t)^{nk−k^{2}/2−3k/2+1}.

(ii) For k ≥ 1, n ≥ 3 and 0 ≤ t < ∞,

E X_{kn}(t) = nμ_{k}(nt) + O_{k}(e^{−nt/2}).

(iii) If k, n ≥ 1 and 0 ≤ t ≤ 1, then

E X_{kn}(t) ≤ C_{2}nk^{−5/2}e^{−nt/2}.

For 0 ≤ t < 1 and n ≥ 4, also

(1 − t)^{−2} E X_{kn}(t) ≤ C_{3}nk^{−5/2}e^{−nt/2}.

Proof. (i) is already proved.

For (ii), consider first the case nt^{2} ≤ 1. Then 0 ≤ t ≤ 1, and by (i), for n ≥ k,

E X_{kn}(t) = \frac{k^{k−2}}{k!} (n)_{k}t^{k−1} exp (−nkt + O(k^{2}t) + O(nkt^{2}))
= nμ_{k}(nt) exp (O(k^{2}t) + O(nkt^{2}) + O(k^{2}/n))
= nμ_{k}(nt) (1 + O_{k}(t + nt^{2} + 1/n))
= nμ_{k}(nt) + O_{k}(((nt)^{k−1} + (nt)^{k+1}) e^{−knt})
= nμ_{k}(nt) + O_{k}(e^{−knt/2}).

If nt^{2} > 1 we obtain similarly, by (i) and the trivial fact that X_{kn}(t) = 0 for t ≥ 1 and n ≥ 3,

\begin{aligned}E X_{kn}(t) & ≤ n^{k}t^{k−1}e^{−tnk+k^{2}} \\ & ≤ n^{k+1}t^{k+1}e^{−knt+k^{2}} \end{aligned}

= O_{k}(e^{−knt/2})

and

nμ_{k}(nt) ≤ n^{2}t^{2}μ_{k}(nt) = O_{k}(e^{−knt/2}).

Hence (ii) follows in both cases.

For (iii), we may assume that 1 ≤ k ≤ n and n ≥ 3. Then, setting x = (n − k/2 − 3/2)t ≥ nt/2−3t/2 and using Lemma 2.1 and Stirling’s formula together with the estimate xe^{−x} ≤ e^{−1},

E X_{kn}(t) ≤ \frac{k^{k−2}}{k!} (n)_{k}t^{k−1}(1 − t)^{k(n−k/2−3/2)}

≤ C_{1} \frac{k^{k−2}}{k!} (n − k/2 − 3/2)^{k}t^{k−1}e^{−kt(n−k/2−3/2)}

≤ C_{1} \frac{k^{k−2}}{k!} nx^{k−1}e^{−kx}

≤ C_{1}n\frac{k^{k−2}}{k!} (xe^{−x})^{k−1}e^{−x}

≤ C_{1}n\frac{k^{k−2}}{k^{k+1/2}e^{−k}} e^{−k+1}e^{−nt/2+3/2}

≤ C_{1}e^{5/2}nk^{−5/2}e^{−nt/2}.

The same argument proves the final estimate. □

We turn to second moment calculations.

Consider Cov (I_{α}(t), I_{β}(u)), where α ∈ T_{k}, β ∈ T_{l} and 0 ≤ t ≤ u ≤ 1 (for simplicity we here and sometimes in the sequel omit the subscript n). Recall that E (I_{α}(t)I_{β}(u)) is the probability that α is a component of G_{n}(t) and that β is a component of G_{n}(u) at a later time u. There are three cases:

(i) α and β are (vertex-)disjoint. If we expand E I_{α}(t)I_{β}(u) and E I_{α}(t) E I_{β}(u) as products over the edges in K_{n}, the only difference is that the former contains one factor 1 − u for each of the kl edges joining α and β, while the latter contains two factors 1 − t and 1 − u. Hence

E I_{α}(t)I_{β}(u) = p_{k}(t)p_{l}(u)(1 − t)^{−kl}.  (2.1)

(ii) α ∩ β ≠ ∅, but α ⊈ β. If α is a component of G_{n}(t) and u ≥ t, then any component of G_{n}(u) that intersects α has to contain α. Hence

E I_{α}(t)I_{β}(u) = 0.  (2.2)

(iii) α ⊆ β. In order for α to be a component in G_{n}(t) that grows to a component β in G_{n}(u), we have to have T_{e} ≤ t for each edge e in α, t < T_{e} ≤ u for each e in β with exactly one endpoint in α, T_{e} ≤ u for each e in β \ α, and T_{e} > u for every other e with one or two endpoints in β. Hence, if there are j edges joining α to β \ α,

E I_{α}(t)I_{β}(u) = t^{k−1}(u − t)^{j}u^{l−k−j}(1 − u)^{(n−l)l+\binom{l}{2}−l+1}.  (2.3)

Let B_{kl} be the number of pairs (α, β) with α ∈ T_{k}, β ∈ T_{l} and α ∩ β ≠ ∅, and let b_{kl} = B_{kl}/|T_{k}||T_{l}|. Note that, for fixed k and l,

b_{kl} = 1 − \frac{(n − k)_{l}}{(n)_{l}} = \frac{kl}{n} + O_{k,l}(n^{−2}).  (2.4)

Now, Cov(X_{k}(t), X_{l}(u)) = ∑\begin{matrix}α∈T_{k} \\ β∈T_{l} \end{matrix} E (I_{α}(t)I_{β}(u)) − E X_{k}(t) E X_{l}(u). There are |T_{k}||T_{l}| −

B_{kl} = (1−b_{kl})|T_{k}||T_{l}| terms of type (i) in the sum, and if t ≤ u we obtain from (2.1)–(2.3),

\begin{aligned}Cov(X_{k}(t), X_{l}(u)) & = (1 − b_{kl})|T_{k}||T_{l}|p_{k}(t)p_{l}(u)(1 − t)^{−kl} + ∑_{α⊆β} E I_{α}(t)I_{β}(u) \\ & − E X_{k}(t) E X_{l}(u) \end{aligned}

= E X_{k}(t) E X_{l}(u)(1 − t)^{−kl}(1 − b_{kl} − (1 − t)^{kl}) + ∑_{α⊆β} E I_{α}(t)I_{β}(u). (2.5)

Again there are three cases:

(i) If k > l and t ≤ u ≤ 1, then α ⊆ β cannot occur, and

Cov(X_{k}(t), X_{l}(u)) = E X_{k}(t) E X_{l}(u)(1 − t)^{−kl}(1 − (1 − t)^{kl} − b_{kl}).  (2.6)

(ii) If k = l and t ≤ u ≤ 1, the only terms with α ⊆ β are those with α = β. Since E I_{α}(t)I_{α}(u) = t^{k−1}(1 − u)^{(n−k)k+\binom{k}{2}−k+1} = (t/u)^{k−1}p_{k}(u) when α ∈ T_{k},

∑_{α} E(I_{α}(t)I_{α}(u)) = (t/u)^{k−1} E X_{k}(u)

and (2.5) yields

Cov(X_{k}(t), X_{l}(u))

= E X_{k}(t) E X_{l}(u)(1 − t)^{−kl}(1 − (1 − t)^{kl} − b_{kl}) + (t/u)^{k−1} E X_{k}(u), (2.7)

(iii) If k < l and t ≤ u ≤ 1, we partition the sum over α ⊂ β further.

Let N_{klj} be the number of pairs (α, β) with α ∈ T_{k}, β ∈ T_{l} and α ⊂ β, such that there are j vertices in β \ α adjacent to α, 1 < j ≤ l − k. This number may be calculated as follows.

There are |T_{k}| choices of α. For each of these, the remaining l − k vertices in β may be chosen in \binom{n−k}{l−k} ways. We may then select the j vertices adjacent to α in \binom{l−k}{j} ways and connect them to α in k^{j} ways. Finally, we complete β by adding a rooted forest on the l − k new vertices, with the j selected vertices as roots; there are j(l − k)^{l−k−j−1} such forests, see [4] and [11]. Hence we find

N_{klj} = |T_{k}|\binom{n − k}{l − k}\binom{l − k}{j}k^{j}j(l − k)^{l−k−j−1}

= |T_{k}|\binom{n − k}{l − k}\binom{l − k − 1}{j − 1}k^{j}(l − k)^{l−k−j}

and, by (2.3), with L = l^{2}/2 + 3l/2 − 1,

∑_{α⊂β} E I_{α}(t)I_{β}(u) = ∑_{j=1}^{l−k} N_{klj}t^{k−1}(u − t)^{j}u^{l−k−j}(1 − u)^{nl−L}

= |T_{k}|\binom{n − k}{l − k}t^{k−1}(1 − u)^{nl−L} ∑_{j=1}^{l−k} \binom{l − k − 1}{j − 1}k^{j}(u − t)^{j}(l − k)^{l−k−j}u^{l−k−j}

= |T_{k}|\binom{n − k}{l − k}t^{k−1}(1 − u)^{nl−L}k(u − t)(k(u − t) + (l − k)u)^{l−k−1}

= k|T_{k}|\binom{n − k}{l − k}t^{k−1}(u − t)(lu − kt)^{l−k−1}(1 − u)^{nl−L},

where we used the binomial theorem (changing the summation index to j − 1). Hence (2.5) yields

Cov(X_{k}(t), X_{l}(u)) = E X_{k}(t) E X_{l}(u)(1 − t)^{−kl}(1 − (1 − t)^{kl} − b_{kl})

+ k|T_{k}|\binom{n − k}{l − k}t^{k−1}(u − t)(lu − kt)^{l−k−1}(1 − u)^{nl−L}. (2.8)

The formulae (2.4) and (2.6)–(2.8) yield immediately the following asymptotical result.

Lemma 2.3. For any fixed k, l ≥ 1 and t, u ≥ 0,

\frac{1}{n} Cov(X_{kn}(\frac{t}{n}), X_{ln}(\frac{u}{n})) ⟶ σ_{kl}(t, u) as n → ∞.

□

Lemma 2.4. For fixed k ≥ 1 and t > 0,

Var(X_{kn}(\frac{t}{n})) ≍ n as n → ∞.

Proof. By definition,

σ_{kk}(t, t) = (t − 1)k^{2}μ_{k}(t)^{2} + μ_{k}(t) = μ_{k}(t)(1 + (t − 1)k^{2}μ_{k}(t)).

If t ≥ 1, this is obviously positive. If 0 < t < 1 and k ≥ 2, then

(1 − t)k^{2}μ_{k}(t) = (1 − t)t\frac{k^{k}}{k!} (te^{−t})^{k−2}e^{−2t} ≤ \frac{1}{4} \frac{e^{k}}{\sqrt{2πk}} e^{−(k−2)} ≤ \frac{e^{2}}{4\sqrt{2π}} < 1.

Similarly, if 0 < t < 1 and k = 1, then (1 − t)k^{2}μ_{k}(t) = (1 − t)e^{−t} < 1. Hence σ_{kk}(t, t) > 0 whenever t > 0, and the result follows by Lemma 2.3.

□

We will also use the following uniform estimates. Lemma 2.5. For all k, n ≥ 1 and t ≥ 0,

Var X_{kn}(t) ≤ C_{4}nk^{−5/2}e^{−nt/2}.

If t < 1 and n ≥ 4, then also

(1 − t)^{−2} Var X_{kn}(t) ≤ C_{5}nk^{−5/2}e^{−nt/2}.

Proof. We may assume 0 ≤ t ≤ 1 and k ≤ n. Then, by (2.7),

Var(X_{kn}(t)) = (E X_{kn}(t))^{2}(1 − t)^{−k^{2}}(1 − (1 − t)^{k^{2}} − b_{kk}) + E X_{kn}(t)

≤ (E X_{kn}(t))^{2}(1 − t)^{−k^{2}}(1 − b_{kk})(1 − (1 − t)^{k^{2}}) + E X_{kn}(t)

= E X_{kn}(t)(1 − b_{kk})|T_{kn}|(1 − t)^{−k^{2}}p_{kn}(t)(1 − (1 − t)^{k^{2}}) + E X_{kn}(t) = E X_{kn}(t)|T_{k,n−k}|p_{k,n−k}(t)(1 − (1 − t)^{k^{2}}) + E X_{kn}(t) = E X_{kn}(t)(E X_{k,n−k}(t)(1 − (1 − t)^{k^{2}}) + 1)

Since 1 − (1 − t)^{k^{2}} ≤ k^{2}t and, by Lemma 2.2 (iii),

k^{2}t E X_{k,n−k}(t) ≤ C_{2}t(n − k)e^{−(n−k)t/2} ≤ C_{2},

this yields

Var X_{kn}(t) ≤ C_{6} E X_{kn}(t),

and the result follows by Lemma 2.2(iii) again. □

We also have to study the drift ξ_{kn}(t) of X_{kn}(t), i.e. the expected rate of change of X_{kn}(t) in an infinitesimal interval (t, t+dt). (More precisely, ξ_{kn}(t) = lim_{△t→0+} E(X_{kn}(t+ △t)−X_{kn}(t) | F_{t})/△t, where F_{t} is the σ-field generated by all events up to time t.) Isolated trees of order k may be both created and destroyed as new edges are added (except for k = 1), and we thus write

ξ_{kn}(t) = ξ_{kn}^{+}(t) − ξ_{kn}^{−}(t),

separating creations and destructions.

An isolated tree in G_{n}(t) is destroyed when any of nk − k^{2}/2 − 3k/2 + 1 edges is added, and since each edge is added with intensity (1 − t)^{−1}, conditionally on not already being present, this yields

ξ_{kn}^{−}(t) = (nk − k^{2}/2 − 3k/2 + 1)(1 − t)^{−1}X_{kn}(t),  0 ≤ t < 1.  (2.9)

Similarly, an isolated tree of order k is created when two isolated trees, of orders j and k − j, say, are joined by an edge. For each such pair of (disjoint) isolated trees, there are j(k − j) possible edges that will join the trees, and thus (the factor \frac{1}{2} is needed because we have considered unordered pairs of trees),

ξ_{kn}^{+}(t) = \frac{1}{2} ∑_{i=1}^{k−1} ∑_{α∈T_{i}} ∑_{\begin{matrix}β∈T_{k−i} \\ β∩α=∅ \end{matrix}} i(k − i)(1 − t)^{−1}I_{α}(t)I_{β}(t),  0 ≤ t < 1.  (2.10)

Lemma 2.6. For each k ≥ 1 and all n ≥ 1 and t ≥ 0,

Var(ξ_{kn}(t)) ≤ C_{7}(k)n^{3}e^{−nt/2}.

Proof. Clearly ξ_{kn}(t) = 0 for t ≥ 1; hence we may assume t < 1. We then have Var(ξ_{kn}(t)) ≤ 2 Var(ξ_{kn}^{+}(t)) + 2 Var(ξ_{kn}^{−}(t)), and, by (2.9) and Lemma 2.5,

Var(ξ_{kn}^{−}(t)) ≤ n^{2}k^{2}(1 − t)^{−2} Var(X_{kn}(t)) ≤ C_{5}n^{3}e^{−nt/2}.

Hence it remains only to consider Var(ξ_{kn}^{+}(t)). We obtain from (2.10)

Var(ξ_{kn}^{+}(t)) = \frac{1}{4} ∑_{i,j=1}^{k−1} i(k − i)j(k − j) ∑_{α,β,γ,δ}(1 − t)^{−2} Cov(I_{α}(t)I_{β}(t), I_{γ}(t)I_{δ}(t)), (2.11)

where we sum over all α ∈ T_{i}, β ∈ T_{k−i}, γ ∈ T_{j}, δ ∈ T_{k−j} such that α ∩ β = γ ∩ δ = ∅. Let us first consider the terms where α, β, γ, δ are pairwise disjoint. Then, similarly to (2.1),

E I_{α}(t)I_{β}(t) E I_{γ}(t)I_{δ}(t) = (1 − t)^{k^{2}} E I_{α}(t)I_{β}(t)I_{γ}(t)I_{δ}(t),

and thus

Cov(I_{α}(t)I_{β}(t), I_{γ}(t)I_{δ}(t)) = (1 − (1 − t)^{k^{2}}) E I_{α}(t)I_{β}(t)I_{γ}(t)I_{δ}(t)
= (1 − (1 − t)^{k^{2}})p_{i,n}(t)p_{k−i,n−i}(t)p_{j,n−k}(t)p_{k−j,n−k−j}(t).

The number of such quadruples (α, β, γ, δ) with given i and j equals |T_{i,n}||T_{k−i,n−i}||T_{j,n−k}| |T_{k−j,n−k−j}| and their total contribution to the inner sum in (2.11) is thus, using Lemma 2.2(iii),

(1 − t)^{−2}(1 − (1 − t)^{k^{2}}) E X_{i,n}(t) E X_{k−i,n−i}(t) E X_{j,n−k}(t) E X_{k−j,n−k−j}(t)

≤ C_{3}C_{2}^{3}k^{2}tn(n − i)(n − k)(n − k − j)e^{−nt/2−(n−i)t/2} ≤ C_{8}k^{2}n^{3}e^{−nt/2}.

Summing over i and j we obtain an estimate of the required order. There still remains the terms where two (or more) of α, β, γ, δ intersect. In this case, if the intersecting trees do not coincide, I_{α}(t)I_{β}(t)I_{γ}(t)I_{δ}(t) = 0 and the covariance in (2.11) is negative. Hence, for an upper bound we only have to consider the cases β = δ with α, β, γ disjoint, and α = γ, β = δ (up to relabelling). For the first case,

Cov(I_{α}(t)I_{β}(t), I_{γ}(t)I_{β}(t)) ≤ E I_{α}(t)I_{β}(t)I_{γ}(t) = p_{i,n}(t)p_{k−i,n−i}(t)p_{i,n−k}(t)

and the total contribution to the inner sum of (2.11) is, for fixed i, using Lemma 2.2(iii) again, bounded by

(1 − t)^{−2} E X_{i,n}(t) E X_{k−i,n−i}(t) E X_{i,n−k}(t) ≤ C_{3}C_{2}^{2}n^{3}e^{−nt/2}.

For the second case we similarly get, for each i, a contribution ≤ C_{9}n^{2}e^{−nt/2}. The lemma follows. □

We next use the orthogonal decomposition in [8], which can be briefly described as follows. Let, for 0 ≤ t ≤ 1, I′_{e}(t) = I_{e}(t) − t; note that E I′_{e}(t) = 0, which is the central point in the theory. Each I_{α}(t) equals a product

∏_{e∈A(α)} I_{e}(t) ∏_{e∈B(α)}(1 − I_{e}(t)) = ∏_{e∈A(α)}(I′_{e}(t) + t) ∏_{e∈B(α)}(1 − t − I′_{e}(t)),  (2.12)

for certain edge sets A(α) and B(α); A(α) is the set of edges in α, and B(α) is the set of all other edges in K_{n} that have at least one endpoint in α. Expanding the product in (2.12), we see that I_{α}(t) equals a linear combination of products ∏_{e∈C} I′_{e}(t), where C ranges over the subsets of A(α) ∪ B(α); summing over α ∈ T_{kn} and collecting terms according to the isomorphism type of the graph spanned by the edges in the set C, we finally arrive at the decomposition

X_{kn}(t) = ∑_{H} ψ̂_{kn}(H; t)S_{n}(H; t),

where H ranges over unlabelled graphs (without isolated vertices), ψ̂_{kn}(H; t) are some deterministic functions and

S_{n}(H; t) = ∑_{F} ∏_{e∈F} I′_{e}(t),

where F ranges over all subgraphs of K_{n} that are isomorphic to H (counted with multiplicity aut(H), for convenience). See [8] for further details.

We do not have to calculate the coefficients ψ̂_{kn}(H; t) exactly, but it will be important to know that the terms when H is not a tree are sufficiently small.

Lemma 2.7. Suppose that H is not a tree. If H has v (non-isolated) vertices and e edges, and t = τ/n with τ > 0 fixed, then (for n ≥ τ)

n^{v/2}t^{e/2}|ψ̂_{kn}(H; t)| ≤ C_{10}(k, H, τ).

Proof. Let us consider one of the terms in the construction above. Fix α and C, and suppose that C consist of k − 1 − j of the k − 1 edges in A(α) and m of the edges in B(α), and that the graph F spanned by the edges in C is isomorphic to H. Further, suppose that H has c components, and that w ≥ 0 of the vertices in α do not appear among the vertices of F (because they are not endpoints of any edge in C). We study the construction of F in three steps. First we start with α and remove j edges; this leaves a forest with k vertices, k − 1 − j edges and j + 1 components (including isolated vertices). Secondly, we add m edges from B, which may only reduce the number of components. Finally, the w remaining isolated vertices are removed. This yields the relations

e = k − 1 − j + m
c ≤ j + 1 − w.

Furthermore, the resulting coefficient of ∏_{e∈F} I′_{e}(t), b(t) say, equals t^{j}(1−t)^{|B(α)|−m}(−1)^{m}. Hence

n^{e/2+c+w}t^{e/2}|b(t)| ≤ n^{e/2+j+1}t^{e/2+j} = n(nt)^{e/2+j}

or

n^{w}|b(t)| ≤ n^{1−c−e/2}t^{−e/2}(nt)^{e/2+j}.  (2.13)

When summing over α and collecting the terms that contribute to ψ̂_{kn}(H; t), we note that several different choices of α and C ⊂ A(α) ∪ B(α) may give the same F. In particular, there are \binom{n−v}{w} ≤ n^{w} choices of the w vertices in α that do not appear in F, but apart from that, the number of possibilities is finite and independent of n (for n large enough). Hence (2.13) implies

|ψ̂_{kn}(H; t)| ≤ C_{11}(k, H)n^{1−c−e/2}t^{−e/2} ∑_{j=0}^{k−1}(nt)^{e/2+j}

and, with t = τ/n,

n^{v/2}t^{e/2}|ψ̂_{kn}(H; t)| ≤ C_{11}(k, H)n^{1−(2c+e−v)/2} ∑_{j=0}^{k−1} τ^{e/2+j}.

Now, v ≤ c + e, with strict inequality except when H is a forest. Hence 2c + e − v = c + (c + e − v) ≥ 2 unless H is a connected forest, i.e. a tree, which completes the proof.

□

We are now prepared to apply the results of [8]. We first consider a fixed k ≥ 1.

First, by Lemmas 2.4, 2.5 and 2.6 and [8, Proposition 4.10], with p_{n} = τ/n and β_{n} = n^{1/2} (τ > 0 fixed), X_{kn}(τ/n) is “almost finitely dominated” by e.g. the family of all graphs. (This means that the variable can be expressed as a function of small subgraph counts, up to a small remainder term.) Moreover, by Lemma 2.7 and [8, Proposition 4.6], X_{kn}(τ/n) is almost finitely dominated by the family of all trees. We now apply [8, Theorem 14], with H the family of all trees, p_{n} = 1/n, p = 0, β_{n} = n^{1/2}, and φ(t) = C_{7}(k)^{1/2}e^{−t/4}. Apart from the facts established above and in Lemma 2.6, this theorem also requires that

n^{v/2−e/2}ψ̂_{kn}(H; τ/n)/\sqrt{n} = ψ̂_{kn}(H; τ/n) → a_{k}(H; τ)

for every tree H and τ ≥ 0 and some functions a_{k}(H; τ). This can be shown by the argument in the proof of Lemma 2.7, but it can also be avoided completely by the subsequence argument in the proofs of [8, Theorems 3 and 13] (it is unfortunate that this version of the theorem is not stated explicitly in [8]). Consequently, we obtain from [8, Theorem 14], using Lemma 2.3,

\frac{X_{kn}(t/n) − E X_{kn}(t/n)}{\sqrt{n}} ⟶^{d} V_{k}(t) as n → ∞,

in D([0, ∞]), where V_{k}(t) is a continuous Gaussian process with mean E V_{k}(t) = 0 and covariance function

E(V_{k}(t)V_{k}(u)) = lim_{n→∞} Cov(X_{kn}(t/n), X_{kn}(u/n)) = σ_{kk}(t, u).

This proves the first assertion in Theorem 2 for a fixed k, and the second follows because

n^{−1/2}(E X_{kn}(t/n) − nμ_{k}(t)) → 0, uniformly in t ≥ 0,

by Lemma 2.2(ii). Joint convergence for several different k follows by the argument above and the Cramr-Wold device, cf. [8, Remark 8.2]. □

3. Proof of Theorem 1.

The minimal spanning tree may be found by the greedy algorithm, see Kruskal [9]; consider the edges in order of increasing weights and select all edges that do not connect two vertices that already are connected by some sequence of selected edges. In other words, we select the edges in G_{n}(t) that decrease the number of components when they appear. If N(t) is the number of selected edges up to time t, and K(t) is the number of components of G_{n}(t), then K(t) = n − N(t). Hence, letting M be the set of edges in the minimal spanning tree,

W_{n} = ∑_{e∈M} T_{e} = ∑_{e∈M} ∫_{0}^{1} I(t < T_{e}) dt = ∫_{0}^{1} ∑_{e∈M}(1 − I(t ≥ T_{e}))dt

= ∫_{0}^{1}(n − 1 − N(t))dt = ∫_{0}^{1}(K(t) − 1) dt.  (3.1)

In order to analyze this further, we study different types of components of G_{n}(t) separately. We already have defined X_{kn}(t) as the number of components of G_{n}(t) that are trees of order k. We further let Y_{kn}(t) be the number of unicyclic components of order k, and Z_{n}(t) the number of components with more than one cycle. Clearly,

K(t) = ∑_{k=1}^{n} X_{kn}(t) + ∑_{k=3}^{n} Y_{kn}(t) + Z_{n}(t)

and the theorem follows from (3.1) and the following five lemmas.

Lemma 3.1.

n^{1/2}(∑_{k=1}^{n} ∫_{0}^{1} X_{kn}(t) dt − ∑_{k=1}^{n} ∫_{0}^{1} E X_{kn}(t) dt) ⟶^{d} N(0, σ^{2})

with

σ^{2} = ∑_{k,l=1}^{∞} ∫_{0}^{∞} ∫_{0}^{∞} σ_{kl}(t, u) dt du.

Lemma 3.2.

∑_{k=1}^{n} ∫_{0}^{1} E X_{kn}(t) dt = ζ(3) + O(1/n).

Lemma 3.3.

E ∑_{k=3}^{n} ∫_{0}^{1} Y_{kn}(t) dt = O(1/n)

and thus

n^{1/2} ∫_{0}^{∞} ∑_{k=3}^{n} Y_{kn}(t) dt ⟶^{p} 0.

Lemma 3.4.

E ∫_{0}^{1} |Z_{n}(t) − 1| dt = O(log n/n)

and thus

n^{1/2} ∫_{0}^{1}(Z_{n}(t) − 1) dt ⟶^{p} 0.

Lemma 3.5.

σ^{2} = ∑_{k,l=1}^{∞} ∫_{0}^{∞} ∫_{0}^{∞} σ_{kl}(t, u) dt du = \frac{π^{2}}{45} − 2 ∑_{i=0}^{∞} ∑_{j=1}^{∞} ∑_{k=1}^{∞} \frac{(i + k − 1)! k^{k}(i + j)^{i−2}j}{i! k! (i + j + k)^{i+k+2}} .

Proof of Lemma 3.1. For convenience, we introduce the normalized variables

X_{kn}^{∗}(t) = \frac{X_{kn}(t) − E X_{kn}(t)}{\sqrt{n}};

note that X_{kn}^{∗}(t) = 0 when k > n or t > 1. By Theorem 2,

X_{kn}^{∗}(t/n) ⟶^{d} V_{k}(t)

in D([0, ∞]) as n → ∞, for every k; since the integral over a finite interval is a continuous functional on D([0, ∞]), this implies

∫_{0}^{A} X_{kn}^{∗}(t/n) dt ⟶^{d} ∫_{0}^{A} V_{k}(t) dt

for any A < ∞. Moreover, by the joint convergence for any finite set of k, also

∑_{1}^{N} ∫_{0}^{A} X_{kn}^{∗}(t/n) dt ⟶^{d} ∑_{1}^{N} ∫_{0}^{A} V_{k}(t) dt  (3.2)

for every A, N < ∞. We want to extend this to A = N = ∞, and therefore observe that by Lemma 2.5,

∥X_{kn}^{∗}(t/n)∥_{2} = Var(X_{kn}^{∗}(t/n))^{1/2} ≤ C_{12}k^{−5/4}e^{−t/4}.  (3.3)

Since ∥X_{kn}^{∗}(t/n)∥_{2} → σ_{kk}(t, t)^{1/2} = ∥V_{k}(t)∥_{2} as n → ∞ by Lemma 2.3, also

∥V_{k}(t)∥_{2} ≤ C_{12}k^{−5/4}e^{−t/4}.  (3.4)

Since ∑_{k=1}^{∞} ∫_{0}^{∞} k^{−5/4}e^{−t/4} dt < ∞, (3.4) implies that the variable

U = ∑_{k=1}^{∞} ∫_{0}^{∞} V_{k}(t) dt

is well-defined in L^{2}. Moreover, if

U_{N} = ∑_{1}^{N} ∫_{0}^{N} V_{k}(t) dt,

U_{Nn}^{∗} = ∑_{k=1}^{N} ∫_{0}^{N} X_{kn}^{∗}(t/n) dt,

U_{n}^{∗} = ∑_{k=1}^{∞} ∫_{0}^{∞} X_{kn}^{∗}(t/n) dt = ∑_{k=1}^{n} ∫_{0}^{n} X_{kn}^{∗}(t/n) dt,

then U_{N} → U in L^{2}, and thus in distribution, as N → ∞, while U_{Nn}^{∗} → U_{n}^{∗} in L^{2} (and thus in probability) uniformly in n as N → ∞, because by (3.3),

∥U_{Nn}^{∗} − U_{n}^{∗}∥_{2} ≤ (∑_{1}^{N} ∫_{N}^{∞} + ∑_{N+1}^{∞} ∫_{0}^{∞})∥X_{kn}^{∗}(t/n)∥_{2} dt

≤ (∑_{1}^{N} ∫_{N}^{∞} + ∑_{N+1}^{∞} ∫_{0}^{∞})C_{12}k^{−5/4}e^{−t/4} dt → 0.

Finally, U_{Nn}^{∗} ⟶^{d} U_{N} as n → ∞ for each N by (3.2). This implies, by [2, Theorem 4.2], that

U_{n}^{∗} ⟶^{d} U  as n → ∞.  (3.5)

Since U is the limit of (Riemann) sums of the jointly normal random variables V_{k}(t), U has a normal distribution; the parameters are given by

E U = ∑_{1}^{∞} ∫_{0}^{∞} E V_{k}(t) dt = 0

and

Var U = E U^{2} = ∑_{k=1}^{∞} ∑_{l=1}^{∞} ∫_{0}^{∞} ∫_{0}^{∞} E(V_{k}(t)V_{l}(u)) dt du

= ∑_{k=1}^{∞} ∑_{l=1}^{∞} ∫_{0}^{∞} ∫_{0}^{∞} σ_{kl}(t, u) dt du.

Thus U ∼ N(0, σ^{2}). The result now follows from (3.5), because by our definitions,

U_{n}^{∗} = n ∑_{k=1}^{n} ∫_{0}^{1} X_{kn}^{∗}(t) dt

= \sqrt{n} ∑_{k=1}^{n} ∫_{0}^{1}(X_{kn}(t) − E X_{kn}(t)) dt.

□

Proof of Lemma 3.2. Let μ_{kn} = ∫_{0}^{1} E X_{kn}(t) dt. By Lemma 2.2(i) and evaluation of a beta integral

\begin{aligned}μ_{kn} & = \binom{n}{k}k^{k−2} \frac{Γ(k)Γ(nk − k^{2}/2 − 3k/2 + 2)}{Γ(nk − k^{2}/2 − k/2 + 2)} \\ & = \frac{(n)_{k}}{k!} k^{k−2} \frac{(k − 1)!}{(nk − k^{2}/2 − k/2 + 1)_{k}} \end{aligned}

= k^{k−3} \frac{(n)_{k}}{(nk − k^{2}/2 − k/2 + 1)_{k}} .

A Taylor expansion of the logarithm yields, for k ≤ n/2 say,

log(n)_{k} = k log n + ∑_{1}^{k−1} log(1 − \frac{i}{n}) = k log n − \frac{k(k − 1)}{2n} + O(\frac{k^{3}}{n^{2}} ),

and similarly

log(nk − k^{2}/2 − k/2 + 1)_{k} = k log(nk − k^{2}/2 − k/2 + 1) + O(\frac{k^{2}}{nk} )

= k log(nk) + k log(1 − \frac{k}{2n} − \frac{1}{2n} + \frac{1}{nk}) + O(\frac{k^{2}}{nk} )

= k log(nk) − \frac{k^{2}}{2n} + O(\frac{k}{n} + \frac{k^{3}}{n^{2}} ).

Hence, if 1 ≤ k ≤ \sqrt{n},

μ_{kn} = k^{k−3} \frac{n^{k}}{(nk)^{k}} exp(O(\frac{k}{n})) = k^{−3}(1 + O(\frac{k}{n})) = k^{−3} + O(n^{−1}k^{−2}).

For \sqrt{n} < k ≤ n we instead use Lemma 2.1 to conclude (assuming as we may n ≥ 4),

μ_{kn} ≤ C_{1}k^{k−3} \frac{(n − k/2 − 3/2)^{k}}{(nk − k^{2}/2 − 3k/2)^{k}} = C_{1}k^{−3}.

For k > n, we trivially have μ_{kn} = 0.

Consequently,

\begin{aligned}|∑_{1}^{n} μ_{kn} − ∑_{1}^{∞} k^{−3}| & ≤ ∑_{1}^{\sqrt{n}} |μ_{kn} − k^{−3}| + ∑_{\sqrt{n}}^{∞}(1 + C_{1})k^{−3} \\ & ≤ \frac{C_{13}}{n} ∑_{1}^{∞} \frac{1}{k^{2}} + C_{14} ∑_{\sqrt{n}}^{∞} k^{−3} \end{aligned}

≤ \frac{C_{15}}{n} .

□

Proof of Lemma 3.3. Let m(k) be the number of connected graphs with k edges on k (labelled) vertices. Then

E Y_{kn}(t) = \binom{n}{k}m(k)t^{k}(1 − t)^{nk−k^{2}+\binom{k}{2}−k}

and thus, evaluating a beta integral as in the proof of Lemma 3.2,

∫_{0}^{1} E Y_{kn}(t) dt = \binom{n}{k}m(k)\frac{Γ(k + 1)}{(nk − k^{2}/2 − k/2 + 1)_{k+1}}

= m(k)\frac{(n)_{k}}{(nk − k^{2}/2 − k/2 + 1)_{k+1}} .

Since m(k) = \frac{1}{2}(k − 1)! ∑_{j=0}^{k−3} k^{j}/j! < (k − 1)!e^{k} ≤ C_{16}k^{k−1/2}, see e.g. [3, Theorem 18], we obtain using Lemma 2.1 for 3 ≤ k ≤ n and n ≥ 4,

\begin{aligned}∫_{0}^{1} E Y_{kn}(t) dt & ≤ C_{17}k^{k−1/2} \frac{(n − k/2 − 3/2)^{k}}{(nk − k^{2}/2 − 3k/2)^{k+1}} \\ & = C_{17} \frac{k^{−3/2}}{n − k/2 − 3/2} \end{aligned}

≤ C_{18}k^{−3/2}n^{−1}.

The result follows because ∑_{1}^{∞} k^{−3/2} < ∞. □

Proof of Lemma 3.4. We consider the integrals over [0, 3 log n/n] and [3 log n/n, 1] separately. Let Z̃_{n} be the number of times during the evolution of G_{n}(t) that a component with at least two cycles is formed (either by the creation of an edge joining two unicyclic components or by the creation of an edge joining two vertices in the same unicyclic component). Clearly Z_{n}(t) ≤ Z̃_{n} for every t, and thus

∫_{0}^{3 log n/n} E |Z_{n}(t) − 1| dt ≤ ∫_{0}^{3 log n/n} E(Z̃_{n} + 1) dt = \frac{3 log n}{n}(E Z̃_{n} + 1).

It was proved in [7] that E Z̃_{n} = O(1) (in fact, EZ̃_{n} → 5π/8\sqrt{3} as n → ∞); hence

∫_{0}^{3 log n/n} E |Z_{n}(t) − 1| dt = O(\frac{log n}{n}).

On the other hand, let E be the event that G_{n}(3 log n/n) is connected and has more than n edges. If E happens, then Z_{n}(t) = 1 for all t ≥ 3 log n/n; thus we conclude from the trivial estimate |Z_{n}(t) − 1| ≤ n that

∫_{3 log n/n}^{1} E |Z_{n}(t) − 1| dt ≤ ∫_{3 log n/n}^{1} n P(E^{c}) dt ≤ n P(E^{c}) = O(n^{−1}),

since P(E^{c}) = O(n^{−2}) as is easily shown, cf. [3, Exercise II.15]. The lemma follows. □

Proof of Lemma 3.5. We first observe that

|σ_{kl}(t, u)| ≤ ∥V_{k}(t)∥_{2}∥V_{l}(u)∥_{2} ≤ C_{12}^{2}k^{−5/4}e^{−t/4}l^{−5/4}e^{−u/4}

by Cauchy-Schwarz’ inequality and (3.4), and thus ∑ ∑ ∫ ∫ |σ_{kl}(t, u)| < ∞. This and the gamma integrals ∫ μ_{k}(t) dt = ∫ tμ_{k}(t) dt = k^{−3} imply easily that all integrals and sums below are finite.

By the definitions,

σ^{2} = 2 ∑_{k,l=1}^{∞} ∫∫_{t≤u} σ_{kl}(t, u) dt du = 2 ∑_{k,l=1}^{∞} ∫_{0}^{∞} ∫_{0}^{∞} σ_{kl}(t, t + s) ds dt

= 2( ∑_{k,l=1}^{∞} I_{1}(k, l) + ∑_{k=1}^{∞} I_{2}(k) + ∑_{k=1}^{∞} ∑_{l=k+1}^{∞} I_{3}(k, l)),

where

\begin{aligned}I_{1}(k, l) & = ∫_{0}^{∞} ∫_{0}^{∞} kl(t − 1)μ_{k}(t)μ_{l}(t + s) ds dt, \\ I_{2}(k) & = ∫_{0}^{∞} ∫_{0}^{∞} e^{−ks}μ_{k}(t) ds dt, \end{aligned}

I_{3}(k, l) = ∫_{0}^{∞} ∫_{0}^{∞} \frac{k^{k−1}}{k! (l − k)!}t^{k−1}s(ls + (l − k)t)^{l−k−1}e^{−ls−lt} ds dt.

Binomial expansions and standard integrations yield

I_{1}(k, l) = \frac{k^{k−1}}{k!} \frac{l^{l−1}}{l!} ∫_{0}^{∞} ∫_{0}^{∞}(t − 1)t^{k−1}(t + s)^{l−1}e^{−(k+l)t−ls} dt ds

= \frac{k^{k−1}}{k!} \frac{l^{l−1}}{l!} ∑_{i=0}^{l−1} ∫_{0}^{∞} ∫_{0}^{∞} \binom{l − 1}{i}(t^{k+i} − t^{k+i−1})s^{l−1−i}e^{−(k+l)t−ls} dt ds

= ∑_{i=0}^{l−1} \frac{k^{k−1}}{k!} \frac{l^{l−1}}{l!} \frac{(l − 1)!}{i! (l − 1 − i)!} \frac{(k + i − 1)! (k + i − (k + l))}{(k + l)^{k+i+1}} \frac{(l − i − 1)!}{l^{l−i}}

= − ∑_{i=0}^{l−1} \frac{(k + i − 1)! k^{k−1}l^{i−2}(l − i)}{k! i! (k + l)^{k+i+1}},

I_{2}(k) = ∫_{0}^{∞} e^{−ks} ds ∫_{0}^{∞} \frac{k^{k−2}}{k!} t^{k−1}e^{−kt} dt = k^{−1} \frac{k^{k−2}}{k!} \frac{(k − 1)!}{k^{k}} = k^{−4},

and, for l > k,

I_{3}(k, l) = \frac{k^{k−1}}{k! (l − k)!} ∑_{i=0}^{l−k−1} ∫_{0}^{∞} ∫_{0}^{∞} \binom{l − k − 1}{i}(l − k)^{i}t^{k−1+i}l^{l−k−1−i}

s^{l−k−i}e^{−ls−lt} ds dt

= ∑_{i=0}^{l−k−1} \frac{k^{k−1}}{k! (l − k)!} \frac{(l − k − 1)!}{i! (l − k − 1 − i)!}(l − k)^{i}l^{l−k−1−i} \frac{(k + i − 1)!}{l^{k+i}} \frac{(l − k − i)!}{l^{l−k−i+1}}

= ∑_{i=0}^{l−k−1} \frac{(k + i − 1)! k^{k−1}(l − k)^{i−1}}{k! i! l^{k+i+2}} (l − k − i).

Summing and substituting l = i + j in I_{1} and l = k + i + j in I_{3}, we obtain

σ^{2} = 2 ∑_{k=1}^{∞} k^{−4} + 2 ∑_{k=1}^{∞} ∑_{i=0}^{∞} ∑_{j=1}^{∞} \frac{(k + i − 1)! k^{k−1}(i + j)^{i−2}j}{k! i! (k + i + j)^{k+i+2}} (−(k + i + j) + i + j)

and the result follows, using the well-known formula ∑_{1}^{∞} k^{−4} = π^{4}/90. □

We have completed the proof of Theorem 1, and it remains only to indicate the small modifications needed to show the corresponding result for spanning pseudoforests stated in Remark 1.5.

It is not difficult to see that the minimum weight pseudoforest consists of the edges in G_{n}(t) that have at least one endpoint in a tree component when they appear (cf. Gabow and Tarjan [6, Lemma 2.1]). Each such edge decreases the number of tree components by one; thus, if N′(t) denotes the number of selected edges that has appeared up to time t, then N′(t) = n − X(t), where X(t) = ∑_{k=1}^{n} X_{kn}(t) is the number of tree components of G_{n}(t). An argument as above then shows

W′_{n} = ∫_{0}^{1}(n − N′(t)) dt = ∫_{0}^{1} X(t) dt = ∑_{k=1}^{n} ∫_{0}^{1} X_{kn}(t) dt

and the result follows by Lemmas 3.1, 3.2 and 3.5. (Thus Lemmas 3.4 and 3.5 are not needed for spanning pseudoforests.)

References

1. A.D. Barbour, Poisson convergence and random graphs, Math. Proc. Camb. Phil. Soc. 92 (1982), 349–359.

2. P. Billingsley, Convergence of Probability Measures, Wiley, New York, 1968.

3. B. Bollobás, Random Graphs, Academic Press, London, 1985.

4. A. Cayley, A theorem on trees, Q. J. Pure Appl. Math. 23 (1889), 376–378.

5. A.M. Frieze, On the value of a minimal spanning tree problem, Discrete Appl. Math. 10 (1985), 47–56.

6. H.N. Gabow and R.E. Tarjan, A linear-time algorithm for finding a minimum spanning pseudoforest, Information Processing Letters 27 (1988), 259–263.

7. S. Janson, Multicyclic components in a random graph process, Random Struct. Alg. 4 (1993), 71–84.

8. S. Janson, Orthogonal decompositions and functional limit theorems for random graph statistics, Memoirs Amer. Math. Soc. 534 (1994).

9. J.B. Kruskal, The expected number of components under random mapping functions, Amer. Math. Monthly 61 (1954), 392–397.

10. B. Pittel, On tree census and the giant component in sparse random graphs, Random Struct. Alg. 1 (1990), 311–342.

11. A. Rényi, Some remarks on the theory of trees, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 73–85.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

   E-mail address: svante.janson@math.uu.se