CYCLES AND UNICYCLIC COMPONENTS IN RANDOM GRAPHS

SVANTE JANSON

Abstract. The sizes of the cycles and unicyclic components in the random graph G(n, n/2 ± s), where n^{2/3} ≪ s ≪ n, are studied using the language of point processes. This refines several earlier results by different authors. Asymptotic distributions of various random variables are given; these distributions include the gamma distributions with parameters 1/4, 1/2 and 3/4, as well as the Poisson–Dirichlet and GEM distributions with parameters 1/4 and 1/2.

1. Introduction and results

Łuczak [16] studied the cycles in the random graph G(n, m) for m = n/2+s, where n^{2/3} ≪ s ≪ n. One of his results is that the longest cycle outside the giant component and the shortest cycle inside the giant, both have lengths of order n/s; more precisely, both these cycle lengths divided by n/s converge in distribution to strictly positive random variables, and he gave formulae for the limit distributions.

In the present paper, we make a further study of the cycles in G(n, m), in particular the cycles with lengths about n/s, always taking assuming m = n/2 ± s, n^{2/3} ≪ s ≪ n.

Let C_{1}, C_{2}, …, C_{N} be the cycles in G(n, m) that belong to unicyclic components, and let C_{1}^{∗}, C_{2}^{∗}, …, C_{N^{∗}}^{∗} be the remaining cycles, i.e. the cycles that belong to multicyclic components. (The ordering is arbitrary except when specified below.)

It is well-known (see e.g. [5, 15, 9, 10]) that for m = n/2 − s, a.a.s. there are no multicyclic components, and thus {C_{i}} is the set of all cycles in G(n, m) while {C_{i}^{∗}} = ∅; for m = n/2+s, there exists a.a.s. one multicyclic component, the giant component, and thus {C_{i}} is the set of cycles outside the giant and {C_{i}^{∗}} is the set of cycles inside the giant. (In this paper, ‘a.a.s.’ (asymptotically almost surely) means ‘with probability tending to 1 as n → ∞’; in contrast, ‘a.s.’ (almost surely) has the standard probabilistic meaning ‘with probability 1’.)

We will use the language of point processes to study the cycle lengths. We regard a point process as a random (multi)set of points in some fixed space, for example (0, ∞); see Section 4 for technical details, including the definition of the vague topology used in the results below, and a discussion of the difference between e.g. (0, ∞), (0, ∞], etc. as ground spaces.

Date: November 22, 2000.

The following theorem is implicit in [16]. (A proof is given in Section 5, where also the other result stated below are proved.) All unspecified limits here and below are as n → ∞.

Theorem 1. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. Then the two sets of cycle lengths, in unicyclic and in multicyclic components resp., converge after normalization by n/s to two independent Poisson processes as follows.

(i) \{\frac{s}{n}|C_{i}|\} →^{d} Ξ as point processes on (0, ∞], where Ξ is a Poisson process with intensity \frac{1}{2x}e^{−2x}, 0 < x < ∞.

(ii) \{\frac{s}{n}|C_{i}^{∗}|\} →^{d} Ξ^{∗} as point processes on [0, ∞), where Ξ^{∗} is a Poisson process with intensity \frac{1}{2x}(e^{2x} − e^{−2x}) = sinh(2x)/x, 0 < x < ∞, for m = n/2 + s, while Ξ^{∗} = ∅ (a Poisson process with intensity 0) for m = n/2 − s.

(iii) The limits in (i) and (ii) hold jointly, i.e.

(\{\frac{s}{n}|C_{i}|\}, \{\frac{s}{n}|C_{i}^{∗}|\}) →^{d} (Ξ, Ξ^{∗})

(as point processes on (0, ∞] and [0, ∞), respectively), with Ξ and Ξ^{∗} as above and independent.

Note that the total intensity of the Poisson process Ξ is ∫_{0}^{∞} \frac{1}{2x}e^{−2x} dx = ∞, so Ξ is a.s. an infinite set of points. On the other hand, the intensity for any interval [a, ∞) with a > 0 is finite, and thus Ξ has only a finite number of points in each such interval. Consequently, we may write Ξ = {ξ_{1}, ξ_{2}, … }, where ξ_{1} > ξ_{2} > · · ·. Similarly, Ξ^{∗} = {ξ_{1}^{∗}, ξ_{2}^{∗}, … }, where 0 < ξ_{1}^{∗} < ξ_{2}^{∗} < · · ·. By Lemma 4 in Section 4, Theorem 1 can be reformulated as follows.

Theorem 2. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n.

(i) If the cycles C_{i} in unicyclic components are ordered such that their lengths are in decreasing order, i.e. |C_{1}| ≥ |C_{2}| ≥ …, then

(\frac{s}{n}|C_{1}|, \frac{s}{n}|C_{2}|, …) →^{d} (ξ_{1}, ξ_{2}, …),

where ξ_{1} > ξ_{2} > … are the points of the Poisson process Ξ with intensity \frac{1}{2x}e^{−2x}, arranged in decreasing order.

(ii) If m = n/2+s and the cycles C_{i}^{∗} not in unicyclic components are ordered such that their lengths are in increasing order, then

(\frac{s}{n}|C_{1}^{∗}|, \frac{s}{n}|C_{2}^{∗}|, …) →^{d} (ξ_{1}^{∗}, ξ_{2}^{∗}, …),

where ξ_{1}^{∗} < ξ_{2}^{∗} < … are the points of the Poisson process Ξ^{∗} with intensity \frac{1}{2x}(e^{2x} − e^{−2x}), arranged in increasing order.

(iii) The limits in (i) and (ii) hold jointly, with Ξ and Ξ^{∗} independent.

In particular, for each fixed k we have \frac{s}{n}|C_{k}| →^{d} ξ_{k}, where ξ_{k} (by a standard calculation) has a distribution with the density function

\frac{e^{−2x}}{2(k − 1)! x} (∫_{2x}^{∞} \frac{1}{2y} e^{−y} dy)^{k−1} exp (− ∫_{2x}^{∞} \frac{1}{2y} e^{−y} dy) ,  x > 0. (1)

Similarly, if m = n/2 + s, \frac{s}{n}|C_{k}^{∗}| →^{d} ξ_{k}^{∗}, where ξ_{k}^{∗} has the density function

\frac{sinh 2x}{(k − 1)! x} (∫_{0}^{2x} \frac{sinh y}{y} dy)^{k−1} exp (− ∫_{0}^{2x} \frac{sinh y}{y} dy) ,  x > 0. (2)

For k = 1 we recover (and simplify) the result by Łuczak [16, Theorem 3], giving the asymptotic distributions of the lengths of the longest cycle outside the giant and the shortest inside it:

Corollary 3. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. For every a > 0,

ℙ(max\{|C_{i}|\} ≤ an/s) → ℙ(ξ_{1} ≤ a) = exp (− ∫_{2a}^{∞} \frac{1}{2y} e^{−y} dy) ,

and, if m = n/2 + s,

ℙ(min\{|C_{i}^{∗}|\} ≤ an/s) → ℙ(ξ_{1}^{∗} ≤ a) = 1 − exp (− ∫_{0}^{2a} \frac{sinh y}{y} dy) .

We can also employ the joint convergence in Theorem 2.

Corollary 4. Consider G(n, m) with m = n/2 + s, n^{2/3} ≪ s ≪ n. The probability that every cycle inside the giant component is longer than every cycle outside converges to

ℙ(ξ_{1}^{∗} > ξ_{1}) = ∫_{0}^{∞} \frac{e^{−x}}{2x} exp(− ∫_{0}^{x} \frac{e^{y} − e^{−y}}{2y} dy − ∫_{x}^{∞} \frac{e^{−y}}{2y} dy)dx ≈ 0.752.

We have nothing more to add to [16] about the cycles inside the giant. For the cycles outside it, however, we note that if we scale all points in the Poisson process Ξ by 2, we obtain a Poisson process with intensity \frac{1}{2x}e^{−x}, which is a well-known object, see Section 2. It follows from Section 2 that 2 ∑ Ξ = 2 ∑_{k} ξ_{k} has the standard Γ(1/2) distribution, and thus the sum ∑ Ξ = ∑_{k} ξ_{k} of all points in Ξ has the gamma distribution Γ(1/2, 1/2), the normalized sequence ξ_{k}/ ∑ Ξ has a Poisson–Dirichlet distribution PD(1/2), and if the sequence is randomly rearranged in size-biased order, its distribution is known as GEM(1/2).

Theorem 1 does not immediately imply results for the sum ∑ |C_{k}| of the cycle lengths (the vague topology is too weak for that), but the theorem can be augmented as follows. The ‘order of appearance’ in (iii) below is defined by inspecting the vertices of G(n, m) in a given order and for each of them checking whether the vertex belongs to a cycle in a unicyclic component; the first cycle found in this way is C_{1}, the second C_{2}, etc. In other words, the cycles are ordered according to their smallest vertex labels. Similarly, in Theorem 7, we list the unicyclic components in order of appearance, i.e. according to their smallest vertex labels; note that this in general differs from listing the components according to the order of appearance of their cycles.

Theorem 5. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. Let L = ∑_{k} |C_{k}| be the total length of all cycles in unicyclic components. Then the limit in Theorem 1(i) extends to joint convergence

(\{\frac{s}{n}|C_{i}|\}, \frac{s}{n}L) →^{d} (Ξ, ∑ Ξ);

in particular, the following holds.

(i) The total cycle length L has an asymptotic gamma distribution,

2\frac{s}{n}L →^{d} Γ(1/2).

(ii) If the cycles are ordered such that their lengths are in decreasing order, then the sequence of relative lengths converges to a Poisson–Dirichlet distribution,

(|C_{1}|/L, |C_{2}|/L, …) →^{d} PD(1/2).

(iii) If the cycles are listed in order of appearance, then the sequence of relative lengths converges to a GEM distribution,

(|C_{1}|/L, |C_{2}|/L, …) →^{d} GEM(1/2).

We next turn to the sizes of the unicyclic components. Let U_{i} be the component containg C_{i}, and let V = ∑_{i} |U_{i}| be the total size of the unicyclic components.

We have the following counterparts of the theorems above. Theorem 6 has earlier been proved by Łuczak [15] (in a different, slighly weaker form). For m = n/2 − s, Kolchin [14] has found the limit law in Theorem 7(i), and a limit distribution for s^{2}n^{−2}|U_{1}| in Theorem 6, which, however, is more complicated than the one given here; as remarked in [16], these results extend to m = n/2+s by the symmetry rule (cf. Section 8).

Theorem 6. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. Then \{\frac{s^{2}}{n^{2}} |U_{i}|\} →^{d} Ξ′ as point processes on (0, ∞], where Ξ′ is a Poisson process with intensity \frac{1}{4x}e^{−2x}, 0 < x < ∞.

In other words, if the unicyclic components are ordered with decreasing sizes, then

(\frac{s^{2}}{n^{2}} |U_{1}|, \frac{s^{2}}{n^{2}} |U_{2}|, …) →^{d} (ξ′_{1}, ξ′_{2}, …),

where ξ′_{1} > ξ′_{2} > … are the points of the Poisson process Ξ′ arranged in decreasing order.

Theorem 7. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. Let V = ∑_{k} |U_{k}| be the total size of all unicyclic components. Then the limit in Theorem 6 extends to joint convergence

(\{\frac{s^{2}}{n^{2}} |U_{i}|\}, \frac{s^{2}}{n^{2}} V ) →^{d} (Ξ′, ∑ Ξ′);

in particular, the following holds.

(i) The total size V has an asymptotic gamma distribution,

2\frac{s^{2}}{n^{2}} L →^{d} Γ(1/4).

(ii) If the unicyclic components are ordered such that their lengths are in decreasing order, then the sequence of relative lengths converges to a Poisson–Dirichlet distribution,

(|U_{1}|/V, |U_{2}|/V, …) →^{d} PD(1/4).

(iii) If the unicyclic components are listed in order of appearance, then the sequence of relative lengths converges to a GEM distribution,

(|U_{1}|/V, |U_{2}|/V, …) →^{d} GEM(1/4).

We further study the joint distribution of the sizes of the unicyclic components and the length of the cycles in them. This has interesting relations to Brownian motion, more precisely to the hitting time for Brownian motion with drift defined by

T_{a,b} = inf{t : B_{t} + bt = a},  (3)

where B_{t} is a standard Brownian motion and a > 0, −∞ < b < ∞. Note that if b ≥ 0, then 0 < T_{a,b} < ∞ a.s., but if b < 0, then with positive probability B_{t}+bt < a for all t ≥ 0, in which case we set T_{a,b} = +∞. Some basic properties of these random variables are collected in Section 3 below.

Theorem 8. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. Then \{(\frac{s}{n}|C_{i}|, \frac{s^{2}}{n^{2}} |U_{i}|)\} →^{d} Ξ̂ as point processes on [0, ∞] × [0, ∞] \ \{(0, 0)\}, where Ξ̂ is a Poisson process with intensity

\frac{1}{\sqrt{8π}} y^{−3/2}e^{−2y−x^{2}/2y}, 0 < x, y < ∞.

Theorem 9. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. Then, with L and V as above, (\frac{s}{n}L, \frac{s^{2}}{n^{2}} V) →^{d} (X, Y), where (X, Y) has the density

\frac{1}{π} x^{1/2}y^{−3/2}e^{−x^{2}/2y−2y}, x, y > 0.

Moreover, the distribution of (X, Y) is characterized by either of:

(i) X ∈ Γ(1/2, 1/2) and the conditional distribution of Y given X = x is the distribution of T_{x,2}.

(ii) Y ∈ Γ(1/4, 1/2) and X^{2}/2Y ∈ Γ(3/4, 1), with Y and X^{2}/2Y independent.

In particular, it follows that L^{2}/2V →^{d} Γ(3/4).

Furthermore, we can combine this with the result in Theorem 1 for cycles in the giant component. For a real number λ, let Ξ̃_{λ} = {(ξ_{i}, η_{i})}_{1}^{∞} be the point process on (0, ∞) × [0, ∞] defined as follows. Let {ξ_{i}}_{1}^{∞} be a Poisson process on (0, ∞) with intensity \frac{1}{2x}e^{λx}, and given \{ξ_{i}\}_{1}^{∞}, choose η_{i} randomly with the distribution of T_{ξ_{i},−λ}, independently for different i. Thus Ξ̃_{λ} is a Poisson process which has an intensity measure given on (0, ∞) × [0, ∞) by, see (7),

\frac{1}{2x}e^{λx}f_{x,−λ}(y) dx dy = \frac{1}{\sqrt{8π}} y^{−3/2} exp(−x^{2}/2y − λ^{2}y/2) dx dy,  (4)

and on (0, ∞) × {∞} by, see Section 3,

\frac{1}{2x}e^{λx} ℙ(T_{x,−λ} = ∞) dx = \begin{cases}\frac{1}{2x}(e^{λx} − e^{−λx}) dx, & λ > 0, \\ 0, & λ ≤ 0. \end{cases}  (5)

Note that if a > 0, and we rescale Ξ̃_{λ} by defining Ξ̃_{λ}^{(a)} = {(aξ_{i}, a^{2}η_{i})}, then Ξ̃_{λ}^{(a)} =^{d} Ξ̃_{λ/a}. Note further that Ξ̃_{−2} equals Ξ̂ in Theorem 8.

We then have the following result; note that unlike in the other theorems, s may here be negative and that we thus consider the cases m < n/2 and m > n/2 together, the difference between the cases corresponding to the different behaviour at infinity of T_{x,−λ} and Ξ̃_{λ} for positive and negative λ.

Theorem 10. Consider G(n, m) with m = n/2 + s, n^{2/3} ≪ |s| ≪ n. Let {C̃_{i}} = {C_{i}} ∪ {C_{i}^{∗}} be the collection of all cycles in G(n, m), and let Ũ_{i} be the component containing C̃_{i}. Then {(|C̃_{i}|, |Ũ_{i}|)} is approximated by Ξ̃_{2s/n}, in the sense that if a_{n} > 0 are such that a_{n}^{−1}s/n → α ≠ 0, then {(a_{n}|C̃_{i}|, a_{n}^{2}|Ũ_{i}|)} →^{d} Ξ̃_{2α} on (0, ∞) × [0, ∞].

The points (ξ, η) in Ξ̃_{2α} with η < ∞ correspond (as a limit) to unicyclic components, while the points with η = ∞ correspond to cycles in the giant component.

Remark 1. In the studied ranges of m, the asymptotic distributions above do not depend on s except through the scaling.

Remark 2. Corresponding results for m = n/2 + O(n^{2/3}) are much more complicated, and we do not obtain Poisson process limits in that case. See [1], [18], [17], or [10]. For the other endpoint, some results for s = Θ(n) are given in [5]; here we still obtain Poisson limits, but the results are somewhat different.

Remark 3. All results above hold for the random graph G(n, p) too, with p = 1/n + 2s/n^{2}, i.e. when n^{−4/3} ≪ |p − n^{−1}| ≪ n^{−1}. This follows easily by conditioning on the number of edges, or by simple modifications of the proofs below.

Remark 4. As is witnessed by the χ^{2} distribution, the standard normalizations of the normal and gamma distributions do not match. As a consequence, the scaling factors chosen above are not always the most convenient ones. For example, normalizing by 2s/n and 2s^{2}/n^{2} instead in Theorem 9, we obtain convergence to the standard gamma distributions Γ(1/2) and Γ(1/4), but we would get T_{x/\sqrt{2},\sqrt{2}} in (i).

Remark 5. In this paper we consider only G(n, m) for a single m (depending on n). It would be interesting to study the random graph process {G(n, m)}_{m≥0} and find asymptotic descriptions of how the various variables and point processes above behave as functions of m (in a suitable range).

Finally we remark that it should not be inferred, however, that all properties of the family of cycles in unicyclic components are reflected in the Poisson processes defined above; by the nature of the convergence in the vague topology, the asymptotics in this paper really only describe cycles of lengths of the order n/s. A concrete counterexample is provided by the following simple result, which contrasts with the fact that the Poisson process Ξ has no double points.

Theorem 11. Consider G(n, m) with m = n/2 ± s, n^{2/3} ≪ s ≪ n. The probability that G(n, m) has two cycles of the same length, both belonging to unicyclic components, converges to

1 − ∏_{k=3}^{∞}(1 + \frac{1}{2k} )e^{−1/2k} = 1 − \frac{16}{15}π^{−1/2}e^{3/4−γ/2} ≈ 0.045.

Some preliminaries are given in Sections 2–4. The theorems above are proved, using the standard method of moments, in Section 5. The final sections contain heuristic arguments using instead Brownian motion and branching processes. These arguments could probably be made rigorous, although we have not attempted that; in any case, we find them conceptually useful.

2. Gamma, Poisson–Dirichlet and GEM distributions

We let, for α, b > 0, Γ(α, b) denote the gamma distribution with density function b^{−1}g_{α}(x/b), where

g_{α}(x) = Γ(α)^{−1}x^{α−1}e^{−x}.  (6)

Thus b is a scale factor only; the distribution Γ(α, 1) with density function g_{α} is called standard gamma and is also denoted by Γ(α).

It is well-known that if α > 0 and Ξ = {ξ_{1}, ξ_{2}, … } is a Poisson process on (0, ∞) with intensity αx^{−1}e^{−x}, then the sum Σ = ∑_{1}^{∞} ξ_{i} of all points in Ξ is a.s. finite, and has the gamma distribution Γ(α). Moreover [12, 13, 2], if we normalize by this sum Σ and consider the sequence (ξ_{1}/Σ, ξ_{2}/Σ, …), with the terms in decreasing order, the distribution of this random sequence is known as Poisson–Dirichlet and denoted by PD(α). If we reorder this sequence by size-biased sampling, we instead obtain the GEM distribution GEM(α).

More generally, if α, b > 0 and Ξ is a Poisson process with intensity αx^{−1}e^{−x/b}, a simple rescaling shows that b^{−1}Σ ∈ Γ(α), and thus Σ ∈ Γ(α, b), while the sequence (ξ_{1}/Σ, ξ_{2}/Σ, …), with the two orderings above, still has the distributions PD(α) and GEM(α), respectively.

3. A hitting time distribution

We collect here some useful facts about the distributions of the hitting times T_{a,b} defined in (3).

The case b = 0 is well-known; T_{a,0} has a stable(1/2) distribution, see e.g. [19, Propositions II.(3.7), III.(3.10)]. The general case is similar. By [19, Exercises II.(3.14), III.(3.28) and VIII.(1.21)] for b > 0, and the same arguments (optional stopping of exponential martingales or the Girsanov–Cameron–Martin theorem) for b < 0, T_{a,b} has the density function

f_{a,b}(t) = \frac{a}{\sqrt{2π}} t^{−3/2} exp(−a^{2}/2t − b^{2}t/2 + ab),  0 < t < ∞,  (7)

and the Laplace transform

𝔼 e^{−λT_{a,b}} = e^{a(b−\sqrt{b^{2}+2λ})},  λ > 0.  (8)

For b < 0 this means that ℙ(T_{a,b} < ∞) = e^{−2a|b|}, cf. [19, Exercise II.(3.12)], and that the conditional distribution of T_{a,b} given T_{a,b} < ∞ equals the distribution of T_{a,|b|}.

Note that if b ≥ 0 is fixed, then the strong Markov property of Brownian motion implies that a ↦ T_{a,b} is an increasing stochastic process with independent, stationary increments. In particular, if a_{1}, a_{2} > 0, and T′_{a_{2},b} denotes a copy of T_{a_{2},b} that is independent of T_{a_{1},b}, then

T_{a_{1},b} + T′_{a_{2},b} =^{d} T_{a_{1}+a_{2},b}.  (9)

(This follows also from (8).) It follows also that (for b ≥ 0) T_{a,b} has an infinitely divisible distribution. Although we will not need it, we remark that its Lévy measure has the density a(2π)^{−1/2}x^{−3/2}e^{−b^{2}x/2}, 0 < x < ∞; in other words, T_{a,b} is distributed as the sum of all points in a Poisson process with this density, cf. the corresponding result for gamma distributions in Section 2.

4. Point processes

We give here some technical remarks on point processes; see e.g. [11] for further details and proofs.

Let 𝔖 be a ‘nice’ topological space; more precisely, a locally compact Polish space. (In this paper we only consider intervals in \overline{ℝ} = [−∞, ∞] and some simple subsets of \overline{ℝ}^{2}.) Although we regard a point process as a random (multi)set {ξ_{i}}_{i} ⊂ 𝔖, it is technically convenient to formally define it as a random measure ∑_{i} δ_{ξ_{i}}. Hence, if Ξ denotes the point process {ξ_{i}}, we write Ξ(A) for the number of points ξ_{i} that belong to a subset A ⊆ 𝔖; similarly, for suitable functions f on 𝔖, ∫ f dΞ = ∑_{i} f(ξ_{i}).

Thus, let 𝔑 = 𝔑(𝔖) be the class of all Borel measures μ on 𝔖 such that μ(A) is a (finite) integer 0, 1, … for every compact Borel set A; this coincides with the class of all finite or countably infinite sums of the type ∑_{i} δ_{x_{i}}, where x_{i} ∈ 𝔖 and each compact subset of 𝔖 contains only a finite number of x_{i}, and we identify such a sum with the (multi)set {x_{i}}.

The standard topology on 𝔑 (known as the vague topology) is defined such that, for μ, μ_{1}, μ_{2}, ⋯ ∈ 𝔑, μ_{n} → μ if and only if ∫ f dμ_{n} → ∫ f dμ for every f ∈ C_{c}(𝔖), the space of real-valued continuous functions on 𝔖 with compact support.

A point process on 𝔖 is a random element of 𝔑. The vague topology is metrizable, so the general theory in [4] of convergence in distribution applies.

If Ξ_{n} and Ξ are point processes on 𝔖, then Ξ_{n} →^{d} Ξ (w.r.t. the vague topology just defined) if and only if ∫ f dΞ_{n} →^{d} ∫ f dΞ (as real-valued random variables) for every f ∈ C_{c}(𝔖). It is also true that Ξ_{n} →^{d} Ξ if and only if Ξ_{n}(A) →^{d} Ξ(A) for every relatively compact Borel set A ⊆ 𝔖 such that Ξ(∂A) = 0 a.s., and moreover joint convergence holds for every finite collection of such sets A.

Note that the definitions of both point processes and convergence of them are sensitive to the choice of 𝔖, since a point process is not allowed to have any cluster point in 𝔖. Hence, for subsets of ℝ^{d}, say, it matters whether boundary points are included. For example, if 𝔖 is a closed interval (or any compact set), then every point process is finite. If, instead, 𝔖 is a half-open interval (a, b], then an element μ ∈ 𝔑 is finite on every interval [c, b], a < c < b, and thus every point process may be written as a (finite or infinite) set {ξ_{i}} with ξ_{1} ≥ ξ_{2} ≥ … and, if the set is infinite, ξ_{i} → a as i → ∞. If 𝔖 = [a, b) we may similarly write a point process as {ξ_{i}} with ξ_{1} ≤ ξ_{2} ≤ … and, if the set is infinite, ξ_{i} → b as i → ∞. Finally, a point process on an open interval (a, b) may have both a and b as cluster points. By including one or both endpoints, we thus get stronger conditions; similarly, as is shown more generally in the following lemma, we get a stronger mode of convergence. It may thus be advantageous to consider (when possible) a random set of points in (a, b) as a point process on [a, b), (a, b] or [a, b].

Lemma 1. Suppose that 𝔖′ is a locally compact subset of 𝔖 and that Ξ_{n}, Ξ are point processes on 𝔖 that a.s. have all their points in 𝔖′.

(i) If Ξ_{n} →^{d} Ξ on 𝔖, then Ξ_{n} →^{d} Ξ on 𝔖′. (ii) If Ξ_{n} →^{d} Ξ on 𝔖′, and for each compact K ⊆ 𝔖 and ε > 0, there exists

a compact K_{ε} ⊆ 𝔖′ such that lim sup_{n→∞} ℙ(Ξ_{n}(K \ K_{ε}) ≠ 0) ≤ ε, then

Ξ_{n} →^{d} Ξ on 𝔖.

Proof. For the first part, suppose that f ∈ C_{c}(𝔖′). Fix a metric on 𝔖. Since supp f is compact, f is uniformly continuous, and may thus be extended to a continuous function on the closure 𝔖̄′ ⊆ 𝔖 [6, Theorem 4.3.17], which by the Tietze–Urysohn extension theorem [6, Theorem 2.1.8 or Exercise 4.1.F] may be further extended to a continuous function f_{1} on 𝔖. Moreover, since supp f is compact and 𝔖 is locally compact, there exists a continuous function g ∈ C_{c}(𝔖) that equals 1 on supp f. Thus f_{2} = gf_{1} ∈ C_{c}(𝔖) and f_{2} = f on 𝔖′. Hence

∫_{𝔖′} f dΞ_{n} = ∫_{𝔖} f_{2} dΞ_{n} →^{d} ∫_{𝔖} f dΞ = ∫_{𝔖′} f dΞ,

and by the criterion above, Ξ_{n} →^{d} Ξ on 𝔖′.

For (ii), let f ∈ C_{c}(𝔖), take K = supp f and let, for N ≥ 1, K_{1/N} be as in the assumption with ε = 1/N. We may assume that K_{1} ⊆ K_{1/2} ⊆ ⋯, and that ⋃_{N} K_{1/N} = 𝔖′. There exists a function g_{N} ∈ C_{c}(𝔖′) with 0 ≤ g_{N} ≤ 1 and g_{N}(x) = 1 for x ∈ K_{1/N}. Thus f_{N} = g_{N}f ∈ C_{c}(𝔖′) and

|∫_{𝔖} f dΞ_{n} − ∫_{𝔖′} f_{N} dΞ_{n}| = |∫_{𝔖′} f(1 − g_{N}) dΞ_{n}| ≤ Ξ_{n}(K \ K_{1/N}) sup |f|,

since f(1 − g_{N}) = 0 off K \ K_{1/N}, and thus

lim_{N→∞} lim sup_{n→∞} ℙ(∫_{𝔖′} f_{N} dΞ_{n} ≠ ∫_{𝔖} f dΞ_{n}) = 0.

Moreover, ∫_{𝔖′} f_{N} dΞ_{n} → ∫_{𝔖′} f_{N} dΞ as n → ∞ for each fixed N, and, denoting the finite set of points in Ξ that belong to K by {ξ′_{j}},

∫_{𝔖′} f_{N} dΞ = ∑_{j} f(ξ′_{j})g_{N}(ξ′_{j}) → ∑_{j} f(ξ′_{j}) = ∫_{𝔖} f dΞ as N → ∞.

It now follows [4, Theorem 4.2] that ∫_{𝔖} f dΞ_{n} → ∫_{𝔖} f dΞ as n → ∞.

In Lemma 1 we assumed that all points that occurs in the point processes lie in the subspace 𝔖′, so that the processes can be regarded as point processes on 𝔖′ too. More generally, we can ignore points outside 𝔖′: if μ ∈ 𝔑(𝔖), we define the restriction μ|_{𝔖′} to be the measure A ↦ μ(A ∩ 𝔖′); regarded as (multi)sets we have μ|_{𝔖′} = μ ∩ 𝔖′.

Lemma 2. Suppose that 𝔖′ is a locally compact subset of 𝔖. The mapping μ ↦ μ|_{𝔖′} is a measurable map 𝔑(𝔖) → 𝔑(𝔖′) which is continuous at every μ ∈ 𝔑(𝔖) such that μ(∂𝔖′) = 0. Consequently, if Ξ_{n} and Ξ are point processes on 𝔖 such that Ξ_{n} →^{d} Ξ, and further Ξ(∂𝔖′) = 0 a.s., then Ξ_{n}|_{𝔖′} →^{d} Ξ|_{𝔖′}.

Proof. The claim about measurability follows immediately, since the Borel σfields are generated by the mappings μ ↦ μ(A), where A ranges over the Borel sets in 𝔖 and 𝔖′, respectively [11, Lemma 4.1]; note that 𝔖′ is σ-compact and thus a Borel subset of 𝔖.

Suppose μ_{n} → μ in 𝔑(𝔖), with μ(∂𝔖′) = 0, and let f ∈ C_{c}(𝔖′). As in the proof of Lemma 1, f can be extended to a function f_{2} ∈ C_{c}(𝔖). Let A = supp(f_{2}) ∩ ∂𝔖′; this is a closed subset of supp(f_{2}) and is thus compact. Moreover, μ(A) = 0, and thus A∩supp(μ) = ∅, and there exists a non-negative function g ∈ C_{c}(𝔖) such that g = 1 in a neighbourhood U of A but g = 0 on supp(μ) and thus ∫ g dμ = 0. Since then ∫ g dμ_{n} → ∫ g dμ = 0 as n → ∞, for some n_{0} and all n > n_{0} we have ∫ g dμ_{n} < 1 and thus μ_{n}(U) = 0.

There exists a non-negative function h ∈ C_{c}(𝔖) with supp(h) ⊂ U and h = 1 on A. The function f_{3} = f_{2}(1−h) ∈ C_{c}(𝔖) then vanishes on ∂𝔖′. Thus, if we define f_{4} by f_{4}(x) = f_{3}(x) for x ∈ 𝔖′ and f_{4}(x) = 0 for x ∉ 𝔖′, f_{4} is continuous, and f_{4} ∈ C_{c}(𝔖). Moreover, if n > n_{0}, then supp(h)∩supp(μ_{n}) = ∅ and thus on supp(μ_{n}) ∩ 𝔖′ we have h = 0 and f_{4} = f_{3} = f_{2} = f; the same holds on supp(μ) ∩ 𝔖′. Consequently, for large n,

∫_{𝔖′} f dμ_{n} = ∫_{𝔖′} f_{4} dμ_{n} = ∫_{𝔖} f_{4} dμ_{n} → ∫_{𝔖} f_{4} dμ = ∫_{𝔖′} f_{4} dμ = ∫_{𝔖′} f dμ,

and μ_{n}|_{𝔖′} → μ|_{𝔖′} follows.

The final assertion on convergence in distribution follows by [4, Theorem 5.1].

The next lemma follows easily from the definitions above.

Lemma 3. If φ : 𝔖 → 𝔖′ is continuous and proper, i.e. φ^{−1}(K) is compact for every compact K ⊆ 𝔖′, then for every point process Ξ = {ξ_{i}} on 𝔖, the image φ(Ξ) = {φ(ξ_{i})} is a point process on 𝔖′. Moreover, if Ξ_{n} →^{d} Ξ on 𝔖, then φ(Ξ_{n}) →^{d} φ(Ξ) on 𝔖′.

For point processes on a closed or half-open interval, with the points ordered as above, convergence in distribution is equivalent to joint convergence of the individual points. We state this for the two cases we are interested in.

Lemma 4. Suppose that Ξ_{n}, 1 ≤ n ≤ ∞, are point processes on the interval (0, ∞], and write Ξ_{n} = {ξ_{ni}}_{i=1}^{N_{n}} with ξ_{n1} ≥ ξ_{n2} ≥ … and 0 ≤ N_{n} ≤ ∞. If some N_{n} < ∞, define further ξ_{ni} = 0 for i > N_{n}. Then Ξ_{n} →^{d} Ξ_{∞} if and only if (ξ_{n1}, ξ_{n2}, …) →^{d} (ξ_{∞1}, ξ_{∞2}, …), in the standard sense that all finite dimensional distributions converge.

The same holds for point processes on [0, ∞), now with ξ_{n1} ≤ ξ_{n2} ≤ …, and ξ_{ni} = ∞ for i > N_{n}.

Proof. It suffices to prove this for non-random sets, i.e. (for (0, ∞]) that the one-to-one correspondence between 𝔑 and the set 𝔛 of all non-increasing sequences {x_{i}}_{i} ∈ [0, ∞]^{∞} such that lim_{i→∞} x_{i} = 0, is a homomorphism when [0, ∞]^{∞} is given the product topology and 𝔛 the corresponding subspace topology. This is a simple consequence of the definition of the vague topology, and we omit the details.

A Poisson process on 𝔖 with intensity measure ν is a point process Ξ such that Ξ(A) has a Poisson distribution with parameter ν(A) for every Borel set A, and Ξ(A_{1}), …, Ξ(A_{k}) are independent for disjoint Borel sets A_{1}, …, A_{k}. Here ν may be any Borel measure on 𝔖 that is finite on compact sets; we will mainly consider absolutely continuous measures (w.r.t. Lebesgue measure on ℝ or ℝ^{2}), and the density of ν is then called the intensity of Ξ.

5. Proofs

Let Z(k, l) be the number of cycles in G(n, m) that have size k and lie in a unicyclic component of order l and let Z̃(k) be the total number of cycles of length k. (Here 3 ≤ k ≤ l ≤ m.)

Denote the corresponding expectations by z(k, l) = 𝔼 Z(k, l) and z̃(k) = 𝔼 Z̃(k). When necessary, we indicate n and m by subscripts and write z_{n,m}(k, l) etc.

As numerous authors before us, we make the straightforward calculations

z̃(k) = \binom{n}{k}\frac{k!}{2k} \binom{\binom{n}{2} − k}{m − k}\binom{\binom{n}{2}}{m}^{−1} = \frac{n\underline{k}m\underline{k}}{2k\binom{n}{2}\underline{k}} ,  (10)

where n\underline{k} = n(n − 1) ⋯ (n − k + 1), and

\begin{aligned}z(k, l) & = \binom{n}{k}\frac{k!}{2k} \binom{n − k}{l − k}kl^{l−k−1}\binom{\binom{n−l}{2}}{m − l}\binom{\binom{n}{2}}{m}^{−1} \\ & = \frac{n\underline{l}l^{l−k−1}m\underline{l}\binom{n−l}{2}\underline{m−l}}{2(l − k)! \binom{n}{2}\underline{m}} \\ & = \frac{l\underline{k}}{l^{k}} \frac{l^{l−1}}{2l!} \frac{n\underline{l}m\underline{l}\binom{n−l}{2}\underline{m−l}}{\binom{n}{2}\underline{m}} . \end{aligned}  (11)

As n → ∞, (10) implies, for k = O(n/s),

z̃(k) = \frac{n^{k}m^{k}}{2k\binom{n}{2}^{k}} (1 + O(k^{2}/n)) = \frac{1}{2k} (1 + \frac{2s}{n})^{k}(1 + o(1)) = \frac{e^{2ks/n+o(1)}}{2k} . (12)

Similarly, (11) implies, by a standard calculation using Stirling’s formula and Taylor expansions of logarithms which we omit, that if k = O(n/s) and l = Θ(n^{2}/s^{2}), then

z(k, l) ∼ (8πl^{3})^{−1/2} exp(−\frac{k^{2}}{2l} − \frac{2s^{2}}{n^{2}} l) = \frac{s^{3}}{n^{3}} ψ(k \frac{s}{n}, l\frac{s^{2}}{n^{2}} )  (13)

with

ψ(x, y) = \frac{1}{\sqrt{8πy^{3}}} exp(−\frac{x^{2}}{2y} − 2y).  (14)

Moreover, similar calculations, which we also omit, show that for some constants c and c′ > 0, and all k and l,

z(k, l) ≤ c′l^{−3/2} exp(−\frac{k^{2}}{2l} − c\frac{s^{2}}{n^{2}} l).  (15)

Proof of Theorem 8. We begin by proving convergence on (0, ∞)×(0, ∞). Let Ξ_{n} = \{(\frac{s}{n}|C_{i}|, \frac{s^{2}}{n^{2}} |U_{i}|)\}.

By [11, Theorem 4.2], it suffices to prove that for any finite family of rectangles R_{i} = [a_{i}, b_{i})×[c_{i}, d_{i}) with 0 < a_{i} < b_{i} < ∞, 0 < c_{i} < d_{i} < ∞, i = 1, …, N, we have Ξ_{n}(R_{i}) →^{d} Ξ̂(R_{i}), jointly for all i. By subdividing the rectangles, if necessary, it suffices to prove this for a disjoint family of rectangles, i.e. to prove that if R_{1}, …, R_{N} are disjoint rectangles, then Ξ_{n}(R_{i}) →^{d} Po(μ(R_{i})), jointly and with independent limits, where μ is the measure with density ψ(x, y) given by (14).

We show this by the method of moments in the traditional way. First, define for E ⊆ ℝ^{2}, τ_{n}(E) = {(xn/s, yn^{2}/s^{2}) : (x, y) ∈ E}. Then

Ξ_{n}(R_{i}) = ∑_{(k,l)∈τ_{n}(R_{i})} Z(k, l),

and thus, letting τ′_{n}(R_{i}) = [⌈a_{i}n/s⌉, ⌊b_{i}n/s⌋ + 1) × [⌈c_{i}n^{2}/s^{2}⌉, ⌊d_{i}n^{2}/s^{2}⌋ + 1) be τ_{n}(R_{i}) rounded off to integer coordinates and R_{in} = τ_{n}^{−1}(τ′_{n}(R_{i})), we have by (13) and dominated convergence, using (15),

𝔼 Ξ_{n}(R_{i}) = ∑_{(k,l)∈τ_{n}(R_{i})} z(k, l) = ∫_{τ′_{n}(R_{i})} z(⌊u⌋, ⌊v⌋) du dv

= ∫_{R_{in}} z(⌊xn/s⌋, ⌊yn^{2}/s^{2}⌋)\frac{n^{3}}{s^{3}} dx dy

→ ∫_{R_{i}} ψ(x, y) dx dy = μ(R_{i}).

It is similarly shown that all mixed factorial moments converge, using the fact that conditioned on the existence of a specific unicyclic component on l given vertices, the rest of G(n, m) is a random graph G(n − l, m − l). Hence, for example, using l = O(n^{2}/s^{2}) = o(s), by dominated convergence as above,

𝔼(Ξ_{n}(R_{1})(Ξ_{n}(R_{1}) − 1)Ξ_{n}(R_{2}))

= ∑_{\begin{matrix}(k_{1},l_{1})∈τ_{n}(R_{1}) \\ (k_{2},l_{2})∈τ_{n}(R_{1}) \\ (k_{3},l_{3})∈τ_{n}(R_{2}) \end{matrix}} z_{n,m}(k_{1}, l_{1})z_{n−l_{1},m−l_{1}}(k_{2}, l_{2})z_{n−l_{1}−l_{2},m−l_{1}−l_{2}}(k_{3}, l_{3})

→ μ(R_{1})^{2}μ(R_{2}).

By the method of moments, this implies the required joint convergence Ξ_{n}(R_{i}) →^{d} Po(μ(R_{i})).

This completes the proof that Ξ_{n} →^{d} Ξ̂ on 𝔖′ = (0, ∞) × (0, ∞). In order to extend this to 𝔖 = [0, ∞] × [0, ∞] \ {(0, 0)}, we use Lemma 1. If K ⊂ 𝔖 is compact, then ([0, r] × [0, r]) ∩ K = ∅ for some r > 0. Taking K_{j} = [j^{−1}, j] × [j^{−1}, j] and writing (E)_{δ} = {x : d(x, E) < δ} for E ⊂ ℝ^{2}, we have, using (15), for some c, c_{1} > 0 and large n,

𝔼 Ξ_{n}(K \ K_{j}) = ∑_{(k,l)∈τ_{n}(K\K_{j})} z(k, l) ≤ ∫_{(τ_{n}(K\K_{j}))\sqrt{2}} z(⌈u⌉, ⌊v⌋) du dv

≤ ∫_{(K\K_{j})_{2s/n}} z(⌈xn/s⌉, ⌊yn^{2}/s^{2}⌋)\frac{n^{3}}{s^{3}} dx dy

≤ c_{1} ∫_{(K\K_{j})_{2s/n}} y^{−3/2} exp(−\frac{x^{2}}{2y} − cy) dx dy.

Since ψ′(x, y) = y^{−3/2} exp(−x^{2}/2y − cy) is integrable over (0, ∞)^{2} \ (0, r)^{2}, we obtain by dominated convergence first

lim sup_{n→∞} ℙ(Ξ_{n}(K \ K_{j}) ≠ 0) ≤ lim sup_{n→∞} 𝔼 Ξ_{n}(K \ K_{j}) ≤ c_{1} ∫_{K\K_{j}} ψ′(x, y) dx dy

and then

lim_{j→∞} lim sup_{n→∞} ℙ(Ξ_{n}(K \ K_{j}) ≠ 0) = 0.

The theorem now follows by Lemma 1(ii).

Proof of Theorems 1(i), 2(i) and 6. By Lemma 1(i), the convergence in Theorem 8 holds also on the subset (0, ∞] × [0, ∞], and since the projection π : (x, y) ↦ x is continuous and proper (0, ∞] × [0, ∞] → (0, ∞], Lemma 3 shows that \{\frac{s}{n}|C_{i}|\} →^{d} π(Ξ̂) on (0, ∞].

Moreover, since Ξ̂ is a Poisson process with intensity

ψ(x, y) = (8πy^{3})^{−1/2} exp(−\frac{x^{2}}{2y} − 2y) = \frac{1}{2x}e^{−2x}f_{x,2}(y),

see (14) and (7), and ∫_{0}^{∞} f_{x,2}(y) dy = 1, π(Ξ̂) is a Poisson process with intensity

∫_{0}^{∞} ψ(x, y) dy = \frac{1}{2x}e^{−2x}.

This proves Theorem 1(i), and Theorem 2(i) follows by Lemma 4.

Similarly, we obtain Theorem 6 by projecting on the second coordinate [0, ∞] × (0, ∞] → (0, ∞] and integrating

∫_{0}^{∞} ψ(x, y) dx = (8πy^{3})^{−1/2}e^{−2y} ∫_{0}^{∞} e^{−x^{2}/2y} dx = \frac{1}{4y} e^{−2y}.

Proof of Theorem 5. Let, for N ≥ 1, f_{N} be a function in C_{c}(0, ∞) such that 0 ≤ f_{N}(x) ≤ x for all x and f_{N}(x) = x when 1/N ≤ x ≤ N, and further f_{N} ≥ f_{N−1} when N ≥ 2. Let L_{N} = ∑_{i} f_{N}(\frac{s}{n}|C_{i}|).

Since the mapping ν ↦ (ν, ∫ f_{N} dν) is continuous 𝔑(ℝ) → 𝔑(ℝ) × ℝ, the convergence \{\frac{s}{n}|C_{i}|\} →^{d} Ξ implies the joint convergence (\{\frac{s}{n}|C_{i}|\}, L_{N}) →^{d} (Ξ, ∫ f_{N} dΞ), as n → ∞, for each fixed N, cf. [4, Section 5]. By monotone convergence, ∫ f_{N} dΞ →^{d} ∫ x dΞ = ∑ Ξ as N → ∞. Moreover,

\begin{aligned}L_{N} ≤ \frac{s}{n}L & ≤ L_{N} + \frac{s}{n} ∑_{i} |C_{i}|1[\frac{s}{n}|C_{i}| < 1/N] + \frac{s}{n} ∑_{i} |C_{i}|1[\frac{s}{n}|C_{i}| > N] \\ & = L_{N} + S_{1} + S_{2}, \end{aligned}

say. Now, for some c > 0,

𝔼 S_{1} ≤ \frac{s}{n} ∑_{k≤ \frac{n}{s} N^{−1}} kz̃(k) ≤ c/N

by (12), and thus

\begin{aligned}ℙ(|L_{N} − \frac{s}{n}L| > ε) & ≤ ℙ(S_{1} + S_{2} > ε) ≤ ℙ(S_{1} > ε) + ℙ(S_{2} ≠ 0) \\ & ≤ c/Nε + ℙ(max_{i} \frac{s}{n}|C_{i}| > N). \end{aligned}

Consequently, by Theorem 2(i),

lim sup_{n→∞} ℙ(|L_{N} − \frac{s}{n}L| > ε) ≤ c/Nε + ℙ(ξ_{1} > N),

which tends to 0 as N → ∞. Thus, by [4, Theorem 4.2], (\{\frac{s}{n}|C_{i}|\}, \frac{s}{n}L) →^{d} (Ξ, ∑ Ξ), as n → ∞.

The assertions (i) and (ii) now follow by Section 2 and Lemma 4; for (iii) we observe that taking the cycles in order of appearence gives a size-biased distribution of the sequence of their lengths.

Proof of Theorem 7. By Theorem 6 and similar arguments as in the proof of Theorem 5, using (15) to obtain the estimate (with ε = 1/N)

𝔼 ∑_{l≤εn^{2}/s^{2}} ∑_{k} \frac{s^{2}}{n^{2}} lz(k, l) ≤ c_{1} \frac{s^{2}}{n^{2}} ∫_{0}^{εn^{2}/s^{2}+1} ∫_{0}^{∞} v^{−1/2}e^{− \frac{u^{2}}{2v} −c \frac{s^{2}}{n^{2}} v}du dv

≤ c_{1} ∫_{0}^{2ε} ∫_{0}^{∞} y^{−1/2}e^{−x^{2}/2y−cy}dx dy
= c_{2} ∫_{0}^{2ε} e^{−cy} dy = O(ε).

Proof of Theorem 9. It follows as in the proofs of Theorems 5 and 7, using the estimates obtained there, that we can sum all points in Theorem 8 and obtain (\frac{s}{n}L, \frac{s^{2}}{n^{2}} V) →^{d} ∑ Ξ̂. The theorem now follows as the case α = 1/4 of the following more general result.

Lemma 5. Let α > 0 and let Ξ̂ be a Poisson process in (0, ∞) × (0, ∞) with intensity

α\sqrt{2/π}y^{−3/2} exp(−x^{2}/2y − 2y).

Then (X, Y) = ∑ Ξ̂ has a distribution that can be characterized by any of the three following properties.

(i) (X, Y) has a density

2^{2α−1/2}π^{−1/2}Γ(2α)^{−1}x^{2α}y^{−3/2} exp(−x^{2}/2y − 2y), 0 < x, y < ∞.

(ii) X has a gamma distribution Γ(2α, \frac{1}{2}), and given X = x, Y is distributed

as T_{x,2}. (iii) Y ∈ Γ(α, \frac{1}{2}) and X^{2}/2Y ∈ Γ(α + \frac{1}{2}, 1), with Y and X^{2}/2Y independent.

Proof. Let h(x, y) denote the intensity of Ξ̂ and write the points of Ξ̂ as (ξ_{1}, η_{1}), (ξ_{2}, η_{2}), . . .. Since h(x, y) = h_{1}(x)f_{x,2}(y) with h_{1}(x) = 2αx^{−1}e^{−2x} and f_{x,2} given by (7), and thus the marginal intensity ∫ h(x, y) dy = h_{1}(x), the Poisson process Ξ̂ can be constructed by first taking a Poisson process Ξ = {ξ_{1}, ξ_{2}, … } on (0, ∞) with intensity h_{1}(x), and then for each ξ_{i} randomly choosing η_{i} with the distribution of T_{ξ_{i},2} (independently for all i). Conditional on (ξ_{1}, ξ_{2}, …) we thus have by (9), for any finite N, ∑_{1}^{N} η_{i} =^{d} T_{∑_{1}^{N} ξ_{i},2}, and letting N → ∞,

Y = ∑_{1}^{∞} η_{i} =^{d} T_{X,2}.  (16)

Moreover, by Section 2, X ∈ Γ(2α, \frac{1}{2}), which yields (ii).

Consequently, X has the density 2g_{2α}(2x), and the conditional density of Y given X = x is by (16) f_{x,2}(y). Thus (X, Y) has the density 2g_{2α}(2x)f_{x,2}(y), which by (6) and (7) yields (i).

Finally, denoting the density just obtained by ρ(x, y) and letting Z = X^{2}/2Y, the density of (Z, Y) is

(2z)^{−1/2}y^{1/2}ρ(\sqrt{2yz}, y) = cy^{α−1}z^{α−1/2}e^{−z−2y} = 2g_{α}(2y)g_{α+1/2}(z),

for some constant c, which shows (iii). (It is easy to calculate c, and verify the formula just given by the duplication formula for the gamma function, but it is easier to ignore the constants and just note that a density function integrates to one, so the constants have to match.)

In order to treat the cycles in the giant component (and in other multicyclic components, in the unlikely event that such exist), we first show that the method of moment applies when we count all cycles.

Lemma 6. Consider G(n, m) with m = n/2 + s, n^{2/3} ≪ s ≪ n. Let I = [a, b) be an interval with 0 < a < b < ∞, and let Z̃_{n}(I) be the number of cycles in G(n, m) with lengths in [an/s, bn/s). Then, for every integer r ≥ 0, 𝔼 Z̃_{n}(I)\underline{r} → λ(I)^{r}, where λ(I) = ∫_{I} \frac{1}{2x}e^{2x} dx. The result extends to joint factorial moments of several Z̃_{n}(I_{i}) for disjoint intervals I_{i}.

Proof. Z̃_{n}(I) = ∑_{an/s≤k<bn/s} Z̃(k) and thus, by (12),

𝔼 Z̃_{n}(I) = ∑_{an/s≤k<bn/s} z̃(k) → ∫_{a}^{b} e^{2x} \frac{dx}{2x} = λ(I).  (17)

In order to treat higher moments, we observe that Z̃_{n}(I)\underline{r} is the number of r-tuples (C_{1}, …, C_{r}) of distinct cycles with the correct lengths. The expected number of such r-tuples with all cycles disjoint is easily shown to converge to λ(I)^{r} by a straight-forward generalization of the calculation (17) for the expectation. This extends to the case of several intervals too.

It thus remains to show that the expected number of such r-tuples (C_{1}, …, C_{r}) with at least two cycles intersecting tends to zero. Consider for simplicity the case when the union C_{1} ∪ ⋯ ∪ C_{r} is connected, and let μ_{1} be the expected number of such r-tuples (C_{1}, …, C_{r}); the general case follows in the same way by considering the components of the union C_{1} ∪ ⋯ ∪ C_{r} separately. Up to a factor of at most r!, we may further assume that the cycles are ordered such that C_{i} ∩ (C_{1} ∪ ⋯ ∪ C_{i−1}) ≠ ∅ for 2 ≤ i ≤ r. Then C_{1} ∪ C_{2} is obtained by adding to C_{1} some number w_{2} ≥ 1 of paths P_{21}, …, P_{2w_{2}}, each having two, not necessarily distinct, endpoints in C_{1}. Similarly, C_{1} ∪ C_{2} ∪ C_{3} is obtained by adding some further paths P_{31}, …, P_{3w_{3}} with endpoints in C_{1} ∪ C_{2}, where w_{3} ≥ 0, and so on. Let k_{i} = |C_{i}| and let l_{ij} ≥ 0 be the number of new vertices in P_{ij}; thus P_{ij} contains l_{ij} + 1 edges. Further, let W = ∑_{i=2}^{r} w_{i} and L = ∑_{i=2}^{r} ∑_{j=1}^{w_{i}} l_{ij}. Note that C_{1} ∪ ⋯ ∪ C_{r} has k_{1} + L vertices and k_{1} + L + W edges; in particular k_{1} + L + W ≤ ∑_{i=1}^{r} k_{i} ≤ rbn/s.

We estimate the expected number of such r-tuples with given k_{1}, (w_{i})_{i} and (l_{ij})_{ij}. First, the cycle C_{1} may be chosen in n\underline{k_{1}} \frac{1}{2k_{1}} < k_{1}^{−1}n^{k_{1}} ways. Next, for i ≥ 2 and each choice of C_{1}, …, C_{i−1}, the endpoints of P_{ij} may be chosen in |C_{1} ∪ ⋯ ∪ C_{i−1}|^{2} ≤ (rbn/s)^{2} ways, and the l_{ij} internal points in at most n^{l_{ij}} ways. Hence the total number of choices of C_{1}, …, C_{r} is at most

\frac{1}{k_{1}} n^{k_{1}+L}(rbn/s)^{2W} .  (18)

For each such choice, the probability that the k_{1} + L + W edges in the union C_{1} ∪ ⋯ ∪ C_{r} belong to G(n, m) is at most

(\frac{m}{\binom{n}{2}})^{k_{1}+L+W} = n^{−k_{1}−L−W} (1 + \frac{2s + 1}{n − 1})^{k_{1}+L+W} ≤ n^{−k_{1}−L−W} (1 + \frac{3s}{n})^{rbn/s}. (19)

By (18) and (19), the expected number of r-tuples with given k_{1}, (w_{i})_{i} and (l_{ij})_{ij} is at most

\frac{c}{k_{1}} n^{−W} (rbn/s)^{2W} ,

for some constant c (depending on b and r).

Moreover, l_{ij} ≤ k_{i} ≤ bn/s, so given w_{2}, …, w_{r}, there are at most (bn/s)^{W} choices of (l_{ij})_{ij}. Consequently, the expected number μ′ is at most, for large n,

r! ∑_{k_{1}=an/s}^{bn/s} ck_{1}^{−1} ∑_{\begin{matrix}w_{2}≥1 \\ w_{3},...,w_{r}≥0 \end{matrix}}(\frac{r^{2}b^{3}n^{2}}{s^{3}} )^{w_{2}+···+w_{r}} ≤ c′ \frac{b}{a} \frac{r^{2}b^{3}n^{2}}{s^{3}} = o(1).

Proof of Theorem 10. For simplicity we assume that a_{n} = |s|/n, and thus α = ±1; the general case follows by a simple rescaling argument. If s < 0, there is a.a.s. no multicyclic component and the result follows by restricting Theorem 8 to (0, ∞) × [0, ∞], using Lemma 1(i).

Thus assume s > 0 and a_{n} = s/n, which implies α = 1. Let Ξ′′_{n} = \{(\frac{s}{n}|C̃_{i}|, \frac{s^{2}}{n^{2}} |Ũ_{i}|)\}, let Ξ̃ be the claimed limit process Ξ̃_{2α} = Ξ̃_{2} and let μ denote its intensity measure. By (4), the restriction of μ to (0, ∞)^{2} equals the intensity measure of Ξ̂ in Theorem 8; note further that, by the construction of Ξ̃_{λ}, for I ⊂ (0, ∞),

μ(I × [0, ∞]) = ∫_{I} \frac{1}{2x}e^{2x} dx.  (20)

Let R be the family of all rectangles in 𝔖 = (0, ∞) × [0, ∞] of the form [a, b) × [c, d) or [a, b) × [c, ∞] with 0 < a < b < ∞ and 0 ≤ c < d < ∞. As in the proof of Theorem 8, it follows from [11, Theorem 4.2] that it suffices to show that Ξ′′_{n}(R_{k}) →^{d} Ξ̃(R_{k}), jointly, for any finite family of rectangles R_{k} ∈ R. By subdividing the rectangles, and perhaps adding some, it suffices to consider the case {R_{k}} = {I_{i} × J_{j}}_{1≤i≤p, 1≤j≤q+1}, where p and q are integers, I_{i} = [a_{i−1}, a_{i}), i = 1, …, p, and J_{j} = [b_{j−1}, b_{j}), j = 1, …, q, while J_{q+1} = [b_{q}, ∞], for some numbers 0 < a_{0} < a_{1} ⋯ < a_{p} < ∞ and 0 = b_{0} < b_{1} ⋯ < b_{q} < ∞. We thus want to show that then

(Ξ′′_{n}(I_{i} × J_{j}))_{i=1, j=1}^{p, q+1} →^{d} (Ξ̃(I_{i} × J_{j}))_{i=1, j=1}^{p, q+1}.  (21)

Writing R_{ij} = I_{i} × J_{j} and R_{i}^{∗} = ⋃_{j=1}^{q+1} R_{ij} = I_{i} × [0, ∞], (21) is equivalent to

(Ξ′′_{n}(R_{ij}))_{i=1, j=1}^{p, q} ∪ (Ξ′′_{n}(R_{i}^{∗}))_{i=1}^{p} →^{d} (Ξ̃(R_{ij}))_{i=1, j=1}^{p, q} ∪ (Ξ̃(R_{i}^{∗}))_{i=1}^{p}.

We make one further preliminary modification. Let, as in the proof of Theorem 8, Ξ_{n} be defined as Ξ′′_{n} but counting cycles in unicyclic components only. A.a.s. there is only one multicyclic component and it has order at least s (indeed, the order is 4s+o_{p}(s)) [15], [10, Theorem 5.12]. Since s ≫ n^{2/3} and thus s > b_{q}n^{2}/s^{2} for large n, it follows that ℙ(Ξ′′_{n}(R_{ij}) ≠ Ξ_{n}(R_{ij})) → 0 for every i and j ≤ q. Consequently, it suffices to show that

(Ξ_{n}(R_{ij}))_{i=1, j=1}^{p, q} ∪ (Ξ′′_{n}(R_{i}^{∗}))_{i=1}^{p} →^{d} (Ξ̃(R_{ij}))_{i=1, j=1}^{p, q} ∪ (Ξ̃(R_{i}^{∗}))_{i=1}^{p}.  (22)

We prove (22) using an unusual version of the method of moments. Define, for non-negative integers r_{1}, …, r_{q}, r, the polynomial

p_{r_{1},...,r_{q},r}(x_{1}, …, x_{q}, y) = x\underline{r_{1}} ; 1 ⋯ x\underline{r_{q}} ; q(y − ∑_{i=1}^{q} r_{i})\underline{r}.

We will show that, for any non-negative integers r_{ij} and r_{i},

𝔼 ∏_{i=1}^{p} p_{r_{i1},...,r_{iq},r_{i}}(Ξ_{n}(R_{i1}), …, Ξ_{n}(R_{iq}), Ξ′′_{n}(R_{i}^{∗}))

→ 𝔼 ∏_{i=1}^{p} p_{r_{i1},...,r_{iq},r_{i}}(Ξ̃(R_{i1}), …, Ξ̃(R_{iq}), Ξ̃(R_{i}^{∗})). (23)

Since the polynomials p_{r_{1},...,r_{q},r} form a basis of the linear space of all polynomials in x_{1}, …, x_{q}, y, it then follows that all mixed moments of (Ξ_{n}(R_{ij}))_{1,1}^{p,q} ∪

(Ξ′′_{n}(R_{i}^{∗}))_{1}^{p} converge to the corresponding moments for Ξ̃, and (22) follows by the method of moments.

To show (23), we observe that the product on the left hand side equals the number of families (C_{ijk})_{1≤i≤p, 1≤j≤q, 1≤k≤r_{ij}} ∪ (C̃_{ik})_{1≤i≤p, 1≤k≤r_{i}} of distinct cycles, such that each C_{ijk} lies in a unicyclic component U_{ijk}, and \frac{s}{n}|C_{ijk}| ∈ I_{i}, \frac{s^{2}}{n^{2}} |U_{ijk}| ∈ J_{j}, \frac{s}{n}|C̃_{ik}| ∈ I_{i}.

First, ignoring the C̃_{ik}, the expected number of such families (C_{ijk})_{ijk} converges by the proof of Theorem 8 (extended to include the case c_{i} = 0) to ∏_{i=1}^{p} ∏_{j=1}^{q} μ(R_{ij})^{r_{ij}}.

Next, suppose we are given a family (U_{ijk})_{ijk} of disjoint unicyclic subgraphs of K_{n} such that \frac{s}{n}|C_{ijk}| ∈ I_{i} and \frac{s^{2}}{n^{2}} |U_{ijk}| ∈ J_{j}, where C_{ijk} is the unique cycle in U_{ijk}. Conditioned on the event that each U_{ijk} is a component of G(n, m), the expected number of families (C̃_{ik})_{i=1, k=1}^{p, r_{i}} of cycles that are distinct from each other and from all C_{ijk}, and with \frac{s}{n}|C̃_{ik}| ∈ I_{i}, equals the expected number of families (C̃_{ik})_{i=1, k=1}^{p, r_{i}} of distinct cycles with such sizes in G(n − L, m − L), where L = ∑_{ijk} |U_{ijk}|. Since L = O(n^{2}/s^{2}) = o(s), it follows from Lemma 6 that, uniformly over all choices of (U_{ijk})_{ijk} with given p, q and r_{ij}, the expected number of (C̃_{ik})_{ik} is ∏_{i=1}^{p} λ(I_{i})^{r_{i}} + o(1), where by (20) λ(I_{i}) = ∫_{I_{i}} \frac{1}{2x}e^{2x} dx = μ(R_{i}^{∗}).

Consequently,

𝔼 ∏_{i=1}^{p} p_{r_{i1},...,r_{iq},r_{i}}(Ξ_{n}(R_{i1}), …, Ξ_{n}(R_{iq}), Ξ′′_{n}(R_{i}^{∗}))

→ ∏_{i=1}^{p}(∏_{j=1}^{q} μ(R_{ij})^{r_{ij}} · μ(R_{i}^{∗})^{r_{i}}). (24)

It remains to verify that the right hand sides of (23) and (24) coincide. Since the variables Ξ̃(R_{ij}) are independent, it suffices to consider a single i and show, changing the notation, that if X_{j} ∼ Po(μ_{j}), j = 1, …, q + 1, are independent Poisson random variables and r_{1}, …, r_{q}, r ≥ 0, then

𝔼 X\underline{r_{1}} ; 1 ⋯ X\underline{r_{q}} ; q(∑_{j=1}^{q+1} X_{j} − ∑_{j=1}^{q} r_{j})\underline{r} = μ_{1}^{r_{1}} ⋯ μ_{q}^{r_{q}}(∑_{1}^{q+1} μ_{j})^{r}.  (25)

This can be verified by taking the derivative (∂/∂u)^{r}|_{u=0} ∏_{1}^{q+1}(∂/∂t_{j})^{r_{j}}|_{t_{j}=0}, with r_{q+1} = 0, of the generating function

𝔼 ∏_{j=1}^{q+1}(1 + t_{j} + u)^{X_{j}} = exp(∑_{i=1}^{q+1} μ_{i}(t_{i} + u)).

(Alternatively, (25) is easily verified using the binomial theorem for fractional powers [8, Exercise 5.37], or by interpreting the left hand side combinatorically and using simple Poisson process properties.) This completes the proof of (23), and thus of the theorem.

Proof of Theorem 1(ii),(iii). In the case m = n/2 − s, the set {C_{i}^{∗}} is a.a.s. empty, and there is nothing to prove.

Thus assume m = n/2 + s, and let, as in the proof of Theorem 10, Ξ′′_{n} = \{(\frac{s}{n}|C̃_{i}|, \frac{s^{2}}{n^{2}} |Ũ_{i}|)\} and Ξ̃ = Ξ̃_{2}; Theorem 10 shows Ξ′′_{n} →^{d} Ξ̃.

Further, let Ξ_{n} = \{(\frac{s}{n}|C̃_{i}|, \frac{s^{2}}{n^{2}} |Ũ_{i}|) : Ũ_{i} is unicyclic\} and Ξ_{n}^{∗} = \{(\frac{s}{n}|C̃_{i}|, \frac{s^{2}}{n^{2}} |Ũ_{i}|) : Ũ_{i} is multicyclic}; thus Ξ′′_{n} = Ξ_{n} ∪ Ξ_{n}^{∗}.

We will separate the points in Ξ_{n} and Ξ_{n}^{∗} from each other using the sizes of the corresponding components. Thus, for any u < ∞, define the restrictions Ξ_{nu} = Ξ′′_{n}|_{(0,∞)×[0,u]} and Ξ_{nu}^{∗} = Ξ′′_{n}|_{(0,∞)×[u,∞]}. Similarly, define Ξ̃_{u} = Ξ̃|_{(0,∞)×[0,u]}, Ξ̃_{u}^{∗} = Ξ̃|_{(0,∞)×[u,∞]} and Ξ̂ = Ξ̃|_{(0,∞)×[0,∞)}, Ξ̂^{∗} = Ξ̃|_{(0,∞)×{∞}}. We regard all these as point processes on (0, ∞) × [0, ∞].

By Lemma 2, the mapping Φ : ν ↦ (ν|_{(0,∞)×[0,u]}, ν|_{(0,∞)×[u,∞]}) is a measurable map 𝔑((0, ∞) × [0, ∞]) → 𝔑((0, ∞) × [0, u]) × 𝔑((0, ∞) × [u, ∞]) which is continuous at every ν with ν((0, ∞) × {u}) = 0. Since the embeddings (0, ∞) × [0, u] → (0, ∞) × [0, ∞] and (0, ∞) × [u, ∞] → (0, ∞) × [0, ∞] are proper, Lemma 3 shows that the same holds if we regard Φ as a mapping into 𝔑((0, ∞) × [0, ∞])^{2}.

For any fixed u < ∞, Ξ̃((0, ∞) × {u}) = 0 a.s., since the intensity measure is absolutely continuous on (0, ∞)^{2} by (4). Consequently, Φ is a.s. continuous at Ξ̃, and Theorem 10 implies, see [4, Theorem 5.1],

(Ξ_{nu}, Ξ_{nu}^{∗}) →^{d} (Ξ̃_{u}, Ξ̃_{u}^{∗}) as n → ∞,  (26)

for any fixed u < ∞.

Moreover, cf. the proof of Theorem 6,

𝔼 Ξ̃((0, ∞) × (1, ∞)) = ∫_{1}^{∞} \frac{1}{4x}e^{−2x} < ∞

and thus a.s. Ξ̃ has only a finite number of points in ((0, ∞) × (1, ∞)); hence, for all large u we have Ξ̃_{u} = Ξ̂ and Ξ̃_{u}^{∗} = Ξ̂^{∗}. In particular, as u → ∞,

(Ξ̃_{u}, Ξ̃_{u}^{∗}) → (Ξ̂, Ξ̂^{∗})  (27)

a.s., and thus in distribution.

Furthermore, let U_{1} be the largest unicyclic component and let V be the smallest multicyclic component (i.e., a.a.s. the unique giant component). If |U_{1}| < un^{2}/s^{2} < |V |, then Ξ_{nu} = Ξ_{n} and Ξ_{nu}^{∗} = Ξ_{n}^{∗}. Thus, using Theorem 6 and the fact that a.a.s. |V | > s > un^{2}/s^{2}, see the proof of Theorem 10,

lim sup_{n→∞} ℙ((Ξ_{nu}, Ξ_{nu}^{∗}) ≠ (Ξ_{n}, Ξ_{n}^{∗}))

≤ lim sup_{n→∞} ℙ(|U_{1}| ≥ un^{2}/s^{2}) + lim sup_{n→∞} ℙ(|V | ≤ un^{2}/s^{2})

= ℙ(ξ′_{1} ≥ u) + 0, (28)

which tends to 0 as u → ∞. Hence, (26), (27) and (28) imply, see [4, Theorem 4.2],

(Ξ_{n}, Ξ_{n}^{∗}) →^{d} (Ξ̂, Ξ̂^{∗}) as n → ∞.  (29)

Next we project the processes onto (0, ∞), using the map π(x, y) = x. By (29) and Lemma 3 we have

(\{\frac{s}{n}|C_{i}|\}, \{\frac{s}{n}|C_{i}^{∗}|\}) = ((π(Ξ_{n}), π(Ξ_{n}^{∗})) →^{d} (π(Ξ̂), π(Ξ̂^{∗})).

as pairs of processes on (0, ∞). By construction, Ξ = π(Ξ̂) and Ξ^{∗} = π(Ξ̂^{∗}) are independent Poisson processes with the intensities \frac{1}{2x}e^{−2x} and \frac{1}{2x}(e^{2x} − e^{−2x}), respectively, see (4) and (5), as asserted in the theorem.

We have shown the asserted joint convergence, but only as processes on (0, ∞). To extend this to (0, ∞] and [0, ∞), we use Lemma 1. Observe that for any two disjoint sets 𝔖_{1} and 𝔖_{2}, there is a natural homeomorphism 𝔑(𝔖_{1})× 𝔑(𝔖_{2}) ≡ 𝔑(𝔖_{1} ∪ 𝔖_{2}); hence the claimed joint convergence can be regarded as convergence of point processes on the disjoint union of (0, ∞] and [0, ∞), i.e. on 𝔖 = (0, ∞] × {0} ∪ [0, ∞) × {1}. We have shown convergence on the subset 𝔖′ = (0, ∞) × {0, 1}, and it is easily seen that the additional assumption in Lemma 1 follows from the two conditions

lim_{N→∞} lim sup_{n→∞} ℙ(π(Ξ_{n})(N, ∞] ≠ 0) = 0,  (30)
lim_{ε→0} lim sup_{n→∞} ℙ(π(Ξ_{n}^{∗})[0, ε) ≠ 0) = 0.  (31)

or, equivalently, if the cycles are ordered as in Theorem 2,

lim_{N→∞} lim sup_{n→∞} ℙ(\frac{s}{n}|C_{1}| > N) = 0,  (32)
lim_{ε→0} lim sup_{n→∞} ℙ(\frac{s}{n}|C_{1}^{∗}| < ε) = 0.  (33)

The statement (32) is implicitly verified in the proof of Theorem 8, and follows directly from Theorem 2(i). Similarly, (33) follows from the fact that \frac{s}{n}C_{1}^{∗} converges in distribution to a strictly positive random variable, as follows from the not yet proved Theorem 2(ii). This fact is proved by Łuczak [16], and our proof is complete. Alternatively, in order to obtain a self-contained proof, we use Lemma 7 below and estimate, for some c > 0 and 0 < ε ≤ 1,

𝔼(π(Ξ_{n}^{∗})[0, ε)) = ∑_{k<εn/s} z^{∗}(k) ≤ cε,

which proves (31).

Lemma 7. Consider G(n, m) with m = n/2 + s, n^{2/3} ≪ s ≪ n. Let z^{∗}(k) = z̃(k) − ∑_{l} z(k, l) be the expected number of cycles of length k in multicyclic components. Then, uniformly for k ≤ n/s, z^{∗}(k) = O(s/n).

Proof. First, for the total number of cycles of length k ≤ n/s, (10) easily yields

z̃(k) ≤ \frac{n^{k}m^{k}}{2k\binom{n}{2}^{k}} = \frac{1}{2k} (1 + \frac{2s + 1}{n − 1})^{k} = \frac{1}{2k} (1 + O(\frac{ks}{n})) = \frac{1}{2k} + O(\frac{s}{n}). (34)

For the cycles in unicyclic components we sum z(k, l) given by (11). If l ≤ n^{2}/s^{2}, it is easy to verify that (11) yields

z(k, l) = \frac{l\underline{k}}{l^{k}} \frac{l^{l−1}}{2l!} exp(−l − O(ls^{2}/n^{2})) = a(k, l)e^{−l} exp(−O(ls^{2}/n^{2})), (35)

where

a(k, l) = \frac{l\underline{k}}{l^{k}} \frac{l^{l−1}}{2l!} = \frac{l^{l−k−1}}{2(l − k)!}.

Then F_{k}(z) = ∑_{l=k}^{∞} a(k, l)z^{l} is the exponential generating function for connected unicyclic graphs with a k-cycle, and F_{k}(z) = \frac{1}{2k}T (z)^{k}, where T (z) = ∑_{1}^{∞} \frac{l^{l−1}}{l!} z^{l} is the tree function. In particular, ∑_{l=k}^{∞} a(k, l)e^{−l} = F_{k}(e^{−1}) = 1/2k, since T (e^{−1}) = 1. Moreover, Stirlings formula yields a(k, l) ≤ l^{l−1}/l! ≤ l^{−3/2}e^{l} for all l. Consequently, (35) yields

\frac{1}{2k} − ∑_{l} z(k, l) = ∑_{l=k}^{∞}(a(k, l)e^{−l} − z(k, l))

≤ ∑_{l=1}^{n^{2}/s^{2}} a(k, l)e^{−l}c\frac{ls^{2}}{n^{2}} + ∑_{n^{2}/s^{2}}^{∞} a(k, l)e^{−l}

≤ c\frac{s^{2}}{n^{2}} ∑_{l=1}^{n^{2}/s^{2}} l^{−1/2} + ∑_{n^{2}/s^{2}}^{∞} l^{−3/2} ≤ c′ \frac{s}{n}.

The result follows by combining this and (34). Remark 6. The limit (29) (and another application of Lemma 1) shows joint convergence for the results in Theorem 8 and Theorem 1(ii). Proof of Theorem 2(ii),(iii). This is an immediate consequence of Theorem 1 and Lemma 4.

Proof of Corollary 3. Directly from Theorem 2(i)(ii); for example,

ℙ(ξ_{1} ≤ a) = ℙ(Ξ(a, ∞) = 0) = exp(− ∫_{a}^{∞} \frac{1}{2x}e^{−2x} dx)

which by a change of variable yields the stated formula.

The calculation of the densities (1) and (2) is similar and left to the reader.

Proof of Corollary 4. By (1) or Corollary 3, ξ_{1} has the density f(x) = \frac{e^{−2x}}{2x} exp(− ∫_{2x}^{∞} \frac{1}{2y}e^{−y} dy). Hence, by the second formula in Corollary 3, and the independence in Theorem 2,

\begin{aligned}ℙ(ξ_{1}^{∗} > ξ_{1}) & = ∫_{0}^{∞} ℙ(ξ_{1}^{∗} > x)f(x) dx \\ & = ∫_{0}^{∞} \frac{e^{−2x}}{2x} exp(− ∫_{2x}^{∞} \frac{1}{2y} e^{−y} dy − ∫_{0}^{2x} \frac{sinh y}{y} dy), \end{aligned}

which yields the stated formula by a change of variable. The integral was numerically evaluated by Maple.

Proof of Theorem 11. This is an easy consequence of another Poisson limit result for cycles, which is well-known and goes back to the fundamental paper by Erdős and Rényi [7]: For each fixed k ≥ 3 (and m as in this paper), the cycle count Z̃(k) →^{d} Po(1/2k); moreover, the convergence holds jointly for any finite family k = 3, …, N.

Let p_{n}[a, b] be the probability that for some k with a ≤ k ≤ b, G(n, m) has two cycles of the same length k in unicyclic components. If N is fixed, there are a.a.s. no cycles of length ≤ N outside unicyclic components, see Theorem 2(ii). Hence, the joint Poisson convergence of the cycle counts implies that, with W_{k} ∈ Po(1/2k) independent,

p_{n}[3, N] → ℙ( max_{3≤k≤N} W_{k} ≥ 2) = 1 − ∏_{k=3}^{N} ℙ(W_{k} ≤ 1) = 1 − ∏_{k=3}^{N}(1 + \frac{1}{2k} )e^{−1/2k}. (36)

Next, let B be a positive constant. Then, if C_{1} is the longest cycle in a unicyclic component, by Theorem 2(i),

p_{n}[Bn/s, n] ≤ ℙ(|C_{1}| ≥ Bn/s) → ℙ(ξ_{1} ≥ B).

Furthermore, for k ≤ Bn/s, the expected number of ordered pairs of disjoint cycles of length k is at most, using (12),

z̃_{n,m}(k)z̃_{n−k,m−k}(k) = \frac{e^{4ks/n+o(1)}}{4k^{2}} ,

and thus, for n large,

p_{n}[N + 1, Bn/s] ≤ ∑_{k=N+1}^{Bn/s} z̃_{n,m}(k)z̃_{n−k,m−k}(k) ≤ ∑_{N+1}^{∞} \frac{e^{4B}}{k^{2}} ≤ \frac{e^{4B}}{N} .

Consequently,

lim sup_{n→∞} |p_{n}[3, n] − p_{n}[3, N]| ≤ lim sup_{n→∞} p_{n}[N + 1, Bn/s] + lim sup_{n→∞} p_{n}[Bn/s, n]

≤ e^{4B}N^{−1} + ℙ(ξ_{1} > B). (37)

Let, for 3 ≤ k ≤ ∞, q_{l} = 1 − ∏_{k=3}^{l}(1 + \frac{1}{2k})e^{−1/2k}. Then, by (36) and (37),

lim sup_{n→∞} |p_{n}[3, n] − q_{∞}| ≤ |q_{N} − q_{∞}| + e^{4B}N^{−1} + ℙ(ξ_{1} > B),

for every positive N and B. Letting first N → ∞ and then B → ∞, we see that the left hand side vanishes, and thus p_{n}[3, n] converges to q_{∞} as asserted. Finally, to find q_{∞} explicitly, we note that

∏_{k=3}^{l}(1+\frac{1}{2k} ) = ∏_{k=3}^{l} \frac{k + 1/2}{k} = \frac{Γ(l + 3/2)/Γ(3 + 1/2)}{Γ(l + 1)/Γ(3)} ∼ l^{1/2} \frac{Γ(3)}{Γ(7/2)} = \frac{16}{15π^{1/2}} l^{1/2}

while

∏_{k=3}^{l} e^{−1/2k} = exp(\frac{3}{4} − \frac{1}{2} ∑_{k=1}^{l} \frac{1}{k}) = exp(\frac{3}{4} − \frac{1}{2}(ln l + γ + o(1)))

and thus

1 − q_{∞} = lim_{l→∞} ∏_{k=3}^{l}(1 + \frac{1}{2k} )e^{−1/2k} = \frac{16}{15}π^{−1/2} exp(\frac{3}{4} − \frac{γ}{2} ).

6. Branching processes

In this and the following section, we give some heuristic arguments that at least suggest some of the results above. We have not attempted to make the arguments rigorous, and we will not try to justify any approximations. For simplicity, we consider instead of G(n, m) the random graph G(n, p) with p = 1/n + 2s/n^{2}, where s is positive or negative with n^{2/3} ≪ |s| = o(n), cf. Remark 3.

We begin with the well-known branching process approximation for component sizes, cf. [10, Section 5.2].

Condition on the existence of a specific k-cycle C. We explore the component containing C step by step as follows. First, we mark the k vertices in C as found. Next, we expose all remaining edges incident to any of them, and mark the other endpoint of each of these edges as found. We continue this process repeatedly, until the entire component is found.

When l vertices are found, the number of new vertices found when exposing the edges at the next vertex has a binomial distribution Bi(n − l, p), with expectation (n − l)p = 1 + 2s/n + O(l/n). We approximate this binomial distribution by a Poisson distribution Po(1+2s/n). Hence, the number of new vertices found at each step is approximated by a (Galton–Watson) branching process, with k initial individuals and the offspring distribution Po(1 + 2s/n). The component size is approximated by the total progeny of this branching process.

If s > 0, this is a supercritical branching process, which has a positive probability of growing for ever. Of course, the component containing C cannot be larger than n, and the approximation above breaks down when a large number of vertices are found, but indefinite growth of the branching process corresponde to C belonging to a very large component, i.e. to the giant component, while extinction corresponds to C belonging to a relatively small component, which then is unicyclic (since a.a.s. only the giant component is multicyclic).

The probability q of extinction of the branching process with offspring distribution Po(1 + 2s/n) and one initial individual is given by the standard equation

q = exp((q − 1)(1 + \frac{2s}{n})),

see e.g. [3, Theorem I.5.1], which yields

q − 1 = (q − 1)(1 + \frac{2s}{n}) + \frac{1}{2}(q − 1)^{2} + o((q − 1)^{2}),
1 = (1 + \frac{2s}{n}) + \frac{1}{2}(q − 1) + o(q − 1),

and, finally,

1 − q = \frac{4s}{n}(1 + o(1)).

With k initial points, as above, the extinction probability is, for k = O(n/s),

q^{k} = (1 − (4 + o(1))s/n)^{k} = e^{−4ks/n+o(1)}.  (38)

The expected number of cycles of length k = xn/s is by (12) ∼ \frac{1}{2k}e^{2x}, and by (38) we expect that the expected number in unicyclic components is e^{−4x} times that, i.e. ∼ \frac{1}{2k}e^{−2x}, and consequently that the expected number in the giant component is ∼ \frac{1}{2k}(e^{2x} − e^{−2x}), in accordance with Theorem 1.

Turning to the sizes of the unicyclic components, consider first the case s < 0. Then the branching process is subcritical and a.s. dies out. The expected total progeny of a single initial individual is

∑_{i=0}^{∞}(1 + \frac{2s}{n})^{i} = ∑_{i=0}^{∞}(1 − \frac{2|s|}{n})^{i} = \frac{n}{2|s|}.

Consequently, we expect that a unicyclic component with a cycle of length k = Θ(n/s) has Θ(kn/s) = Θ(n^{2}/s^{2}) vertices.

In the supercritical case s > 0, we obtain the same result if we conditionthe branching process on extinction, since a branching process with offspring distribution Po(1 + 2s/n) conditioned on extinction is a branching process with offspring distribution Po(q(1+2s/n)), with q as above, and q(1+2s/n) ≈ 1−2s/n.

Hence, for both positive and negative s we expect that the largest unicyclic components should be of order n^{2}/s^{2}, as shown in detail in Theorem 6.

For the distribution of the sizes of the unicyclic components, one could similarly study the distribution of the total progeny in the branching processes, but the method in the next section seems more instructive and we do not pursue this further.

7. Brownian motion heuristics

As in Section 6, we condition on the existence of a specific k-cycle and explore the component it belongs to, but this time we expose the edges incident to one vertex at a time, and will use a Brownian motion approximation. Note that similar arguments have been used in a rigorous way by Aldous [1] to study components in the critical case s = O(n^{2/3}); presumably similar methods could be used to make our argument too rigorous.

Thus, let X_{0} = k and let X_{i} be the number of vertices found to belong to the component when the neighbourhoods of i vertices have been exposed, for i = 1, …, M, where M is the component size. Thus X_{i} > i for i < M while X_{M} = M. As above, we approximate X_{i} − X_{i−1} by independent Po(1 + 2s/n) variables. These have mean 1 + 2s/n and variance 1 + 2s/n ∼ 1, and thus, given some positive scaling factors a_{n} → 0, we may approximate

−a_{n}(X_{⌊a_{n}^{−2}t⌋} − X_{0} − a_{n}^{−2}t(1 + 2s/n))

by a standard Brownian motion B_{t}, cf. Donsker’s theorem [4].

We thus approximate X_{u} (defined for integers u ≤ M) by

X′_{u} = k + (1 + 2s/n)u − a_{n}^{−1}B_{a_{n}^{2}u}

(defined for all real u ≥ 0); hence we approximate the component size

M = min{i : X_{i} = i}

by

min{u : X′_{u} = u} = min{u : a_{n}^{−1}B_{a_{n}^{2}u} = k + 2us/n}
= a_{n}^{−2} min{t : a_{n}^{−1}B_{t} = k + 2a_{n}^{−2}ts/n}
= a_{n}^{−2} min{t : B_{t} = a_{n}k + 2a_{n}^{−1}ts/n}.

Assuming a_{n}^{−1}s/n → α ≠ 0 and a_{n}k = x, we thus approximate a_{n}^{2}M by min{t : B_{t} = x + 2αt} = T_{x,−2α}, cf. (3). This approximation is in accordance with Theorem 10, including the case T_{x,−2α} = ∞ (possible when s > 0), which is interpreted as a_{n}^{2}M being ‘large’, which means that C belongs to the giant component.

8. Three symmetry rules

Finally, we remark that the arguments in the two preceding sections show that there are close connections between the following three well-known ‘symmetry rules’:

Random graph symmetry rule. If n^{2/3} ≪ s ≪ n, then G(n, n/2 + s) with its giant component deleted looks roughly the same as G(n, n/2 − s). (For a precise formulation, see e.g. [15, 10].) In the present paper this is reflected in that the asymptotic results for m = n/2 + s and m = n/2 − s coincide for the unicyclic components and the cycles in them.

Branching process symmetry rule. A supercritical Galton-Watson branching process with offspring distribution Po(λ), λ > 1, conditioned on extinction, coincides with a subcritical branching process with offspring distribution Po(λ′), where λ′ < 1 satisfies λ′e^{−λ′} = λe^{−λ}. More generally, every supercritical branching process conditioned on extinction is equivalent to a subcritical branching process with a suitable offspring distribution, see [3, Theorem I.12.3].

Brownian motion symmetry rule. If a, b > 0, then the hitting time T_{a,−b}, conditioned on being finite, has the same distribution as T_{a,b}. (An easy consequence of the Cameron–Martin formula; see further Section 3.)

References

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

[2] R. Arratia, A.D. Barbour & S. Tavaré, The Poisson–Dirichlet distribution and the scale invariant Poisson process. Combin. Probab. Comput. 8 (1999), 407–416.

[3] K.B. Athreya & P.E. Ney, Branching processes. Grundlehren math. Wiss. 196, Springer, Berlin, 1972.

[4] P. Billingsley, Convergence of Probability Measures. Wiley, New York, 1968.

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

[6] R. Engelking, General Topology. 2^{nd} ed., Heldermann, Berlin, 1989.

[7] P. Erdős & A. Rényi On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61.

[8] R.L. Graham, D.E. Knuth & O. Patashnik, Concrete Mathematics. 2^{nd} ed., Addison– Wesley, Reading, Mass., 1994.

[9] S. Janson, D.E. Knuth, T. Łuczak & B. Pittel, The birth of the giant component. Random Structures Algorithms 4:3 (1993), 233–358.

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

[11] O. Kallenberg, Point Processes. Akademie-Verlag, Berlin, 1983.

[12] J.F.C. Kingman, Random discrete distributions. J. Roy. Statist. Soc. B 37 (1975), 1–22.

[13] J.F.C. Kingman, Poisson Processes. Oxford Univ. Press, Oxford, 1993.

[14] V.F. Kolchin, On the behavior of a random graph near a critical point. (Russian) Teor. Veroyatnost. i Primenen. 31:3 (1986), 503–515; English transl. Theory Probab. Appl. 31:3 (1986), 439–451.

[15] T. Łuczak, Component behavior near the critical point of the random graph process. Random Structures Algorithms 1 (1990), 287–310.

[16] T. Łuczak, Cycles in a random graph near the critical point. Random Structures Algorithms 2 (1991), 421–440.

[17] 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, Budapest, 1996, pp. 399–422.

[18] 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.

[19] D. Revuz & M. Yor, Continuous Martingales and Brownian Motion. 3^{rd} ed., Springer, Berlin, 1999.

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

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