GROWTH OF COMPONENTS IN RANDOM GRAPHS

SVANTE JANSON

Abstract. The creation and growth of components of a given complexity in a random graph process are studied. In particular, the expected number and total size of all such components is found. It follows that the largest ℓ-component during the process is O_{p}(n^{2/3}) for any given ℓ. The results also yield a new proof of the asymptotic behaviour of Wright’s coefficients.

1. Introduction

We consider the growth of size and complexity of the components of a random graph process \{G(n, m)\}_{0≤m≤\binom{n}{2}} or \{G(n, t)\}_{0≤t≤1}. Recall that both processes describe a randomly growing graph on n vertices, where edges are added one by one, and where each new edge is chosen uniformly at random among all remaining possibilities. The only difference between the two processes is that in {G(n, m)}, the edges are added at the fixed times 1,2,…, so at time m we have the random graph G(n, m) with m edges, while in {G(n, t)} the edges are added at random times in such a way that at time t = p, we have the random graph G(n, p). ({G(n, t)} may be constructed by letting each edge e in the complete graph K_{n} appear at a random time T_{e}, with T_{e} independent and uniformly distributed on (0, 1), and letting G(n, t) contain the edges that have appeared before t.)

In this paper, we will study random variables that depend on the order the edges appear in the process, but not on the time scale. All such variables will thus have the same distribution for both processes (not only asymptotically, but also for each finite n). Hence all results below are valid for both processes.

We define the complexity of a connected graph to be its number of edges minus its number of vertices. A component of a graph of complexity ℓ is called an ℓ-component. Here ℓ ≥ −1; a (−1)-component is a tree, a 0-component is unicyclic, and ℓ-components with ℓ ≥ 1 are known as complex components.

In the beginning of the random graph process, there are no edges at all, and thus n components of order 1 and complexity −1; at the end, we have the complete graph, with a single component of complexity \binom{n}{2}−n. Several authors have studied what happens in between, see e.g. [4, 9, 6, 7, 11, 8]. We will here add some results obtained by studying, as in [6], the ways ℓ-components are created.

Each time a new edge is added, there are two possibilities:

Date: January 26, 2000; revised June 15, 2000.

This is a preprint of an article published in Random Structure & Algoritms 17 (2000), no. 3-4, 343-356. \begin{matrix}c \\ ◯ \end{matrix} John Wiley & Sons, Inc.

(i) The edge joins two vertices already in the same component. The number of components and their orders remain the same, but if the edge was added to an ℓ-component, it becomes an (ℓ + 1)-component. We call this a transition ℓ → ℓ + 1.

(ii) The edge joins two vertices in different components. If these have complexities ℓ_{1} and ℓ_{2}, they will merge to an (ℓ_{1} + ℓ_{2} + 1)-component. We call this a transition ℓ_{1} ⊕ ℓ_{2} → ℓ_{1} + ℓ_{2} + 1.

We say that an ℓ-component is created by a transition ℓ − 1 → ℓ or ℓ_{1} ⊕ ℓ_{2} → ℓ with ℓ_{1}, ℓ_{2} ≥ 0; in contrast, we say (for ℓ ≥ 0) that an ℓ-component grows when it swallows a tree by a transition ℓ ⊕ −1 → ℓ.

We can regard the ℓ-components that appear in the random graph process {G(n, m)} (or, similarly, {G(n, t)}) in two ways:

The static view: Let C_{ℓ}(m) denote the collection of all ℓ-components in G(n, m), and consider the family C_{ℓ}^{∗} = ⋃_{m} C_{ℓ}(m) of every ℓ-component that appears at some stage of the process, ignoring when it appears. We sometimes, for emphasis, call the elements of C_{ℓ}^{∗} static ℓ-components. The dynamic view: For ℓ ≥ 0, we can regard a component as “the same” even after it has grown by merging with a tree. In other words, we identify any two elements of C_{ℓ}^{∗} such that one is contained in the other, and regard the ℓ-components in the random graph process as functions of time; these time-dependent subgraphs of K_{n} are called dynamic ℓcomponents. Each dynamic component thus exists during some time interval, in which it is created, grows, and disappears. In particular, a dynamic component does not have a fixed size.

The maximal elements of C_{ℓ}^{∗} (with respect to inclusion) are called maximal ℓ-components. Note that for ℓ ≥ 0, the maximal ℓ-components are in one-to-one correspondence with the dynamic ℓ-components; they are the final forms of the dynamic components before disappearing. For any ℓ, the maximal ℓcomponents are disjoint, their vertex sets form a partition of the set V_{ℓ} = ⋃{V (C) : C ∈ C_{ℓ}^{∗}} of every vertex that belongs to an ℓ-component at some stage of the random graph process, and every static ℓ-component is a subgraph of some maximal ℓ-component.

We further define V_{ℓ} = |V_{ℓ}|, the number of vertices that at some time belong to an ℓ-component, and V_{ℓ}^{max} = max{|V (C)| : C ∈ C_{ℓ}^{∗}}, the order of the largest ℓ-component that ever appears. Note that, trivially, V_{ℓ}^{max} ≤ V_{ℓ}, and that for any m or t, each ℓ-component in G(n, m) or G(n, t) has at most V_{ℓ}^{max} vertices, while the union of all ℓ-components has at most V_{ℓ} vertices.

Let α(ℓ; k) be the expected number of times that a new edge is added to an ℓcomponent of order k, with both ends of the edge in the component. Similarly let β(ℓ_{1}, ℓ_{2}; k_{1}, k_{2}) be the expected number of ordered pairs (H_{1}, H_{2}) such that H_{1} and H_{2} are two distinct components at some stage of the process, which are joined by the next edge, and such that H_{i} has k_{i} vertices and complexity ℓ_{i}. (Note that, by considering ordered pairs, every edge joining two components is counted twice.)

Our results are based on an evaluation of these expected numbers in Lemma 1 below (Section 2). In the following sections we apply Lemma 1 to, respectively, complex components, unicyclic components, tree components, and complex components again. For example, we show that for any fixed ℓ ≥ −1, the largest ℓ-component that appears during the evolution is of order O_{p}(n^{2/3}). (See e.g. [8] for the definition of O_{p} and o_{p}.) In particular, this holds for tree components and unicyclic components, which extends the well-known result that for any given m = m(n) or p = p(n), the maximal order of such components in G(n, m) or G(n, p) is O_{p}(n^{2/3}).

Remark 1. In this paper we study only the expectations of various random variables. In principle, it is possible to compute variances and higher moments too; see [6], where this is done for the special case ℓ = 0. Such calculations might perhaps be used to show that some of the random variables studied below are concentrated about their means (as we conjecture), but we have not attempted this.

Remark 2. Although we will not do it in this paper, it is possible to study also when the transitions occur in the random graph process by keeping track of the time t in the estimates above, instead of immediately integrating over all t. Again, see [6], where this is done for ℓ = 0.

Remark 3. It might be possible to make a similar study of the disappearance of components of a given complexity, but so far we have not succeeded to deduce anything useful.

2. The expected number of transitions

Let C(k, k + ℓ) denote the number of connected graphs with k + ℓ edges on k labelled vertices. Then C(k, k − 1) = k^{k−2} (Cayley’s formula for the number of labelled trees); more generally, by Wright [13], see also [7, 12], for any fixed ℓ ≥ −1, there exists a constant ρ_{ℓ} such that

C(k, k + ℓ) = ρ_{ℓ}k^{k−1/2+3ℓ/2}(1 + O(k^{−1/2})).  (1)

In particular, ρ_{−1} = 1, ρ_{0} = \sqrt{π/8} and ρ_{1} = 5/24.

We can now state our basic result. We use n\underline{k} to denote the falling factorial n(n − 1) ⋯ (n − k + 1).

Lemma 1. For any ℓ ≥ −1 and k ≥ 1,

α(ℓ; k) = n\underline{k} \frac{(k + ℓ)!}{k!}C(k, k + ℓ) (\binom{k}{2} − k − ℓ) \frac{(nk − k^{2}/2 − 3k/2 − ℓ − 1)!}{(nk − k^{2}/2 − k/2)!},

(2)

and for any k_{1}, k_{2}, ℓ_{1}, ℓ_{2}, with k = k_{1} + k_{2} and ℓ = ℓ_{1} + ℓ_{2},

β(ℓ_{1}, ℓ_{2}; k_{1}, k_{2})

= n\underline{k}(k + ℓ)!\frac{k_{1}C(k_{1}, k_{1} + ℓ_{1})}{k_{1}!} \frac{k_{2}C(k_{2}, k_{2} + ℓ_{2})}{k_{2}!} \frac{(nk − k^{2}/2 − 3k/2 − ℓ − 1)!}{(nk − k^{2}/2 − k/2)!}.(3)

Moreover, for fixed ℓ, and all k and n with 1 ≤ k ≤ n,

α(ℓ; k) = \frac{1}{2}ρ_{ℓ}k^{(3ℓ+1)/2}n^{−ℓ−1}e^{−k^{3}/24n^{2}}(1 + O(\frac{k}{n} + \frac{k^{4}}{n^{3}} + k^{−1/2})),  (4)

and if further k_{1}, k_{2} ≥ 1, ℓ_{1}, ℓ_{2} ≥ −1, k_{1} + k_{2} = k and ℓ_{1} + ℓ_{2} = ℓ,

\begin{aligned}β(ℓ_{1}, ℓ_{2}; k_{1}, k_{2}) & = \frac{1}{\sqrt{2π}}ρ_{ℓ_{1}}ρ_{ℓ_{2}}k_{1}^{3ℓ_{1}/2}k_{2}^{3ℓ_{2}/2}k^{−1/2}n^{−ℓ−1}e^{−k^{3}/24n^{2}} \\ & · (1 + O(\frac{k}{n} + \frac{k^{4}}{n^{3}} + k_{1}^{−1/2} + k_{2}^{−1/2})), \end{aligned}  (5)

and also

\begin{aligned}β(ℓ_{1}, −1; k_{1}, k_{2}) & = ρ_{ℓ_{1}}k_{1}^{3ℓ_{1}/2} \frac{k_{2}^{k_{2}−1}e^{−k_{2}}}{k_{2}!} k^{−1/2}n^{−ℓ_{1}}e^{−k^{3}/24n^{2}} \\ & · (1 + O(\frac{k}{n} + \frac{k^{4}}{n^{3}} + k_{1}^{−1/2})). \end{aligned}  (6)

Proof. We do the calculations for G(n, t), which is more convenient. Similar calculations can be performed for G(n, m), leading to sums of terms including several binomial coefficients. By the equivalence discussed above, these sums must equal the values in (2) and (3), although it seems difficult to show this directly. (Perhaps, the Gosper–Zeilberger algorithm [5, Section 5.8] can be used, but we have not tried it.) Asymptotic results are easily derived using these sums too.

For a transition ℓ → ℓ + 1 when a new edge is added to an ℓ-component of order k, there are \binom{n}{k}C(k, k +ℓ) possible ℓ-components and \binom{k}{2}−k −ℓ possible edges to add; moreover, the probability that a given one of these possible ℓcomponents actually is a component of G(n, t) is t^{k+ℓ}(1 − t)^{(n−k)k+\binom{k}{2}−k−ℓ}, and the conditional probability that a given edge, not in this component, is added in the time interval (t, t + dt), given that it was not added earlier, is dt/(1 − t). Hence, we obtain, integrating over all times,

α(ℓ; k) = \binom{n}{k}C(k, k + ℓ) (\binom{k}{2} − k − ℓ) ∫_{0}^{1} t^{k+ℓ}(1 − t)^{(n−k)k+\binom{k}{2}−k−ℓ−1} dt.

We obtain (2) by evaluating the beta integral.

Similarly, with k = k_{1} + k_{2} and ℓ = ℓ_{1} + ℓ_{2}, since there are k_{1}k_{2} ways to join two given components of orders k_{1} and k_{2},

\begin{aligned}β(ℓ_{1}, ℓ_{2}; k_{1}, k_{2}) & = \binom{n}{k}\binom{k}{k_{1}}C(k_{1}, k_{1} + ℓ_{1})C(k_{2}, k_{2} + ℓ_{2})k_{1}k_{2} \\ & · ∫_{0}^{1} t^{k+ℓ}(1 − t)^{(n−k)k+\binom{k}{2}−k−ℓ−1} dt, \end{aligned}

which yields (3).

For the asymptotical results we observe that, for fixed ℓ and k ≤ n,

k(n − k/2) ≥ nk − k^{2}/2 − k/2 ≥ nk − k^{2}/2 − 3k/2 − ℓ − 1

= k(n − k/2 + O(1)) = k(n − k/2)(1 + O(\frac{1}{n}))

and thus

\begin{aligned}\frac{(nk − k^{2}/2 − 3k/2 − ℓ − 1)!}{(nk − k^{2}/2 − k/2)!} & = \frac{1}{(nk − k^{2}/2 − k/2)\underline{k+ℓ+1}} \\ & = k^{−k−ℓ−1}(n − k/2)^{−k−ℓ−1}(1 + O(\frac{k}{n})). \end{aligned} (7)

Moreover, we claim that for 1 ≤ k ≤ n,

\frac{n\underline{k}}{(n − k/2)^{k}} = e^{−k^{3}/24n^{2}}(1 + O(\frac{k}{n} + \frac{k^{4}}{n^{3}} )).  (8)

Indeed, if k ≤ n^{3/4}, then, by Taylor expansions,

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

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

and

log(n − k/2)^{k} = k log n + k log(1 − k/2n) = k log n − \frac{k^{2}}{2n} − \frac{k^{3}}{8n^{2}} + O(\frac{k^{4}}{n^{3}} ),

which imply (8).

On the other hand, if n^{3/4} ≤ k ≤ n, then

0 ≤ \frac{n\underline{k}}{(n − k/2)^{k}} ≤ 2 ∏_{i=1}^{k−1} \frac{n − i}{n − k/2} = 2 ∏_{i=1}^{k/2} \frac{(n − i)(n − (k − i))}{(n − k/2)^{2}}

= 2 ∏_{i=1}^{k/2} (1 − \frac{(i − k/2)^{2}}{(n − k/2)^{2}} ) ≤ 2 exp (− ∑_{i=1}^{k/2} \frac{(i − k/2)^{2}}{(n − k/2)^{2}} )

= 2 exp (−\frac{(k/2)^{3}}{3(n − k/2)^{2}} + O(\frac{k^{2}}{n^{2}} )) ≤ exp(−\frac{k^{3}}{24n^{2}} + O(1)),

and again (8) follows (since now k^{4}/n^{3} ≥ 1).

Combining (2), (7), (8) and (1), we obtain (4). Similarly, from (3), (7), (8),

(1) and Stirling’s formula we obtain (5) and (6) (for the latter using Cayley’s formula for C(k_{2}, k_{2} − 1) instead of (1)). □

When using Lemma 1, we will frequently find use for the following simple asymptotic formulas.

Lemma 2.

(i) If a > −1, then

∑_{1}^{n} k^{a}e^{−k^{3}/24n^{2}} ∼ 2^{a+1}3^{(a−2)/3}Γ(\frac{a + 1}{3})n^{2(a+1)/3}

as n → ∞.

(ii) If a, b > −1, then

∑_{\begin{matrix}k_{1}+k_{2}=k \\ k_{1},k_{2}≥1 \end{matrix}} k_{1}^{a}k_{2}^{b} ∼ \frac{Γ(a + 1)Γ(b + 1)}{Γ(a + b + 2)}k^{a+b+1}

as k → ∞.

Proof. For (i) it is easily checked that

\begin{aligned}∑_{1}^{n} k^{a}e^{−k^{3}/24n^{2}} & ∼ ∫_{0}^{n} x^{a}e^{−x^{3}/24n^{2}} dx = n^{2(a+1)/3} ∫_{0}^{n^{1/3}} y^{a}e^{−y^{3}/24} dy \\ & ∼ n^{2(a+1)/3} ∫_{0}^{∞} y^{a+1}e^{−y^{3}/24} \frac{dy}{y} , \end{aligned}

where the final integral equals, by the substitution y = (24z)^{1/3},

∫_{0}^{∞}(24z)^{(a+1)/3}e^{−z} \frac{dz}{3z} = (24)^{(a+1)/3}3^{−1}Γ((a + 1)/3).

For (ii), similarly,

\begin{aligned}∑_{\begin{matrix}k_{1}+k_{2}=k \\ k_{1},k_{2}≥1 \end{matrix}} k_{1}^{a}k_{2}^{b} & = ∑_{k_{1}=1}^{k−1} k_{1}^{a}(k − k_{1})^{b} ∼ ∫_{0}^{k} x^{a}(k − x)^{b} dx \\ & = k^{a+b+1} ∫_{0}^{1} x^{a}(1 − x)^{b} dx = \frac{Γ(a + 1)Γ(b + 1)}{Γ(a + b + 2)}k^{a+b+1}. \end{aligned} □

3. Creation of complex components

It was observed in [6] that a complex component must be created first as a 1-component, i.e. through a transition 0 → 1 or 0 ⊕ 0 → 1, and the expected numbers of such transitions were calculated (by the same method as here). As a warm-up, we rederive this result using Lemma 1.

Indeed, (4) implies by four applications of Lemma 2(i), recalling ρ_{0} = \sqrt{π/8}, that the expected numbers of transitions 0 → 1 is

∑_{k=1}^{n} α(0; k) = \frac{1}{2}ρ_{0}n^{−1} ∑_{k=1}^{n}(k^{1/2} + O(\frac{k^{3/2}}{n} + \frac{k^{9/2}}{n^{3}} + 1))e^{−k^{3}/24n^{2}}

= \frac{1}{2}ρ_{0}2^{3/2}3^{−1/2}Γ(1/2)(1 + o(1)) + O(n^{5/3−2}) + O(n^{11/3−4})

+ O(n^{2/3−1})

= \frac{π}{2\sqrt{3}} + o(1).

Similarly, the expected numbers of transitions 0⊕0 → 1 is, with the factor 1/2 since β counts ordered pairs, by (5) and several applications of Lemma 2(i),(ii)

(we leave the details to the reader)

\frac{1}{2} ∑_{k_{1},k_{2}=1}^{n} β(0, 0; k_{1}, k_{2}) ∼ \frac{1}{2}(\frac{1}{2π} )^{1/2} \frac{π}{8} ∑_{k=2}^{n} k^{1/2}n^{−1}e^{−k^{3}/24n^{2}} ∼ \frac{π}{8\sqrt{3}}.

Adding these numbers together, we obtain that the expected number of creations of complex components converges to 5π/8\sqrt{3} ≈ 1.134.

Remark 4. By studying higher moments, it was in [6] further deduced that the probability that the random graph process never has more than one complex component converges to a limit strictly between 0 and 1; this limit was shown to equal 5π/18 in [7].

4. Unicyclic components

Unicyclic components are created by the transition −1 → 0 and grow further by 0 ⊕ −1 → 0.

Unlike the creation of 1-components studied in the preceding section, the number of transitions −1 → 0 is large; it follows from Lemma 1 (and Lemma 2 for the error terms), that its expectation is

∑_{k=1}^{n} α(−1; k) ∼ \frac{1}{2} ∑_{k=1}^{n} k^{−1}e^{−k^{3}/24n^{2}} ∼ \frac{1}{2} ∫_{1}^{n} \frac{1}{x}e^{−x^{3}/24n^{2}}dx.

To estimate this integral, we write it as

∫_{1}^{n^{2/3}} (\frac{1}{x} + O(\frac{x^{2}}{n^{2}} )) dx + ∫_{1}^{n^{1/3}} e^{−y^{3}/24} \frac{dy}{y} = log n^{2/3} + O(1) + O(1),

and thus the expected number of creations is ∼ \frac{1}{3} log n. Hence, on the average, a random graph process has about \frac{1}{3} log n different dynamic unicyclic components during the evolution (and thus about \frac{1}{3} log n maximal unicyclic components in the static view). Equivalently, there are at the end about \frac{1}{3} log n cycles that at some time have belonged to unicyclic components. (We believe that these random numbers are concentrated about their mean, i.e. that they are (\frac{1}{3} + o_{p}(1)) log n, but we have not attempted to verify this.)

It can easily be verified by calculations similar to those in [8, Section 5.3] that the average number of unicyclic components in G(n, n/2) or G(n, 1/n) is ∼ \frac{1}{6} log n; moreover the actual random number is (\frac{1}{6} + o_{p}(1)) log n, so it is concentrated about its mean (for example by using Corollary 4 below to show that unicyclic components of size larger than n^{2/3}/ log log n are too few to matter, and then estimating the variance of the number of smaller unicyclic components). Hence, roughly 1/2 of all (dynamic) unicyclic components that appear during the evolution exist at m = n/2 (or at p = 1/n). (I’m grateful to a referee for pointing out an error in a previous version of the present paper.)

Remark 5. The number of cycles in complex components in G(n, n/2) (or G(n, 1/n)) is O_{p}(1) (see [8, Theorem 5.19]) and thus the total number of cycles is (\frac{1}{6} +o_{p}(1)) log n too. On the other hand, it is also easily checked that the average number of cycles is ∼ \frac{1}{4} log n. In other words, the number of cycles in G(n, n/2) or G(n, 1/n) is concentrated at \frac{1}{6} log n, which is only (asymptotically) 2/3 of the average. (The reason is of course that there is a small probability of having a component with very many cycles.) This is a striking example of the well-known fact that the average can be misleading.

The number of transitions 0 ⊕ −1 → 0 when the unicyclic components grow is much larger; its expectation is, by Lemmas 1 and 2 as above (now using (6)) and the well-known formula ∑_{1}^{∞} k^{k−1}e^{−k}/k! = 1,

\begin{aligned}∑_{k_{1},k_{2}} β(0, −1; k_{1}, k_{2}) & ∼ \sqrt{\frac{π}{8}} ∑_{k=1}^{n} ∑_{k_{2}=1}^{k−1} \frac{k_{2}^{k_{2}−1}e^{−k_{2}}}{k_{2}!} k^{−1/2}e^{−k^{3}/24n^{2}} \\ & ∼ \sqrt{\frac{π}{8}} ∑_{k=1}^{n} k^{−1/2}e^{−k^{3}/24n^{2}} \\ & ∼ 2^{−1}3^{−5/6}π^{1/2}Γ(1/6)n^{1/3}. \end{aligned}  (9)

Summarizing, we have:

Theorem 1. The expected number of dynamic 0-components is ∼ \frac{1}{3} log n.

The expected number of static 0-components is ∼ 2^{−1}3^{−5/6}π^{1/2}Γ(1/6)n^{1/3} ≈ 1.975 n^{1/3}. □

Next, we study V_{0} = |V_{0}|, the number of vertices that ever belong to unicyclic components. The expected number of vertices added to V_{0} by creations of unicyclic components (transitions 0 → 1) is, by Lemmas 1 and 2,

∑_{k=1}^{n} kα(−1; k) ∼ \frac{1}{2} ∑_{k=1}^{n} e^{−k^{3}/24n^{2}} ∼ 3^{−2/3}Γ(\frac{1}{3})n^{2/3},

and the expected number of vertices added to already existing unicyclic components (by transitions 0 ⊕ −1 → 0) is

\begin{aligned}∑_{k_{1},k_{2}} k_{2}β(0, −1; k_{1}, k_{2}) & ∼ \frac{1}{\sqrt{2π}} \sqrt{\frac{π}{8}} ∑_{k=1}^{n} ∑_{k_{2}=1}^{k−1} k_{2}^{−1/2}k^{−1/2}e^{−k^{3}/24n^{2}} \\ & ∼ \frac{1}{4} ∑_{k=1}^{n} 2e^{−k^{3}/24n^{2}} ∼ 3^{−2/3}Γ(1/3)n^{2/3}. \end{aligned}

Both types of transitions thus asymptotically contributes the same number of vertices, and by summing we obtain:

Theorem 2.

𝔼 V_{0} ∼ 2 · 3^{−2/3}Γ(1/3)n^{2/3} ≈ 2.576 n^{2/3}.  □

Since V_{0} majorizes both V_{0}^{max} and the total order of the unicyclic components at any given stage of the process, we obtain immediate corollaries.

Corollary 3. For any C > 2 · 3^{−2/3}Γ(1/3) and large enough n,

𝔼 V_{0}^{max} ≤ Cn^{2/3}.

Thus the largest unicyclic component during the evolution has order O_{p}(n^{2/3}). □

Corollary 4. For any given m = m(n) or p = p(n), let Ṽ_{0} be the total size of the unicyclic components in G(n, m) or G(n, p). Then, for any C > 2 · 3^{−2/3}Γ(1/3) and large enough n,

𝔼 Ṽ_{0} ≤ Cn^{2/3}.  □

For m = n/2 or p = 1/n,

𝔼 Ṽ_{0} ∼ \frac{6^{1/3}Γ(1/3)}{12}n^{2/3} = 2^{−5/3}3^{−2/3}Γ(1/3)n^{2/3}

[4, Theorem V.23], that is, by Theorem 2,

𝔼 Ṽ_{0} ∼ 2^{−8/3} 𝔼 V_{0}.

Thus, on the average, 2^{−8/3} ≈ 0.157 of the vertices that at some stage of the random graph process belongs to a unicyclic component, do so when m = n/2. (The random variables V_{0} and Ṽ_{0} are not concentrated in the above sense, which follows e.g. from the results in [1] or [10, Theorem 9]. In view of the latter results, it seems highly likely that n^{−2/3}V_{0} has an asymptotic distribution, but unlikely that it has a simple form.)

5. Tree components

We cannot estimate the size of the maximal tree components by the method of the previous section, since each vertex belongs to a tree at the beginning of the process and thus V_{−1} = |V_{−1}| = n. Instead, let W_{−1} be the number of unordered pairs of vertices {x, y} such that x and y belong to the same tree component at some stage of the process; equivalently, W_{−1} is the number of pairs {x, y} such that x and y belong to the same maximal tree component. Hence, if the maximal tree components are T_{1},…,T_{N},

W_{−1} = ∑_{i} \binom{|T_{i}|}{2}.  (10)

Theorem 5.

𝔼 W_{−1} ∼ 2^{−1}3^{−5/6}π^{1/2}Γ(1/6)n^{4/3} ≈ 1.975 n^{4/3}.

Proof. The number of pairs {x, y} in the same tree is 0 at the beginning of the process, and increases by k_{1}k_{2} each time two tree components of orders k_{1} and k_{2} merge. Consequently, again with the symmetry factor 1/2,

\begin{aligned}𝔼 W_{−1} & = \frac{1}{2} ∑_{k_{1},k_{2}} k_{1}k_{2}β(−1, −1; k_{1}, k_{2}) \\ & ∼ \frac{1}{2} ∑_{k_{1},k_{2}} \frac{1}{\sqrt{2π}} k_{1}^{−1/2}k_{2}^{−1/2}k^{−1/2}ne^{−k^{3}/24n^{2}} \\ & ∼ \frac{π}{2\sqrt{2π}} n ∑_{k=2}^{n} k^{−1/2}e^{−k^{3}/24n^{2}} \\ & ∼ (\frac{π}{8} )^{1/2}2^{1/2}3^{−5/6}Γ(1/6)n^{1+1/3}. \end{aligned}  □

By (10), (V_{−1}^{max})^{2} ≤ 2W_{−1} + n. Consequently, we can now estimate the size of the largest tree component.

Corollary 6. At least for large enough n,

𝔼(V_{−1}^{max})^{2} ≤ 4n^{4/3}

and thus 𝔼 V_{−1}^{max} ≤ 2n^{2/3}. In particular, V_{−1}^{max} = O_{p}(n^{2/3}). □

Remark 6. We can similarly consider, for any j ≥ 2,

W_{−1}^{(j)} = ∑_{i} \binom{|T_{i}|}{j},

the number of j-tuples of vertices that at some stage belong to the same tree component, cf. (10). The argument above extends to

𝔼 V_{−1}^{(j)} ∼ C_{−1}^{(j)}n^{2j/3}

for every j ≥ 2 and some constants

C_{−1}^{(j)} = 2^{j−3}3^{j/3−3/2}π^{−1/2} \frac{Γ(j/3 − 1/2)}{Γ(j − 1)} ∑_{i=1}^{j−1} \frac{Γ(i − 1/2)Γ(j − i − 1/2)}{i! (j − i)!}.

In particular, this implies that all moments of n^{−2/3}V_{−1}^{max} are bounded. We omit the details.

Moreover, similar results hold for ℓ-components for any ℓ ≥ 0 too (and any j ≥ 1). Again, we leave the details to the reader; note that j = 1 gives V_{ℓ} treated in the next section.

6. Higher complexities

In this final section, we study creations of components of higher complexity. Let, for ℓ ≥ 1, U′_{ℓ} be the number of creations by transitions ℓ − 1 → ℓ, and U′′_{ℓ} the number of creations by transitions ℓ_{1} ⊕ ℓ_{2} → ℓ for some ℓ_{1}, ℓ_{2} ≥ 0 (i.e. mergers of two cyclic components). Furthermore, let U_{ℓ} = U′_{ℓ} +U′′_{ℓ} be the total number of creations of ℓ-components, i.e. the number of dynamic ℓ-components in the random graph process. We begin by computing the expectations.

Theorem 7. Let ℓ ≥ 1. Then, as n → ∞,

𝔼 U′_{ℓ} → u′_{ℓ} = 2^{3ℓ/2−1}3^{ℓ/2−1}ρ_{ℓ−1}Γ(ℓ/2),
𝔼 U′′_{ℓ} → u′′_{ℓ} = 2^{3ℓ/2−1/2}3^{ℓ/2−1}π^{−1/2} \frac{Γ(ℓ/2)}{Γ(3ℓ/2 + 1/2)}

· \frac{1}{2} ∑_{m=0}^{ℓ−1} ρ_{m}ρ_{ℓ−m−1}Γ(3m/2 + 1)Γ(3(ℓ − m − 1)/2 + 1)

and thus 𝔼 U_{ℓ} → u′_{ℓ} + u′′_{ℓ}.

Proof. We argue as for the special case ℓ = 1 in Section 3. First, by Lemmas 1 and 2,

\begin{aligned}𝔼 U′_{ℓ} & = ∑_{k=1}^{n} α(ℓ − 1; k) ∼ \frac{1}{2}ρ_{ℓ−1}n^{−ℓ} ∑_{k=1}^{n} k^{3ℓ/2−1}e^{−k^{3}/24n^{2}} \\ & ∼ 2^{3ℓ/2−1}3^{ℓ/2−1}ρ_{ℓ−1}Γ(ℓ/2). \end{aligned}

Secondly,

𝔼 U′′_{ℓ} = \frac{1}{2} ∑_{m=0}^{ℓ−1} ∑_{k_{1},k_{2}} β(m, ℓ − m − 1; k_{1}, k_{2}),

which by a similar computation yields the second formula. □

While the limits in Theorem 7 can be evaluated for any given ℓ, they are not very illuminating as they stand, but we can connect them to well-known properties of the evolution of random graphs.

Note first that, as a consequence of [7, Theorem 16], each U_{ℓ} converges in distribution to some random variable Y_{ℓ}, whose support is {1, 2, … } for ℓ = 1 and {0, 1, 2, … } for ℓ ≥ 2. Furthermore, usually U_{ℓ} = 1 (although thus both U_{ℓ} ≥ 2 and, for ℓ ≥ 2, U_{ℓ} = 0 are possible with positive limit probabilities). Indeed, see Remark 4, with probability approching 5π/18, U_{ℓ} = 1 for all ℓ = 1, …, \binom{n}{2} − n simultaneously. Moreover, the tendency for U_{ℓ} to equal 1 becomes more pronounced as ℓ increases, and we have the following result.

Lemma 3. For every ε > 0 there is an L such that, for any n, the probability that U_{ℓ} = 1 for all ℓ = L, L + 1, …, \binom{n}{2} − n is at least 1 − ε.

Sketch of proof. This is an easy consequence of [7, Theorem 16]. Alternatively (and simpler), it can be proved as follows; see [8, Theorem V.10] for more details (in a slightly different case). First, we can find (by methods close to those used in this paper) A such that the probability that a new complex component is created after n/2 + An^{2/3} edges have been added is at most ε/3. Then we find B such that the probability that there exist two complex components in G(n, ⌊n/2 + An^{2/3}⌋) that are not joined by at least one of the following Bn^{2/3} edges is at most ε/3. Finally there is an L such that the probability that there is a component in G(n, ⌊n/2 + (A + B)n^{2/3}⌋) with complexity at least L is at most ε/3. If none of these exceptional events occurs, then U_{ℓ} = 1 for ℓ ≥ L. □

We next observe that U_{ℓ} is close to 1 in mean too, using an argument similar to dominated convergence. Since each complex component must begin as one or several ℓ-components, we have the majorization U_{ℓ} ≤ U_{1} for every ℓ ≥ 1, and thus, by the Cauchy–Schwarz inequality and the fact that 𝔼 U_{1}^{2} ≤ C for some constant C [6],

| 𝔼 U_{ℓ} − 1| ≤ (𝔼(U_{1} + 1)^{2} ℙ(U_{ℓ} ≠ 1))^{1/2} ≤ C′ ℙ(U_{ℓ} ≠ 1)^{1/2}.

By Lemma 3, this implies that 𝔼 U_{ℓ} is close to 1 for large ℓ (for all n), and thus, by Theorem 7,

u′_{ℓ} + u′′_{ℓ} → 1 as ℓ → ∞.  (11)

Indeed, (11) can also be derived from the well-known asymptotics of Wright’s constants ([2, 3]; see also [7, Section 8])

2^{5ℓ/2−1/2}3^{−ℓ}π^{−1/2} \frac{Γ(3ℓ/2)}{Γ(ℓ)}ρ_{ℓ} → \frac{1}{2π}  as ℓ → ∞.  (12)

Simple calculations using Stirling’s formula show that (12) is equivalent to u′_{ℓ} → 1 as ℓ → ∞, and that it implies u′′_{ℓ} → 0 as ℓ → ∞. (More precisely, u′′_{ℓ} = O(ℓ^{−1}); the main contribution for large ℓ coming from the terms with m = 0 and m = ℓ − 1, which together yield u′_{ℓ}/(3ℓ − 1) for ℓ ≥ 2.)

Conversely, our result (11) yields u′_{ℓ} ≤ C for some constant C. The calculations just mentioned now show first that the left hand side of (12) is bounded and then that u′′_{ℓ} = O(ℓ^{−1}). Consequently (11) yields u′_{ℓ} → 1, and thus (by the same calculations again) we obtain a new proof of (12).

Remark 7. The random graph process eventually has a unique complex component, and by Lemma 3 this usually happens before the complexity gets very large. This complex component increases its complexity by receiving new edges added to it and by merging with unicyclic components. The facts that u′_{ℓ} → 1 and u′′_{ℓ} ∼ u′_{ℓ}/(3ℓ − 1) ∼ 1/3ℓ as ℓ → ∞ show that usually the first case occurs, although sometimes a unicyclic component is swallowed.

We may also compute the expected number of transitions ℓ ⊕ −1 → ℓ when the ℓ-components grow; this is, using Lemmas 1 and 2 as in (9),

∑_{k_{1},k_{2}} β(ℓ, −1; k_{1}, k_{2}) ∼ ρ_{ℓ}2^{3ℓ/2+1/2}3^{ℓ/2−5/6}Γ(ℓ/2 + 1/6)n^{1/3}.

This and Theorem 7 yields an extension of the second part of Theorem 1.

Theorem 8. Let ℓ ≥ 0. Then the expected number of static ℓ-components is asymptotically s_{ℓ}n^{1/3}, where

s_{ℓ} = 2^{3ℓ/2+1/2}3^{ℓ/2−5/6}Γ(ℓ/2 + 1/6)ρ_{ℓ}.

For large ℓ we can estimate s_{ℓ} using Stirling’s formula and (12), or by the identity s_{ℓ} = 3^{−1/3}(Γ(ℓ/2 + 1/6)/Γ(ℓ/2 + 1/2))u′_{ℓ+1}; this yields

s_{ℓ} ∼ (3ℓ/2)^{−1/3} as ℓ → ∞.

Finally we consider the number of vertices in ℓ-components, generalizing the results for ℓ = 0 in Section 4.

Theorem 9. For any ℓ ≥ 0,

𝔼 V_{ℓ} ∼ v_{ℓ}n^{2/3}

where

\begin{aligned}v_{ℓ} & = 2^{3ℓ/2}3^{ℓ/2−2/3}Γ(ℓ/2 + 1/3) \\ & · (ρ_{ℓ−1} + ∑_{m=0}^{ℓ}(\frac{2}{π} )^{1/2}ρ_{m}ρ_{ℓ−m−1} \frac{Γ(3m/2 + 1)Γ(3ℓ/2 − 3m/2 + 1/2)}{Γ(3ℓ/2 + 3/2)}). \end{aligned} ; (13)

In particular, V_{ℓ} = O_{p}(n^{2/3}).

Proof. The expected number of vertices contributed by transitions ℓ − 1 → ℓ is ∑_{k} kα(ℓ − 1; k), while the number of vertices contributed by a j-component (−1 ≤ j ≤ ℓ − 1) merging with an (ℓ − j − 1)-component is ∑_{k_{1},k_{2}} k_{1}β(j, ℓ − j − 1; k_{1}, k_{2}). Thus, with m = ℓ − j − 1,

𝔼 V_{ℓ} = ∑_{k} kα(ℓ − 1; k) + ∑_{m=0}^{ℓ} ∑_{k_{1},k_{2}} k_{1}β(ℓ − m − 1, m; k_{1}, k_{2}),

which yields the result using (4), (5) and Lemma 2 as above. □

Corollary 10. For any ℓ ≥ 0, 𝔼 V_{ℓ}^{max} = O(n^{2/3}), and thus V_{ℓ}^{max} = O_{p}(n^{2/3}). □

The proof of Theorem 9 shows that the different terms in (13) correspond to the different ways that an ℓ-component can be created or grow (the latter for m = ℓ).

Example. For ℓ = 1, Theorem 9 yields

𝔼 V_{1} ∼ \frac{25}{16}3^{−1/6}π^{1/2}Γ(5/6)n^{2/3} ≈ 2.603 n^{2/3}.

Of this asymptotical value, 16/25 comes from transitions 0 → 1, 4/25 from transitions 0 ⊕ 0 → 1 and 5/25 from transitions 1 ⊕ −1 → 1 (i.e. from growth of 1-components).

For large ℓ, straightforward estimates using Stirling’s formula and (12) (or u′_{ℓ} → 1 and u′′_{ℓ} → 0) show that the first term in (13) dominates, and we have

v_{ℓ} ∼ 2^{3ℓ/2}3^{ℓ/2−2/3}Γ(ℓ/2 + 1/3)ρ_{ℓ−1} ∼ (12ℓ)^{1/3} as ℓ → ∞.  (14)

Remark 8. We have in this paper studied ℓ-components for ℓ fixed, but one can also let ℓ increase with n. It follows automatically from Theorem 9 and (14) that if ℓ = ℓ(n) → ∞ slowly enough, then 𝔼 V_{ℓ} ∼ (12ℓ)^{1/3}n^{2/3}; however, we do not know for which functions ℓ(n) this holds.

References

[1] D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), 812–854.

[2] G.N. Bagaev & E.F. Dmitriev, Enumeration of connected labeled bipartite graphs. (Russian.) Dokl. Akad. Nauk BSSR 28 (1984), 1061–1063, 1148.

[3] E.A. Bender, E.R. Canfield & B.D. McKay, The asymptotic number of labeled connected graphs with a given number of vertices and edges. Rand. Struct. Alg. 1 (1990), 127–169.

[4] B. Bollobás, Random Graphs. Academic Press, London, 1985.

[5] R.L. Graham, D.E. Knuth & O. Patashnik, Concrete Mathematics. 2nd ed., Addison-Wesley, Reading, Mass., 1994.

[6] S. Janson, Multicyclic components in a random graph process. Rand. Struct. Alg. 4 (1993), 71–84.

[7] S. Janson, D.E. Knuth, T. Łuczak & B. Pittel, The birth of the giant component. Rand. Struct. Alg. 4 (1993), 233–358.

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

[9] T. Łuczak, Component behavior near the critical point of the random graph process. Rand. Struct. Alg. 1 (1990), 287–310.

[10] T. Łuczak, The phase transition in a random graph. In Combinatorics, Paul Erdős is Eighty, Vol. 2, eds. D. Miklós, V.T. Sós & T. Szőnyi, Bolyai Soc. Math. Stud. 2, J. Bolyai Math. Soc., Budapest 1996, pp. 399–422.

[11] T. Łuczak, B. Pittel & J.C. Wierman, The structure of a random graph near the point of the phase transition. Trans. Amer. Math. Soc. 341 (1994), 721–748.

[12] J. Spencer, Enumerating graphs and Brownian motion. Commun. Pure Appl. Math. 50 (1997), 291–294.

[13] E.M. Wright, The number of connected sparsely edged graphs. J. Graph Th. 1 (1977), 317–330.

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

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