THE FIRST EIGENVALUE OF RANDOM GRAPHS

SVANTE JANSON

To Béla Bollobás on his 60th birthday

Abstract. We extend a result by Füredi and Komlós and show that the first eigenvalue of a random graph is asymptotically normal, both for G_{n,p} and G_{n,m}, provided np ≥ n^{δ} or m/n ≥ n^{δ} for some δ > 0. The asymptotic variance is of order p for G_{n,p}, and n^{−1} for G_{n,m}. This gives a (partial) solution to a problem raised by Krivelevich and Sudakov.

The formula for the asymptotic mean involves a mysterious power series.

1. Introduction

Füredi and Komlós [2] investigated the eigenvalues of random symmetric matrices. In particular, their result shows that for constant p ∈ (0, 1), the first eigenvalue λ_{1} of the adjacency matrix of the random graph G_{n,p} is asymptotically normal, with

λ_{1}(G_{n,p}) − (n − 1)p − 1 + p →^{d} N(0, 2p(1 − p))  as n → ∞.  (1.1)

In fact, [2] showed that the random fluctuation of of λ_{1}(G_{n,p}) asymptotically can be completely explained by the fluctuation of the number of edges in G_{n,p}. More precisely, they showed that if e(G_{n,p}) ∼ N (\binom{n}{2}, p) is the number of edges in G_{n,p}, then

λ_{1}(G_{n,p}) − \frac{2e(G_{n,p})}{n} − (1 − p) = O_{p} (n^{−1/2}) →^{p} 0,

which immediately implies (1.1) by the central limit theorem.

This suggests studying λ_{1}(G_{n,p}) conditioned on a given e(G_{n,p}), or, equivalently, λ_{1}(G_{n,m}), where m is a given function of n. Assume first, in analogy to the case studied by Füredi and Komlós, that m/\binom{n}{2} → p, with p ∈ (0, 1) fixed. We will show that then λ_{1}(G_{n,m}) too is asymptotically normal, but with an asymptotic variance of order only n^{−1}.

We will also extend the results to p → 0 and m/\binom{n}{2} → 0, as long as np ≫ n^{δ} and m ≫ n^{1+δ} for some δ > 0.

Krivelevich and Sudakov [6] have found the first order asymptotics of λ_{1}(G_{n,p}) for all p = p(n); in particular, for p in the range treated here, their result gives λ_{1}(G_{n,p})/(np) →^{p} 1. They leave the question of the limit distribution as an open problem, which we thus (partially) answer. Note also the large deviation result by Alon, Krivelevich and Vu [1].

Our main results are the following. Here and elsewhere in this paper, (a_{i})_{i=0}^{∞} is a certain sequence of integers, defined in Section 4. We have computed a_{j} for j ≤ 10 by calculations with Pascal and Maple and found (unless we made a mistake)

A(z) := ∑_{0}^{∞} a_{j}z^{j} = 1 + z + z^{2} + z^{5} + z^{7} + 5z^{8} + 2z^{9} + 17z^{10} + …

Date: August 4, 2003; revised February 17, 2005.

No simple form is evident.

Theorem 1.1. Suppose that n → ∞, p → p_{0} ∈ [0, 1) and n^{1−δ}p → ∞, for some fixed δ > 0. Let, for some integer J with 2J + 1 ≥ 1/δ,

α_{n,p} := (n − 2)p + ∑_{j=1}^{J} a_{j}(np)^{1−j} = ∑_{j=0}^{J} a_{j}(np)^{1−j} − 2p.

Then

p^{−1/2}(λ_{1}(G_{n,p}) − α_{n,p}) →^{d} N(0, 2(1 − p_{0})).

Theorem 1.2. Suppose that n → ∞, m/\binom{n}{2} → p_{0} ∈ [0, 1) and n^{−1−δ}m → ∞ for some fixed δ > 0. Let, for some integer J with 2J ≥ 1/δ,

α_{n,m} := \frac{2m}{n} + ∑_{j=1}^{J} a_{j}(\frac{2m}{n})^{1−j} − \frac{2m}{n^{2}} = \frac{2m}{n}(∑_{j=0}^{J} a_{j}(\frac{2m}{n})^{−j} − \frac{1}{n}).

Then

n^{1/2}(λ_{1}(G_{n,m}) − α_{n,m}) →^{d} N(0, 2(1 − p_{0})^{2}).

Note that J is chosen such that terms a_{j}(np)^{1−j} or a_{j}(2m/n)^{1−j} with j > J can be ignored.

The definition of (a_{i})_{i=0}^{∞} in Section 4 is rather involved, and we find the numbers a_{j} quite mysterious. Lemma 3.1 exhibits the combinatorial significance of these numbers perhaps better than the theorems above. Nevertheless we are lacking a simple combinatorial interpretation of a_{j}, and leave it as an open problem to understand these numbers better.

Theorem 1.1 follows easily from Theorem 1.2. We will, however, prove both in parallel by the same method. Not surprisingly, the details are somewhat simpler for Theorem 1.1, but we will see that with our methods, the difference is not great.

Remark 1.3. Also for p → 0, the random variation of λ_{1}(G_{n,p}) is explained by the variation of the number of edges e(G_{n,p}) in the sense of linear regression. I.e., we have λ_{1}(G_{n,p}) = a(n, p)e(G_{n,p})+b(n, p)+R for certain constants a(n, p) and b(n, p) and a random error term R such that p^{−1/2}R →^{p} 0 while p^{−1/2}a(n, p)(e(G_{n,p}) − 𝔼 e(G_{n,p})) converges in distribution.

For G_{n,m}, where the number of edges is constant and explains nothing, the proof shows that the variation is explained in this way by the number of paths of length 2 (or, equivalently, by the sum of the squares of the vertex degrees).

The proof uses the traditional method of computing the trace of a suitable power of the adjacency matrix as the number of closed walks of a given length in the graph. This number is closely related to subgraph counts, and we use methods from [3] to find the required asymptotics.

We consider the case np ≫ n^{δ} (m/n ≫ n^{δ}) for some δ > 0. It turns out that the smaller δ is, the higher matrix powers and the longer walks have to be employed (otherwise we cannot ignore the other eigenvalues); we also need more terms in the sums defining α_{n,p} and α_{n,m}. We thus give general arguments treating arbitrarily long walks below. If we restricted ourselves to, say, p ≥ n^{−1/2}, we would only have to consider a few small values of this length, and the general arguments could be replaced by explicit calculations, which would make the proof simpler but perhaps less interesting.

Remark 1.4. Note that we only study the case when p or m is so large that there is a large gap between the first and second eigenvalue. It seems that different methods are needed in the case of sparser graphs. Perhaps the methods of [6] could be useful.

Remark 1.5. Füredi and Komlós [2] studied more general random symmetric matrices where the entries are not restricted to 0 and 1. We leave it to the reader to extend the results of this paper to such matrices.

Remark 1.6. Note that λ_{1}(G) ≥ 2e(G)/n for every graph G with n vertices, since vAv^{t} = 2e(G)/n if v = n^{−1/2}(1, …, 1) and A is the adjacency matrix of G. The results above show that, with high probability, we almost have equality for the random graphs studied here, which witnesses that the eigenvector for λ_{1} is close to v.

If X_{n} are random variables and c_{n} positive numbers, we write X_{n} = o_{p}(c_{n}) if X_{n}/c_{n} →^{p} 0, and X_{n} = O_{p}(c_{n}) if the sequence X_{n}/c_{n} is stochastically bounded (tight).

If H is a graph, v(H), e(H) and aut(H) denote the numbers of vertices, edges and automorphisms of H.

Acknowledgement. Part of this research was done on a previous visit to Cambridge. I thank Béla Bollobás for interesting discussions.

2. Matrices

We denote the eigenvalues (with multiplicities) of a real symmetric matrix M by λ_{1}(M) ≥ λ_{2}(M) ≥ ⋯ ≥ λ_{ν}(M). For a graph G, we similarly denote the eigenvalues of its adjacency matrix by λ_{1}(G) ≥ . . ..

The algebraic part of our proofs is the following lemma.

Lemma 2.1. Let M be a real symmetric matrix and let T_{k} := Tr(M^{k}) = ∑_{i} λ_{i}(M)^{k}. Suppose that, for some even k ≥ 2 and μ > 0,

λ_{1}(M) ≥ μ,  (2.1)
T_{k} ≤ μ^{k}(1 + 2^{−k}).  (2.2)

Then

T_{k}(2 − \frac{T_{k−2}T_{k+2}}{T_{k}^{2}} ) ≤ λ_{1}(M)^{k} ≤ T_{k}.

Proof. Let δ_{i} = λ_{i}/λ_{1}, 1 ≤ i ≤ ν, where ν is the size of M. First, by (2.1) and (2.2),

1 + ∑_{i=2}^{ν} δ_{i}^{k} = T_{k}/λ_{1}^{k} ≤ 1 + 2^{−k}.

Hence |δ_{i}| ≤ 1/2 for i ≥ 2. In particular,

(1 − δ_{i}^{2})^{2} ≥ (\frac{3}{4})^{2} > \frac{1}{2} ≥ 2δ_{i}^{2}.

Consequently,

T_{k−2}T_{k+2} − T_{k}^{2} = ∑_{i,j=1}^{ν}(λ_{i}^{k−2}λ_{j}^{k+2} − λ_{i}^{k}λ_{j}^{k}) = ∑_{i<j}(λ_{i}^{k−2}λ_{j}^{k+2} + λ_{i}^{k+2}λ_{j}^{k−2} − 2λ_{i}^{k}λ_{j}^{k})

= ∑_{i<j} λ_{i}^{k−2}λ_{j}^{k−2}(λ_{i}^{2} − λ_{j}^{2})^{2} ≥ ∑_{j=2}^{ν} λ_{1}^{k+2}λ_{j}^{k−2}(1 − δ_{j}^{2})^{2}

≥ ∑_{j=2}^{ν} λ_{1}^{k+2}λ_{j}^{k−2} · 2δ_{j}^{2} = 2λ_{1}^{k} ∑_{j=2}^{ν} λ_{j}^{k} = 2λ_{1}^{k}(T_{k} − λ_{1}^{k})

≥ T_{k}(T_{k} − λ_{1}^{k}).

The left inequality follows. The right one is immediate. □

Lemma 2.2. Let M_{n}, n ≥ 1, be random symmetric matrices (of arbitrary sizes), and let T_{k,n} := Tr(M_{n}^{k}). Suppose that μ_{n} > 0 are real numbers such that for every η > 0

ℙ(λ_{1}(M_{n}) ≥ (1 − η)μ_{n}) → 1 as n → ∞, (2.3)

and that Y is a random variable and ε_{n} → 0 are positive numbers such that

ε_{n}^{−1}(\frac{T_{k,n}}{μ_{n}^{k}} − 1) →^{d} kY  as n → ∞,  (2.4)

jointly for three fixed consecutive even values of k. Then

ε_{n}^{−1}(\frac{λ_{1}(M_{n})}{μ_{n}} − 1) →^{d} Y as n → ∞.

Proof. Write

T_{k,n} = μ_{n}^{k}(1 + ε_{n}kY_{k,n}).  (2.5)

Thus Y_{k,n} →^{d} Y jointly for three even values of k, say k = m − 2, m and m + 2, and

hence (m − 2)Y_{m−2,n} + (m + 2)Y_{m+2,n} − 2mY_{m,n} →^{p} 0. Then

\begin{aligned}Q_{n} & := \frac{T_{m−2,n}T_{m+2,n}}{T_{m,n}^{2}} = \frac{(1 + ε_{n}(m − 2)Y_{m−2,n})(1 + ε_{n}(m + 2)Y_{m+2,n})}{(1 + ε_{n}mY_{m,n})^{2}} \\ & = 1 + ε_{n}((m − 2)Y_{m−2,n} + (m + 2)Y_{m+2,n} − 2mY_{m,n}) + o_{p}(ε_{n}) \\ & = 1 + o_{p}(ε_{n}). \end{aligned} (2.6)

(The reader that prefers may use the Skorohod representation theorem [5, Theorem 4.30] and assume for simplicity that Y_{k,n} → Y a.s. for k = m − 2, m, m + 2; then o_{p} may be replaced by o.)

Moreover, with μ̃ := μ_{n}(1 − η), where η > 0 is so small that (1 − η)^{−k} < 1 + 2^{−k},

ℙ(T_{k,n} ≤ μ^{k}(1 + 2^{−k})) = ℙ(1 + ε_{n}kY_{n} ≤ (1 − η)^{k}(1 + 2^{−k})) → 1 as n → ∞.

Since ℙ(λ_{1}(M_{n}) ≥ μ̃) → 1 as n → ∞ by (2.3), we see that with probability tending to 1 as n → ∞, M_{n} satisfies the assumptions of Lemma 2.1 (with m and μ̃) and thus

ℙ[T_{m,n}(2 − Q_{n}) ≤ λ_{1}(M_{n})^{m} ≤ T_{m,n}] → 1.  (2.7)

Combined with (2.6), this yields

λ_{1}(M_{n})^{m} = T_{m,n}(1 + o_{p}(ε_{n}))

and thus

\begin{aligned}λ_{1}(M_{n}) & = T_{m,n}^{1/m}(1 + o_{p}(ε_{n})) = μ_{n}(1 + ε_{n}mY_{m,n})^{1/m}(1 + o_{p}(ε_{n})) \\ & = μ_{n}(1 + ε_{n}Y_{m,n} + o_{p}(ε_{n})). \end{aligned}

The result follows. □

We apply Lemma 2.2 to G_{n,p} and G_{n,m}, with μ_{n} = α_{n,p} and μ_{n} = α_{n,m}, respectively. Note that α_{n,p} = np(1 + o(1)) and α_{n,m} = \frac{2m}{n}(1 + o(1)). By Remark 1.6, λ_{1}(G_{n,m}) ≥ 2m/n, and (2.3) follows. For G_{n,p}, similarly, λ_{1} ≥ 2e(G_{n,p})/n and 2e(G_{n,p})/(n^{2}p) →^{p} 1 by the law of large numbers; again (2.3) follows.

Note further that if M is the adjacency matrix of a graph G, then Tr(M^{k}) equals the number of closed walks of length k in G; i.e. sequences v_{0}, …, v_{k} of vertices such that v_{0} = v_{k} and v_{i−1} and v_{i} are adjacent for 1 ≤ i ≤ k; we denote this number by W_{k}(G). Theorems 1.1 and 1.2 therefore follow by Lemma 2.2 from the following two lemmas. (The assumptions k ≥ 6/δ are made for convenience and could be weakened. However, the results are not true for, say, k = 2 or k = 4, even for constant p.)

Lemma 2.3. Under the hypotheses of Theorem 1.1, if Y ∼ N(0, 2(1 − p_{0})), then for every k ≥ 6/δ,

np^{1/2} (\frac{W_{k}(G_{n,p})}{α_{n,p}^{k}} − 1) →^{d} kY

and the convergence holds jointly for any set of such k.

Lemma 2.4. Under the hypotheses of Theorem 1.2, if Y ∼ N(0, 2(1 − p_{0})^{2}), then for every k ≥ 6/δ,

2mn^{−1/2} (\frac{W_{k}(G_{n,m})}{α_{n,m}^{k}} − 1) →^{d} kY

and the convergence holds jointly for any set of such k.

3. Random graphs

We prove Lemmas 2.3 and 2.4 using the orthogonal decomposition method of [3], summarized in [4, Section 6.4]. For convenience, we repeat the main definitions and results here, referring to [3] for proofs. We begin by defining an orthogonal family of functionals of G_{n,p}.

Let H be a graph. Consider the (n)_{v_{H}} injective mappings from the vertex set of H into {1, …, n}. Each such mapping φ maps H onto a copy φ(H) of H in K_{n}, and we define

S_{n,p}(H) := ∑_{φ} ∏_{e∈φ(H)}(I_{e} − p),  (3.1)

where I_{e} = 1[e ∈ G_{n,p}] is the indicator that the edge e is present. In other words, we sum ∏_{e∈H′}(I_{e} − p) over all copies of H in G_{n,p}, counted with multiplicities aut(H). Note that if X_{H}(G) denotes the number of copies of H in G, each counted with multiplicity aut(H), we have the similar formula

X_{H}(G_{n,p}) = ∑_{φ} ∏_{e∈φ(H)} I_{e},  (3.2)

where, however, the terms in the sum not are orthogonal.

S_{n,p}(H) depends on H only up to isomorphism. Hence we may regard H as an unlabelled graph.

Let U^{0} denote the set of unlabelled graphs without isolated vertices. Then the random variables {S_{n,p}(H)}_{H∈U^{0}} are orthogonal, and each functional of G_{n,p} that depends only on the isomorphism type is a linear combination of these variables. In particular,

W_{k}(G_{n,p}) = ∑_{H∈U^{0}} ŵ_{k}(n, p; H)S_{n,p}(H)  (3.3)

for some coefficients ŵ_{k}.

We allow here H to be the empty graph ∅ with v(∅) = e(∅) = 0; then S_{n,p}(∅) = 1. Since 𝔼 S_{n,p}(H) = 0 when H ≠ ∅, we have

ŵ_{k}(n, p; ∅) = 𝔼 W_{k}(G_{n,p}).  (3.4)

We can find the decomposition (3.3) as follows. A closed walk of length k may have a finite number (depending on k) different shapes, since one or several vertices may be repeated. Hence W_{k} can be written as a linear combination of different subgraph counts X_{H}. For example, with k = 4 we can have a 4-cycle, a path of length 2 with each edge traversed twice, or a single edge traversed four times, and we find

W_{4} = X_{C_{4}} + 2X_{P_{2}} + X_{K_{2}}.

(P_{l} denotes the path with l edges and thus l + 1 vertices.)

Next, substituting I_{e} = (I_{e} − p) + p in (3.2) and expanding, each X_{H} becomes a linear combination of S_{n,p}(K) for K ⊆ H. For example, straightforward calculations yield, with (n)_{k} = n(n − 1) ⋯ (n − k + 1),

X_{K_{2}}(G_{n,p}) = S_{n,p}(K_{2}) + (n)_{2}p
X_{P_{2}}(G_{n,p}) = S_{n,p}(P_{2}) + 2(n − 2)pS_{n,p}(K_{2}) + (n)_{3}p^{2}
X_{C_{4}}(G_{n,p}) = S_{n,p}(C_{4}) + 4pS_{n,p}(P_{3}) + 4(n − 3)p^{2}S_{n,p}(P_{2}) + 2p^{2}S_{n,p}(2K_{2})
+ 4(n − 2)(n − 3)p^{3}S_{n,p}(K_{2}) + (n)_{4}p^{4}.

In this way, we can obtain a decomposition (3.3) for any k explicitly (but the amount of work increases rapidly with k). Note that only terms with e(H) ≤ k appears.

For H ∈ U^{0},

S_{n,p}(H) = O_{p}(n^{v(H)/2}p^{e(H)/2}).  (3.5)

Hence we also define

S_{n,p}^{∗}(H) := n^{−v(H)/2}p^{−e(H)/2}S_{n,p}(H),  (3.6)
ŵ_{k}^{∗}(n, p; H) := n^{v(H)/2}p^{e(H)/2}ŵ_{k}(n, p; H);  (3.7)

thus (3.3) can be rewritten

W_{k}(G_{n,p}) = ∑_{H∈U^{0}} ŵ_{k}^{∗}(n, p; H)S_{n,p}^{∗}(H),  (3.8)

where by (3.5), for every H,

S_{n,p}^{∗}(H) = O_{p}(1).  (3.9)

If further H ≠ ∅ and H is connected, we have the limit result [3, Theorem 1], [4, Theorem 6.43] that if n → ∞, p → p_{0} ∈ [0, 1] and np^{m(H)} → ∞, where m(H) := max{e(F)/v(F) : F ⊆ H, v(F) > 0}, then, for some random variables U(H),

S_{n,p}^{∗}(H) →^{d} U(H) ∼ N(0, aut(H)(1 − p_{0})^{e(H)}).  (3.10)

To prove Lemma 2.3, it is now sufficient to verify, for k ≥ 6/δ,

𝔼 W_{k}(G_{n,p}) = α_{n,p}^{k}(1 + o(n^{−1}p^{−1/2}))  (3.11)
ŵ_{k}^{∗}(n, p; K_{2}) = α_{n,p}^{k}n^{−1}p^{−1/2}(k + o(1))  (3.12)
ŵ_{k}^{∗}(n, p; H) = o(α_{n,p}^{k}n^{−1}p^{−1/2}),  H ∈ U^{0}, v(H) ≥ 3,  (3.13)

because then (3.8) yields by (3.4), (3.9)

\begin{aligned}α_{n,p}^{−k}W_{k}(G_{n,p}) & = α_{n,p}^{−k} 𝔼 W_{k}(G_{n,p}) + α_{n,p}^{−k}ŵ_{k}^{∗}(n, p; K_{2})S_{n,p}^{∗}(K_{2}) + o_{p}(n^{−1}p^{−1/2}) \\ & = 1 + n^{−1}p^{−1/2}kS_{n,p}^{∗}(K_{2}) + o_{p}(n^{−1}p^{−1/2}), \end{aligned}

and Lemma 2.3 follows by (3.10), with Y = U(K_{2}).

To prove Lemma 2.4, we define p := m/\binom{n}{2} and note that

α_{n,p} = α_{n,m} + O(1/n) = α_{n,m}(1 + O(n^{−2}p^{−1})) = α_{n,m}(1 + o(n^{−3/2}p^{−1})).

For Lemma 2.4, we now need, for k ≥ 6/δ,

𝔼 W_{k}(G_{n,p}) = α_{n,p}^{k}(1 + o(n^{−3/2}p^{−1}))  (3.14)
ŵ_{k}^{∗}(n, p; P_{2}) = α_{n,p}^{k}n^{−3/2}p^{−1}(k + o(1))  (3.15)
ŵ_{k}^{∗}(n, p; H) = o(α_{n,p}^{k}n^{−3/2}p^{−1}),  H ∈ U^{0}, H ≠ ∅, K_{2}, P_{2}.  (3.16)

(No condition on ŵ_{k}^{∗}(n, p; K_{2}) is needed.) Indeed, using these estimates, [3, Theorem 7] or [4, Theorem 6.54], with β_{n} := n^{−3/2}p^{−1}α_{n,m}^{k}, shows that

n^{3/2}p (\frac{W_{k}(G_{n,m})}{α_{n,m}^{k}} − 1) →^{d} kU(P_{2})

(again jointly for different k), which yields Lemma 2.4 and thus Theorem 1.2.

It is important to note that we here draw a conclusion for G_{n,m} from the estimates (3.14)–(3.16) for G_{n,p}. In the remainder of the paper, we thus consider G_{n,p} only.

It remains to prove the estimates (3.11)–(3.13) and (3.14)–(3.16). Using α_{n,p} ∼ np and changing J, we restate (and partly improve) them slightly as the following lemmas, which thus contain the combinatorial part of the proof of Theorems 1.1 and 1.2. (We treat ŵ_{k}(n, p; ∅) = 𝔼 W_{k}(G_{n,p}) separately because a much smaller relative error is required.)

Lemma 3.1. Let δ > 0 and let k and J be fixed integers with J ≥ 1/δ and k ≥ 6/δ. If n → ∞ and np/n^{δ} → ∞, then

𝔼 W_{k}(G_{n,p}) = (np)^{k}(1 − \frac{2}{n} + ∑_{j=1}^{J} a_{j}(np)^{−j} + O(n^{−2}p^{−1}))^{k}.

Lemma 3.2. Let δ > 0 and k ≥ 4/δ be fixed, and suppose that H ∈ U^{0} with H ≠ ∅. If n → ∞ and np/n^{δ} → ∞, then

(np)^{−k}ŵ_{k}(n, p; H) = \begin{cases}kn^{−2}p^{−1} + o(n^{−2}p^{−1}), & H = K_{2}, \\ kn^{−3}p^{−2} + o(n^{−3}p^{−2}), & H = P_{2}, \\ o(n^{−v(H)/2−3/2}p^{−e(H)/2−1}), & H ≠ ∅, K_{2}, P_{2}. \end{cases}

4. Proof of Lemma 3.1

We begin by giving an explicit, although rather opaque, definition of the numbers a_{j} in Theorems 1.1 and 1.2.

For a tree T, let b_{k}(T) be the number of (not necessarily closed) walks of length k on T that traverse every edge at least twice. Let T_{n} be the set of the n^{n−2} trees on {1, …, n}, and let T := ⋃_{n=1}^{∞} T_{n}, and define the formal power series

Ψ(ε, z) := ∑_{k=0}^{∞} ∑_{n=1}^{∞} \frac{1}{n!} ∑_{T ∈T_{n}} b_{k}(T)ε^{k−e(T)}z^{k} = ∑_{k=0}^{∞} ∑_{T ∈T} \frac{1}{v(T)!}b_{k}(T)ε^{k−e(T)}z^{k}.

By symmetry, we can eliminate the factor 1/n! by only considering walks on T ∈ T_{n} such that the first visits to the vertices come in order 1, 2, …, n. Thus Ψ has integer coefficients.

If a term ε^{j}z^{k} appears in Ψ(ε, z) with non-zero coefficient, then j = k − e(T) for some tree with a walk of length k that uses every edge at least twice. Thus k ≥ 2e(T), so k/2 ≤ j ≤ k. We can thus regard Ψ(ε, z) as a power series in ε, with coefficients that are polynomials in z with integer coefficients. Note also that the constant term Ψ(0, z) = 1. It follows that there exists a unique power series Z(ε) such that

Z(ε)Ψ(ε, Z(ε)) = 1.  (4.1)

Z has integer coefficients and Z(0) = 1. Finally, define the formal power series

A(ε) = ∑_{k=0}^{∞} a_{k}ε^{k} := \frac{1}{Z(ε)}.  (4.2)

Note that each a_{k} is an integer and a_{0} = 1.

Proof of Lemma 3.1. A closed walk with k steps defines a connected graph F consisting of all vertices and edges in the walk. Since e(F) ≤ k, there is only a finite number of possible F (regarded as unlabelled graphs). The contribution to (np)^{−k} 𝔼 W_{k}(G_{n,p}) for a given unlabelled F is clearly

(np)^{−k}O(n^{v(F)}p^{e(F)}) = O(n^{v(F)−k}p^{e(F)−k}).  (4.3)

We consider three cases separately.

Case 1: F is a tree, v(F) = e(F) + 1.

Since a closed walk on a tree has to traverse each edge at least twice, we have 2e(F) ≤ k and thus the contribution is, by (4.3),

O(n^{v(F)−k}p^{e(F)−k}) = O(n(np)^{e(F)−k}) = O(n(np)^{−k/2}) = O(n^{−2})  (4.4)

because (np)^{k/2} ≥ (np)^{3/δ} ≫ n^{3}.

Case 2: F has more that one cycle, v(F) < e(F).

The contribution from F is by (4.3)

O(n^{−(e(F)−v(F))}(np)^{e(F)−k})

which is O(n^{−2}p^{−1}) except when v(F) = e(F) − 1 and e(F) = k. The latter case means that the edges of the walk are distinct but one vertex is repeated. Labelling the vertices v_{1}, …, v_{k}, we thus have v_{i} = v_{j} for two indices i and j, while the v_{i}’s otherwise are distinct. Moreover, 3 ≤ |i − j| ≤ k − 3 since each of the two cycles in F has at least 3 vertices. The indices i and j may thus be chosen in k(k − 5)/2 ways, and thus the contribution from such walks is

(np)^{−k} \frac{k(k − 5)}{2}(n)_{k−1}p^{k} = \frac{k(k − 5)}{2}n^{−1} + O(n^{−2}).

The total contribution from F with v(F) < e(F) is thus

\frac{k(k − 5)}{2}n^{−1} + O(n^{−2}p^{−1}).  (4.5)

Case 3: F is unicyclic, v(F) = e(F).

Then F consists of a cycle with attached trees. Given a closed walk on F traversing all edges, colour all edges of F that are traversed at least twice red and colour the remaining edges green. Each edge in the attached trees is red, while the edges in the cycle may be either red or green. Let l ≥ 0 be the number of green edges.

If there are l ≥ 1 green edges, the removal of them from F leaves l red components T_{1}, …, T_{l}. Each T_{l} is a tree (possibly a single vertex only) and v(F) = ∑_{i=1}^{l} v(T_{i}); moreover, the green edges join the red components into a cycle.

Fix l ≥ 3 and trees T_{1}, …, T_{l} (regarded as disjoint subgraphs of K_{n}), and consider together all F that are obtained by joining the trees by l edges, one from each T_{i} to T_{i+1} (and from T_{l} to T_{1}). A closed walk on one of these F with red subtrees T_{1}, …, T_{l}, that starts with the green edge leading from T_{l} to T_{1}, is called special. A special closed walk thus consists of a walk in each T_{i} that traverses each edge at least twice, together with single (green) steps linking the walks. The green links are determined by the walks in the trees, and thus the number of special walks with k_{i} steps inside T_{i}, i = 1, …, l, is ∏_{i=1}^{l} b_{k_{i}}(T_{i}); summing we find that the number of special walks with length k, for given T_{1}, …, T_{l}, is, with B(x; T) := ∑_{k=0}^{∞} x^{k}b_{k}(T) and using [x^{j}]f(x) to denote the coefficient of x^{j} in a power series f(x),

∑_{k_{1}+···+k_{l}=k−l} ∏_{i=1}^{l} b_{k_{i}}(T_{i}) = [x^{k−l}]B(x; T_{1}) ⋯ B(x; T_{l}).  (4.6)

Each of these walks uses ∑_{1}^{l} v(T_{i}) edges, so to get the contribution to (np)^{−k} 𝔼 W_{k}(G_{n,p}) we multiply by (np)^{−k}p^{∑ v(T_{i})}.

Summing first over all choices of T_{1}, …, T_{l} with given vertex sets and then over all ways to choose these vertex sets in {1, …, n} we obtain

\begin{matrix}(np)^{−k} ∑_{n_{1},...,n_{l}≥1} & \binom{n}{n_{1}, …, n_{l}} ∑_{T_{i}∈T_{n_{i}}}[x^{k−l}]B(x; T_{1}) ⋯ B(x; T_{l})p^{∑_{i} v(T_{i})} \\ = (np)^{−k}[x^{k−l}](∑_{T ∈T} \frac{B(x; T)}{v(T)!}(np)^{v(T)})^{l}(1 + O(\frac{1}{n})). \end{matrix}  (4.7)

This is, for a given l ≥ 3, the contribution from the walks that generate a unicyclic F with l red subgraphs, and that begin with a green edge. A walk generating such an F may be shifted (cyclically) in k ways by changing the starting point, and l of these shifts begin with a green edge; hence, the contribution from the walks that begin with a green edge is l/k times the total contribution for this F. Consequently, the contribution from all walks that generate a unicyclic F with l red subgraphs (for given l ≥ 3) is k/l times the value in (4.7).

If l < k, then v(T_{i}) > 1 for some i so F contains a red edge. This means that k > e(F) = v(F) = ∑_{i} v(T_{i}). Since each term in the sum in (4.7) then is

O((np)^{∑_{i} v(T_{i})−k}) = O((np)^{−1}),

the contribution of the term O(1/n) in (4.7) then is O((n^{2}p)^{−1}). Moreover,

∑_{T ∈T} \frac{B(x; T)}{v(T)!}(np)^{v(T)} = ∑_{k=1}^{∞} ∑_{T ∈T} \frac{b_{k}(T)x^{k}}{v(T)!} (np)^{e(T)+1} = npΨ(\frac{1}{np}, npx).

Hence we find from (4.7) that the contribution to (np)^{−k} 𝔼 W_{k}(G_{n,p}) from all walks that generate a unicyclic F with l red subtrees is, for 3 ≤ l < k,

\frac{k}{l} (np)^{−k}[x^{k−l}](np)^{l}Ψ(\frac{1}{np}, npx)^{l} + O((n^{2}p)^{−1}) = \frac{k}{l} [x^{k−l}]Ψ(\frac{1}{np}, x)^{l} + O((n^{2}p)^{−1}).

(4.8)

For l = k we are considering walks without repeated edges, i.e. cycles. Clearly, the contribution from them is

(np)^{−k}(n)_{k}p^{k} = 1 − \binom{k}{2}\frac{1}{n} + O(n^{−2}) = [x^{0}]Ψ(\frac{1}{np}, x)^{k} − \binom{k}{2}\frac{1}{n} + O(n^{−2}). (4.9)

For l ≤ 2, the formulas above are not quite correct. However, with l ≥ 0 green edges and thus e(F) − l red edges, we have k ≥ l + 2(e(F) − l) and thus e(F) ≤ (k + l)/2. If l ≤ 2 we thus have e(F) ≤ 1 + k/2, and by (4.3), the contribution from such F is, since k/2 ≥ 3/δ,

O((np)^{e(F)−k}) = O((np)^{1−k/2}) = O(n(np)^{−3/δ}) = O(n^{−2}).  (4.10)

Summing (4.4), (4.5), (4.8) for 3 ≤ l < k and (4.9), (4.10) we find

(np)^{−k} 𝔼 W_{k}(G_{n,p}) = ∑_{l=3}^{k} \frac{k}{l} [x^{k−l}]Ψ(\frac{1}{np}, x)^{l} − 2\frac{k}{n} + O(n^{−2}p^{−1}).

Lemma 3.1 now follows from the following algebraic lemma. □

Lemma 4.1. If J ≥ 0 and k ≥ m ≥ 2J, then

∑_{l=k−m}^{k} \frac{k}{l} [z^{k−l}]Ψ(ε, z)^{l} = (∑_{j=0}^{J} a_{j}ε^{j})^{k} + O (ε^{J+1}) .

Here and in the proof, O(ε^{a}), with a real, denotes a polynomial or power series in ε containing only powers ε^{j} with j ≥ a.

Proof. Define Φ_{ε} as the power series that solves the equation

Ψ(ε, z) = Φ_{ε}(zΨ(ε, z)).  (4.11)

Since Ψ(ε, 0) = 1, it is easily seen that Φ_{ε} exists and is unique; moreover, by an easy induction, each coefficient [z^{k}]Φ_{ε}(z) is a polynomial in ε with nonzero terms c_{j}ε^{j} for k/2 ≤ j ≤ k only, because Ψ is of this type. The same then is true for any power of Φ_{ε}(z).

By Lagrange’s inversion formula [7, Theorem 5.4.2], for 1 ≤ l ≤ k,

\frac{k}{l} [z^{k−l}]Ψ(ε, z)^{l} = \frac{k}{l} [z^{k}](zΨ(ε, z))^{l} = [u^{k−l}]Φ_{ε}(u)^{k}.

This is a polynomial in ε and is O(ε^{(k−l)/2}). Hence,

∑_{l=k−m}^{k} \frac{k}{l} [z^{k−l}]Ψ(ε, z)^{l} = ∑_{j=0}^{m}[u^{j}]Φ_{ε}(u)^{k} = ∑_{j=0}^{∞}[u^{j}]Φ_{ε}^{k}(u) + O (ε^{(m+1)/2}) ,

where the infinite sum is well defined as a power series in ε. This sum of all coefficients of Φ_{ε}^{k} is

Φ_{ε}^{k}(1) = Φ_{ε}(1)^{k}

and, substituting (4.1) in (4.11) and using (4.1) and (4.2),

Φ_{ε}(1) = Φ_{ε}(Z(ε)Ψ(ε, Z(ε))) = Ψ(ε, Z(ε)) = \frac{1}{Z(ε)} = A(ε).

(These manipulations are easily justified modulo ε^{N} for any fixed N.) The lemma follows. □

5. Proof of Lemma 3.2

It is easily seen from the discussion if Section 3 that ŵ_{k}(n, p; H) can be computed as follows. Fix a copy H_{0} of H in K_{n} and consider the set W of closed walks of length k in K_{n} that use every edge in H_{0} at least once. If γ ∈ W, let γ̄ denote its trace, i.e. the subgraph of K_{n} consisting of the edges and vertices in γ. Then

ŵ_{k}(n, p; H) = \frac{1}{aut(H)} ∑_{γ∈W} p^{e(γ̄)−e(H)}.  (5.1)

Let c = c(H) be the number of components of H, and note that v(H) ≤ c + e(H).

Fix j ≥ 0 and consider the closed walks γ in this sum that pass through j vertices outside H_{0}. Clearly, the number of such γ is O(n^{j}).

Since γ̄ connects the j vertices outside H_{0} and the c components of H_{0}, it has at least j + c − 1 edges outside H_{0}, i.e.

e(γ̄) − e(H) ≥ j + c − 1.

Case 1: e(γ̄) − e(H) = j + c − 1.

In this case, if we collapse each component of H_{0} to a single point, γ̄ becomes a connected graph with j + c vertices and j + c − 1 edges, i.e. a tree. The closed walk γ has to traverse each edge in this tree an even number of times, and thus

k ≥ 2(j + c − 1) + e(H).

The contribution to (np)^{−k}ŵ_{k}(n, p; H) from all γ in Case 1 is thus, using (5.1),

O ((np)^{−k}n^{j}p^{j+c−1}) = O ((np)^{−k/2}n^{1−c−e(H)/2}p^{−e(H)/2})
= o (n^{−kδ/2+1−c/2−v(H)/2}p^{−e(H)/2})
= o (n^{−3/2−v(H)/2}p^{−e(H)/2}) .

This is covered by the o term in the lemma.

Case 2: e(γ̄) − e(H) ≥ j + c.

Then k ≥ e(γ̄) ≥ j + c + e(H). The contribution to (np)^{−k}ŵ_{k}(n, p; H) is, using (5.1),

\begin{aligned}O ((np)^{−k}n^{j}p^{j+c}) & = O (n^{−c−e(H)}p^{−e(H)}) \\ & = O ((np)^{−e(H)/2}n^{−c/2−v(H)/2}p^{−e(H)/2}) . \end{aligned}  (5.2)

If e(H) ≥ 3, or if e(H) = 2 and c > 1, this is o (n^{−3/2}p^{−1}n^{−v(H)/2}p^{−e(H)/2}), which verifies the lemma for these H, i.e. all H except K_{2} and P_{2}.

For H = P_{2}, the calculation in (5.2) yields O (n^{−3}p^{−2}), and o (n^{−3}p^{−2}) unless k = e(γ̄) = j + c + e(H) = j + 3. We thus only have to consider γ that go through k different vertices, i.e. cycles of length k. The number of such cycles passing through H_{0} is 2k(n)_{k}/(n)_{3}, since there are (n)_{k}/(n)_{3} choices of the cycle γ̄, and for each γ̄, γ may start at k places and in 2 directions. Thus, (5.1) yields

(np)^{−k}ŵ_{k}(n, p; P_{2}) = (np)^{−k} \frac{k(n)_{k}}{(n)_{3}} p^{k−2} + o (n^{−3}p^{−2}) = kn^{−3}p^{−2} + o (n^{−3}p^{−2}) .

Finally, for H = K_{2}, (5.2) yields O (n^{−2}p^{−1}), and again we have o unless k = e(γ̄) = j + c + e(H) = j + v(H). Thus, again, we only have to consider γ that go through k different vertices, i.e. cycles of length k. Arguing as for P_{2} we find that the number of such cycles passing through H_{0} is 2k(n)_{k}/(n)_{2}, and

(np)^{−k}ŵ_{k}(n, p; K_{2}) = (np)^{−k} \frac{k(n)_{k}}{(n)_{2}} p^{k−1} + o (n^{−2}p^{−1}) = kn^{−2}p^{−1} + o (n^{−2}p^{−1}) .

□

References

[1] N. Alon, M. Krivelevich & V. H. Vu, On the concentration of eigenvalues of random symmetric matrices. Israel J. Math. 131 (2002), 259–267.

[2] Z. Füredi & J. Komlós, The eigenvalues of random symmetric matrices. Combinatorica 1 (1981), no. 3, 233–241.

[3] S. Janson, Orthogonal Decompositions and Functional Limit Theorems for Random Graph Statistics. Mem. Amer. Math. Soc., vol. 111, no. 534, American Mathematical Society, Providence, R.I., 1994.

[4] S. Janson, T. Łuczak, A. Ruciński, Random Graphs. John Wiley & Sons, New York, 2000.

[5] O. Kallenberg, Foundations of Modern Probability, 2nd ed., Springer, New York, 2002.

[6] M. Krivelevich & B. Sudakov, The largest eigenvalue of sparse random graphs. Combin. Probab. Comput. 12 (2003), 61–72.

[7] R.P. Stanley, Enumerative Combinatorics, Volume 2. Cambridge Univ. Press, 1999.

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

   E-mail address: svante.janson@math.uu.se
   URL: http://www.math.uu.se/~svante/