Cycles of given lengths in unicyclic components in sparse random graphs

Marc Noy Department of Mathematics, Universitat Politècnica de Catalunya
and Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech), Spain. [email protected] , Vonjy Rasendrahasina Ecole Normale Supérieure, Université d’Antananarivo, Madagascar. [email protected] , Vlady Ravelomanana IRIF, Université de Paris, France. [email protected] and Juanjo Rué Department of Mathematics, Universitat Politècnica de Catalunya
and Barcelona Graduate School of Mathematics (BgsMath), Spain. [email protected]

Abstract.

Let $L$ be subset of $\{3,4,\dots\}$ and let $X_{n,M}^{(L)}$ be the number of cycles belonging to unicyclic components whose length is in $L$ in the random graph $G(n,M)$ . We find the limiting distribution of $X_{n,M}^{(L)}$ in the subcritical regime $M=cn$ with $c<1/2$ and the critical regime $M=\frac{n}{2}\left(1+\mu n^{-1/3}\right)$ with $\mu=O(1)$ . Depending on the regime and a condition involving the series $\sum_{\ell\in L}z^{\ell}/(2\ell)$ , we obtain in the limit either a Poisson or a normal distribution as $n\to\infty$ .

MSC: Primary 05A16, 01C80; Secondary 05C10

Keywords: Random graphs, random variables, analytic combinatorics.

1. Introduction

A graph is unicyclic if it is connected and has a unique cycle. We say that a cycle in a graph is isolated if it is the unique cycle in a unicyclic connected component. Let $G(n,M)$ be the random graph with $n$ vertices and exactly $M$ edges drawn uniformly at random from the set of ${n\choose 2}$ possible edges. This is the model introduced in the seminal paper of Erdős and Rényi [3], in which each graph has the same probability

\binom{\binom{n}{2}}{M}^{-1}.

We are interested in the number of isolated cycles in $G(n,M)$ whose lengths are restricted to take certain values. More precisely, let $\mathbb{N}_{\geqslant 3}=\{3,4,\dots\}$ and $L$ a subset of $\mathbb{N}_{\geqslant 3}$ . We denote by $X_{n,M}^{(L)}$ the random variable equal to the number of isolated cycles in $G(n,M)$ whose lengths lie in $L$ . Our main result gives the limiting distribution of $X_{n,M}^{(L)}$ for various values of $M$ , corresponding to the so-called subcritical and critical regimes. Depending on the regime and a condition involving the generating function $\lambda(z)=\sum_{\ell\in L}z^{\ell}/(2\ell)$ , we obtain in the limit as $n\to\infty$ either a Poisson or a normal distribution.

The number of cycles in $G(n,M)$ has been studied since the appearance of [3]. When $M=cn$ , Erdős and Rényi showed [3, Theorem 3b] that the number of cycles of length $k$ converges to a Poisson law with parameter $(2c)^{k}/(2k)$ . Let $X_{n,\,M}$ be the random variable equal to the number of isolated cycles in $G(n,M)$ . When $M=cn$ and $c<1/2$ , asymptotically almost surely (that is, with probability tending to 1 as $n\to\infty$ ) all cycles are isolated. As a consequence we have

\lim_{n\to\infty}{\mathbb{E}}[X_{n,cn}]=\sum_{k\geqslant 3}\frac{(2c)^{k}}{2k}=\frac{1}{2}\log\frac{1}{1-2c}-c-c^{2}.

We next recall the different regimes for sparse random graphs (see for instance [7, 1]). The following results hold asymptotically almost surely (shortened to a.a.s.).

•

Subcritical regime. When $M=cn$ with $c<1/2$ , the connected components of $G(n,M)$ are either trees or unicyclic graphs.
•

Barely subcritical regime. When $M=\frac{n}{2}\left(1-\mu n^{-1/3}\right)$ with $\mu\to\infty$ and $\mu=o\left(n^{1/3}\right)$ ,
•

Critical regime. This is when $M=\frac{n}{2}\left(1+\mu n^{-1/3}\right)$ and $\mu=O(1)$ . In this regime the connected components of $G(n,M)$ are trees, unicyclic graphs, and complex components. A complex component is obtained from a connected cubic multigraph $K$ by performing the following operations: first replace edges in $K$ by induced paths of any length so that to obtain a simple graph $C$ , and then attach rooted trees to the vertices of $C$ .
•

Supercritical regime. When $M=cn$ with $c>1/2$ , there exists a unique component $L$ of linear size and the remaining components are either trees or unicyclic graphs. The ‘Symmetry principle’ (see [7, Section 5.6]) says that in this case $G(n.M)\backslash L$ in some sense ‘looks like’ a subcritical random graph with suitable parameters.

In the barely subcritical regime Kolchin showed that if $r_{0}=\frac{1}{6}\log n-\frac{1}{2}\log\mu$ , then the normalized random variable $(X_{n,M}-r_{0})/\sqrt{r_{0}}$ tends in distribution to a Gaussian law (see [8, Theorem 1.1.15]). In the critical regime, Flajolet, Knuth and Pittel [4, Corollary 6] showed that ${\mathbb{E}}[X_{n,M}]\sim\frac{1}{6}\log n$ . By the so-called symmetry property [7, Theorem 5.24], $X_{n,M}$ properly normalized should also be Gaussian when $M=\frac{n}{2}(1+\mu n^{-1/3})$ and $\mu\to\infty$ with $\mu=o(n^{1/3})$ .

Some results have been obtained fixing a set $L$ of positive integers as possible cycle lengths. Following [4], define an $L$ -cycle as an isolated cycle whose length is in $L$ . Let $X_{n,\,M}^{(L)}$ be the number of $L$ -cycles in $G(n,\,M)$ . It is shown in [4, Corollary 7] that if $\lim_{n\rightarrow\infty}\frac{2M}{n}=\lambda<1$ , then the probability that a graph (or multigraph) with $n$ vertices and $M$ edges has no $L$ -cycle is equal to

\sqrt{1-\lambda}\,\exp{\left(\sum_{l\geqslant 1,\ell\notin L}\frac{\lambda^{\ell}}{2l}\right)}+O\left(n^{-1/2}\right)=\exp{\left(-\sum_{l\geqslant 1,\ell\in L}\frac{\lambda^{\ell}}{2l}\right)}+O\left(n^{-1/2}\right).

(1)

Our results concern the distribution of the random variables $X_{n,M}^{(L)}$ . In particular, we obtain full limiting distributions both in the subcritical and the critical regimes.

Theorem 1.1.

Let $L\subseteq\mathbb{N}_{\geqslant 3}$ and set $\lambda_{L}(z)=\sum_{\ell\in L}\frac{z^{\ell}}{2\ell}$ , considered as a function of one complex variable in the unit disk $|z|<1$ . Let $X_{n,M}^{(L)}$ be the random variable equal to the number of $L$ -cycles in $G(n,M)$ . Then the following holds:

(A)

(Subcritical regime). Let $c=c(n)$ be such that $0<\limsup_{n\to\infty}c<1/2$ and $M=cn$ . Then

\frac{X_{n,\,M}^{(L)}}{\lambda_{L}(2c)}\mathbin{\stackrel{{\scriptstyle\mathop{d}}}{{\longrightarrow}}}\mathbin{\mathop{\mathrm{Poisson}}}\left(1\right),\quad\hbox{ as $n\to\infty$}.

(2)

(B)

(Barely subcritical regime). Let $M=\frac{n}{2}(1-\mu n^{-1/3})$ with $\lim\mu=+\infty$ and $\mu=o(n^{1/3})$ . Then two situations may happen: if $\lim_{n\to\infty}\lambda_{L}(\frac{2M}{n})<+\infty$ , then

\frac{X_{n,\,M}^{(L)}}{\lambda_{L}\left(\frac{2M}{n}\right)}\mathbin{\stackrel{{\scriptstyle\mathop{d}}}{{\longrightarrow}}}\mathbin{\mathop{\mathrm{Poisson}}}\left(1\right),\quad\hbox{ as $n\to\infty$}.

(3)

Otherwise, if $\lim_{n\to\infty}\lambda_{L}(\frac{2M}{n})=+\infty$ , then

\frac{X_{n,\,M}^{(L)}-\lambda_{L}\left(\frac{2M}{n}\right)}{\sqrt{\lambda_{L}\left(\frac{2M}{n}\right)}}\mathbin{\stackrel{{\scriptstyle\mathop{d}}}{{\longrightarrow}}}\mathcal{N}(0,1),\quad\hbox{ as $n\to\infty$}.

(4)

(C)

(Critical regime). Let $M=\frac{n}{2}(1+\mu n^{-1/3})$ , with $\mu=O(1)$ . Let $\alpha$ be the unique positive solution of $\mu=\frac{1}{\alpha}-\alpha$ . Then two situations may happen: if $\lim_{n\to\infty}\lambda_{L}(e^{-\alpha n^{-1/3}})<+\infty$ , then

\frac{X_{n,\,M}^{(L)}}{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}\mathbin{\stackrel{{\scriptstyle\mathop{d}}}{{\longrightarrow}}}\mathbin{\mathop{\mathrm{Poisson}}}\left(1\right),\quad\hbox{ as $n\to\infty$}.

(5)

Otherwise, if $\lim_{n\to\infty}\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)=+\infty$ , then

\frac{X_{n,\,M}^{(L)}-\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}{\sqrt{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}}\mathbin{\stackrel{{\scriptstyle\mathop{d}}}{{\longrightarrow}}}\mathcal{N}(0,1),\quad\hbox{ as $n\to\infty$}.

(6)

Points (A), (B) and (C) in Theorem 1.1 are the contents of Theorems 3.1, 3.2 and 3.4 given in the Section 3. We remark that in the previous statement there is no discontinuity between equations (2)–(3)–(5) and equations (4)–(6): the Taylor expansion of the term $e^{-\alpha n^{-1/3}}$ in the statement for the critical regime is equal to $1-\alpha n^{-1/3}+o(n^{-1/3})$ , which coincides with the term $1-\mu n^{-1/3}$ in the barely subcritical region.

The proofs are based on estimating coefficients of generating functions by means of Cauchy integrals along suitable contours and applying the saddle-point method.

Remarks. Observe that (1) follows directly from (2). Let us mention that technical refinements of our techniques would provide similar results for the region just before the supercritical regime, namely $M=\frac{n}{2}(1+\mu n^{-1/3})$ when $\mu\to\infty$ , $\mu=o(n^{1/12})$ . We do not include the analysis of this region because the computations become too involved.

Finally, one may wonder why in the previous theorem we do not have a corresponding result for the supercritical regime. The reason is that in this case our techniques, based on the detailed structure of $G(n,p)$ together with saddle-point estimates for the associated generating functions, do not apply in this situation. Given the Symmetry principle mentioned above, one should expect the number of $L$ -cycles in the supercritical regime follows a limit Poisson law as in the subcritical regime, but the tools provided by the Symmetry principle do no seem precise enough to prove such a statement.

2. Preliminaries and notation

All graphs considered in this paper are labelled. The size of a graph is the number of vertices. The excess of a graph $G$ is the number of vertices minus the number of edges. In $G(n,M)$ the excess is $M-n$ .

2.1. Analytic combinatorics of graphs

We use the language of analytic combinatorics as in [5]. Given a generating function $A(x)=\sum_{n\geqslant 0}a_{n}x^{n}$ , we write $[x^{n}]A(x)=a_{n}$ . If $A(x)=\sum_{n\geqslant 0}a_{n}x^{n}$ and $B(x)=\sum_{n\geqslant 0}b_{n}x^{n}$ , we write $A(x)\preceq B(x)$ if there exists $n_{0}$ such that $[x^{n}]A(x)\leqslant[x^{n}]B(x)$ for $n\geqslant n_{0}$ . All the generating functions that appear in this work are exponential generating functions of the form $\sum_{n\geqslant 0}a_{n}x^{n}/n!$ , or EGF for short (see [5, Chapter 2]).

We denote by $T(x)$ and $W_{-1}(x)$ the EGF of rooted and unrooted labelled trees, respectively. It is well known that

T(x)=xe^{T(x)}=\sum_{n=1}^{\infty}n^{n-1}\frac{x^{n}}{n!},\qquad W_{-1}(x)=T(x)-\frac{T(x)^{2}}{2}.

(7)

The EGF $W_{0}(x)$ of unicyclic graphs (connected graphs with $n$ vertices and $n$ edges) is given by (see for instance [6, Equation (3.5)])

W_{0}(x)=\sum_{k\geqslant 3}\frac{T(x)^{k}}{2k}=-\frac{1}{2}\log{(1-T(x))}-\frac{T(x)}{2}-\frac{T(x)^{2}}{4}.

(8)

We write $\lambda(t)=\sum_{k\geqslant 3}\frac{t^{k}}{2k}=-\frac{1}{2}\log(1-t)-{t}/{2}-{t^{2}}/{4}$ , so that $W_{0}(x)=\lambda(T(x))$ .

2.2. From Poisson parametrizations to central limit theorems

We include the following result by Kolchin that provides an approximation to a normal law by a Poisson parametrization.

Theorem 2.1 ([8, Theorem 1.1.15]).

Let $k=\lambda_{n}+\rho_{n}\sqrt{\lambda_{n}}$ . If $(1+\rho_{n})^{6}/\lambda_{n}\to 0$ as $n\to\infty$ then

e^{-\lambda_{n}}\frac{\lambda_{n}^{k}}{k!}=\frac{1}{\sqrt{2\pi\lambda_{n}}}e^{-\rho_{n}^{2}/2}\left(1+\frac{\rho_{n}^{3}-\rho_{n}}{6\sqrt{\lambda_{n}}}+O\left(\frac{1+\rho_{n}^{6}}{\lambda_{n}}\right)\right).

3. Proof of Theorem 1.1

We present separately the proof for each regime in Theorem 1.1. The main idea in all proofs is to encode the typical structure of random graphs in the regime under consideration using generating functions and then obtain large power estimates by means of saddle point bounds.

3.1. Subcritical regime

In this regime, the connected components of $G(n,M)$ are a.a.s. a set of acyclic graphs (a forest) together with a set of unicyclic graphs. We exploit this property in order to get the following result which refines the first statement in Theorem 1.1:

Theorem 3.1.

Let $c$ such that $0<c<1/2$ , and $M=cn$ . Let $L\subseteq\mathbb{N}_{\geqslant 3}$ and $\lambda_{L}(z)=\sum_{\ell\in L}\frac{z^{\ell}}{2\ell}$ . Then the random variable $X_{n,\,M}^{(L)}$ equal to the number of $L$ -cycles satisfies

\Pr\left[X_{n,\,M}^{(L)}=k\right]=e^{-\lambda_{L}(2c)}\frac{\lambda_{L}(2c)^{k}}{k!}\left(1+O\left(n^{-1}\right)\right).

Moreover, if $k\to\infty$ as $n\to\infty$ then

\Pr\left[X_{n,\,M}^{(L)}=k\right]=O(k^{-k}).

Proof.

It suffices to consider graphs whose connected components are trees and unicyclic graphs. Using the symbolic method we obtain that the probability that $G(n,M)$ contains exactly $k$ unicyclic components containing an $L$ -cycle is equal to

\Pr\left[X_{n,\,M}^{(L)}=k\right]=\frac{n!}{\binom{\binom{n}{2}}{M}}[x^{n}]\frac{W_{-1}(x)^{n-M}}{(n-M)!}\frac{\lambda_{L}(T(x))^{k}}{k!}e^{W_{0}(x)-\lambda_{L}(T(x))}\,.

(9)

The term $\frac{\lambda_{L}(T(x))^{k}}{k!}$ encodes the components containing an $L$ -cycle, while the term $e^{W_{0}(x)-\lambda_{L}(T(x))}$ encodes the rest of unicyclic components (whose lengths do not belong to $L$ ). Using Cauchy integral’s formula we get

	$\displaystyle[x^{n}]W_{-1}(x)^{n-M}\lambda_{L}(T(x))^{k}e^{W_{0}(x)-\lambda_{L}(T(x))}=$		(10)
	$\displaystyle\frac{2^{M-n}}{2\pi i}\oint\left(2W_{-1}(x)\right)^{n-M}\lambda_{L}(T(x))^{k}e^{W_{0}(x)-\lambda_{L}(T(x))}\frac{dx}{x^{n+1}}.$

After the change of variables $z=T(x)$ , it becomes

[x^{n}]W_{-1}(x)^{n-M}\lambda_{L}(T(x))^{k}e^{W_{0}(x)-\lambda_{L}(T(x))}=\frac{2^{M-n}}{2\pi i}\oint g(z)\lambda_{L}(z)^{k}e^{nh(z)}\frac{dz}{z}\,,

(11)

where

	$\displaystyle g(z)$	$\displaystyle=$	$\displaystyle(1-z)e^{\lambda(z)-\lambda_{L}(z)},$		(12)
	$\displaystyle h(z)$	$\displaystyle=$	$\displaystyle z-\log z+\left(1-\tfrac{M}{n}\right)\log\left(2z-z^{2}\right).$		(13)

Note that the function $h(z)$ given by (13) is exactly the same as [2, Equation (30)], which satisfies the conditions $h^{\prime}(2c)=h^{\prime}(1)=0$ . In the range $M=cn$ with $0<c<\frac{1}{2}$ , we can apply saddle-point methods by choosing a circular path $\{2ce^{i\theta},\theta\in[-\pi,\pi)\}$ as the contour of integration. As shown in [4], we split the integral in (11) into three parts, namely $\int_{-\pi}^{-\theta_{0}}+\int_{-\theta_{0}}^{\theta_{0}}+\int_{\theta_{0}}^{\pi}$ . It suffices to integrate from $-\theta_{0}$ to $\theta_{0}$ , for a convenient value of $\theta_{0}$ , because the remaining integrals can be bounded by the magnitude of the central integrand. Following the proof of [2, Theorem 3.2] and choosing $\theta_{0}=n^{-2/5}$ (so that $n\theta_{0}^{2}\to\infty$ but $n\theta_{0}^{3}\to 0$ as $n\to\infty$ ) we have

\exp\left(nh(2ce^{i\theta})\right)=\exp\left(nh(2c)-\tfrac{nc(1-2c)}{2(1-c)}\theta^{2}\right)\left(1+iO(n\theta^{3})+O(n\theta^{4})\right),

(14)

and for all choices of $\theta$ in $[-\pi,-\theta_{0}]\cup[\theta_{0},\pi)$ we have

\left|\exp\left(nh(2ce^{i\theta})-nh(2c)\right)\right|=\exp\left(-O(n^{1/5})\right).

(15)

As $2c<1$ in the vicinity of $\theta_{0}$ , we have

g\left(2ce^{i\theta}\right)=g(2c)\left(1+iO(\theta)+O(\theta^{2})\right),

(16)

and

\lambda_{L}(2ce^{i\theta})^{k}=\lambda_{L}(2c)^{k}\left(1+iO(\theta)+O(\theta^{2})\right)

(17)

for fixed $k\geqslant 0$ . Using expansions (14), (16), (17) and the bound (15) we have

\oint g(z)\lambda_{L}(z)^{k}e^{nh(z)}\frac{dz}{z}=i\int_{-\theta_{0}}^{\theta_{0}}g(2ce^{i\theta})\lambda_{L}(2ce^{i\theta})^{k}e^{nh(2ce^{i\theta})}d\theta\left(1+e^{-O(n^{1/5})}\right)

=ig(2c)\lambda_{L}(2c)^{k}e^{nh(2c)}\int_{-\theta_{0}}^{+\theta_{0}}e^{-n\sigma\tfrac{\theta^{2}}{2}}\cdot(1+iO(\theta)+O(\theta^{2})+iO(n\theta^{3})+O(n\theta^{4}))d\theta\left(1+e^{-O(n^{1/5})}\right),

\begin{split}\oint g(z)\lambda_{L}(z)^{k}e^{nh(z)}\frac{dz}{z}=i\int_{-\theta_{0}}^{\theta_{0}}g(2ce^{i\theta})\lambda_{L}(2ce^{i\theta})^{k}e^{nh(2ce^{i\theta})}d\theta\left(1+e^{-O(n^{1/5})}\right)\\ =ig(2c)\lambda_{L}(2c)^{k}e^{nh(2c)}\int_{-\theta_{0}}^{+\theta_{0}}e^{-n\sigma\tfrac{\theta^{2}}{2}}\cdot(1+iO(\theta)+O(\theta^{2})+iO(n\theta^{3})+O(n\theta^{4}))d\theta\left(1+e^{-O(n^{1/5})}\right),\end{split}

where $\sigma=\,{\frac{c\left(1-2c\right)}{1-c}}$ . If we set $x=\sqrt{n\sigma}\theta$ the integral in the above equation becomes

\frac{1}{\sqrt{n\sigma}}\int_{-\sigma^{1/2}n^{1/10}}^{\sigma^{1/2}n^{1/10}}e^{-\tfrac{x^{2}}{2}}\left(1+iO\left(\tfrac{x}{\sqrt{n\sigma}}\right)+O\left(\tfrac{x^{2}}{n\sigma}\right)+iO\left(n\tfrac{x^{3}}{\sqrt{n\sigma}^{3}}\right)+O\left(\tfrac{x^{4}}{n\sigma^{2}}\right)\right)dx.

(18)

Observe that $\sigma=O(1)$ and the estimate (18) is a real number (because (10) is a real number). Hence (18) is equal to

\frac{1}{\sqrt{\sigma n}}\int_{-\sigma^{1/2}n^{1/10}}^{\sigma^{1/2}n^{1/10}}e^{-\tfrac{x^{2}}{2}}\left(1+O\left(\frac{x^{2}}{n}\right)+O\left(\frac{x^{4}}{n}\right)\right)dx.

It follows that

\int_{-\theta_{0}}^{\theta_{0}}g(2ce^{i\theta})\lambda_{L}(2ce^{i\theta})^{k}e^{nh(2ce^{i\theta})}d\theta=\sqrt{\frac{2\pi}{\sigma n}}g(2c)\lambda_{L}(2c)^{k}e^{nh(2c)}\left(1+O\left(n^{-1}\right)+e^{-O(n^{1/5})}\right).

That is

[x^{n}]W_{-1}(x)^{n-M}\lambda_{L}(T(x))^{k}e^{W_{0}(x)-\lambda_{L}(T(x))}=2^{M-n}\frac{1}{\sqrt{2\pi\sigma n}}g(2c)\lambda_{L}(2c)^{k}e^{nh(2c)}\left(1+O\left(n^{-1}\right)\right)

(19)

Using Stirling’s formula for the corresponding range of $M$ , we have

\frac{1}{\binom{\binom{n}{2}}{M}}\frac{n!}{(n-M)!k!}=\frac{1}{k!}\sqrt{\frac{2\pi nM}{n-M}}\frac{2^{M}n^{n}M^{M}}{n^{2M}(n-M)^{n-M}}\exp\left(-2M+\frac{M}{n}+\frac{M^{2}}{n^{2}}\right)\left(1+O\left(n^{-1}\right)\right).

(20)

Multiplying (19) and (20), after cancellations we obtain

\Pr\left[X_{n,\,M}^{(L)}=k\right]=e^{-\lambda_{L}(2c)}\frac{\lambda_{L}(2c)^{k}}{k!}\left(1+O\left(n^{-1}\right)\right).

This proves the first part of the theorem.

Now, suppose that $k\to\infty$ as $n\to\infty$ . The previous arguments work in a similar way. Instead of using the estimate (17), which is only valid when $\theta$ is small enough, we exploit the fact that $\lambda_{L}$ has non-negative Taylor coefficients. Hence, Equation (17) can be replaced by the relation

\left|\lambda_{L}(2ce^{i\theta})^{k}\right|\leqslant\lambda_{L}(2c)^{k},

which is valid for each choice of $\theta\in[-\pi,\pi)$ . Applying the same arguments as before and that $\frac{1}{k!}<\frac{e^{k}}{k^{k}}$ for large $k$ , we conclude that

\Pr\left[X_{n,\,M}^{(L)}=k\right]\leqslant e^{-\lambda_{L}(2c)}\frac{\lambda_{L}(2c)^{k}}{k!}\left(1+O\left(n^{-1}\right)\right)<Ce^{-\lambda_{L}(2c)}\frac{(e\lambda_{L}(2c))^{k}}{k^{k}},

for a suitable constant $C$ . The second result in the theorem follows from the fact that $c<\frac{1}{2}$ , and hence $\lambda_{L}(2c)$ is bounded. ∎

3.2. Barely subcritical regime

In the barely subcritical regime the asymptotic structure of $G(n,M)$ is the same as in the subcritical regime. However, the integration countour we use is slightly more complicated in order to encode cycles of arbitrary length.

Theorem 3.2.

Let $M=\frac{n}{2}(1-\mu n^{-1/3})$ with $\mu$ tending to infinity with $\mu=o\left(n^{1/3}\right)$ . Let $L\subseteq\mathbb{N}_{\geqslant 3}$ and $\lambda_{L}(z)=\sum_{\ell\in L}\frac{z^{\ell}}{2\ell}$ . Then the random variable $X_{n,\,M}^{(L)}$ equal to the number of $L$ -cycles satisfies

\mathrm{Pr}\left[X_{n,M}^{(L)}=k\right]=e^{-\lambda_{L}\left(\frac{2M}{n}\right)}\frac{\lambda_{L}\left(\frac{2M}{n}\right)^{k}}{k!}\left(1+O\left(\mu^{-3}\right)\right).

(21)

Assume moreover that $\lim_{n}\lambda_{L}\left(\frac{2M}{n}\right)=\infty$ . Then for fixed real numbers $y_{0}<y_{1}$

\Pr\left[y_{0}\leqslant\frac{X_{n,\,M}-\lambda_{L}\left(\frac{2M}{n}\right)}{\sqrt{\lambda_{L}\left(\frac{2M}{n}\right)}}\leqslant y_{1}\right]\to\frac{1}{\sqrt{2\pi}}\int_{y_{0}}^{y_{1}}e^{-u^{2}/2}du,\quad\hbox{as $n\to\infty$}.

(22)

Proof.

The arguments and notation are similar to the ones in the proof of Theorem 3.1. As mentioned in the proof of Theorem 3.1, a.a.s. in this regime $G(n,M)$ contains only trees and unicyclic graphs as components. We need estimates for (9) in this new range of $M$ . We use again the same methods as in the proof of [2, Theorem 3.2]. Let

\omega(n)=\frac{(n-2M)^{1/4}}{n^{1/6}},\,\qquad\tau=\frac{n(n-M)}{M(n-2M)},\,\qquad\theta_{0}=\sqrt{\frac{\tau}{n}}\omega(n).

Then $n\theta^{2}\to\infty$ and $n\theta^{3}\to 0$ as $n\to\infty$ . The expansion of $h$ in the vicinity of $\theta_{0}$ is

h\left(\frac{2M}{n}e^{i\theta}\right)=h\left(\frac{2M}{n}\right)-\frac{M(n-2M)}{2n(n-M)}\theta^{2}-i\frac{(n^{2}-5nM+2M^{2})M}{6(n-M)^{2}}\theta^{3}+O(\theta^{4}).

(23)

For $\theta\in[-\theta_{0},+\theta_{0}]$ , $k=\Theta\left(\lambda_{L}(\frac{2M}{n})\right)$ , the expansion of $\lambda_{L}$ in the vicinity of $\theta_{0}$ is

\begin{split}\frac{\lambda_{L}\left(\frac{2M}{n}e^{i\theta}\right)^{k}}{\lambda_{L}\left(\frac{2M}{n}\right)^{k}}&=1+iO\left(\frac{k}{\lambda_{L}\left(\frac{2M}{n}\right)}\frac{n}{(n-2M)}\theta\right)+O\left(\frac{k^{2}}{\lambda_{L}\left(\frac{2M}{n}\right)^{2}}\frac{n^{2}}{(n-2M)^{2}}\theta^{2}\right)\\ &=1+iO\left(\frac{n}{(n-2M)}\theta\right)+O\left(\frac{n^{2}}{(n-2M)^{2}}\theta^{2}\right).\end{split}

(24)

The integrand can be bounded on $[-\pi,-\theta_{0})\cup(\theta_{0},\pi)$ because

\left|\exp\left(nh\left(\frac{2M}{n}e^{i\theta}\right)-nh\left(\frac{2M}{n}\right)\right)\right|=O(e^{-\omega(n)^{2}/2}).

(25)

Combining (23), (24) and (25), we have

\begin{array}[]{ll}\mathrm{Pr}\left[X_{n,M}^{(L)}=k\right]=\frac{n!}{\binom{\binom{n}{2}}{M}(n-M)!}\frac{2^{M-n}}{2\pi}g\left(\frac{2M}{n}\right)\exp\left(nh\left(\frac{2M}{n}\right)\right)\frac{\lambda_{L}\left(\frac{2M}{n}\right)^{k}}{k!}\times\\ \int_{-\theta_{0}}^{\theta_{0}}e^{-n\tau\frac{\theta^{2}}{2}}\left(1+iO\left(\frac{n}{(n-2M)}\theta\right)+O\left(\frac{n^{2}}{(n-2M)^{2}}\theta^{2}\right)\right)\times\\ \left(1+in\frac{(n^{2}-5nM+2M^{2})M}{6(n-M)^{2}}\theta^{3}+O(n\theta^{4})\right)d\theta\left(1+O(e^{-\omega(n)^{2}/2})\right).\end{array}

We set $\theta=\sqrt{{\tau}/{n}}x$ and the integral becomes

\begin{split}\sqrt{\frac{\tau}{n}}&\int_{-\omega(n)}^{\omega(n)}e^{-\frac{x^{2}}{2}}\left(1+iO\left(\frac{n}{(n-2M)^{3/2}}x\right)+O\left(\frac{n^{2}}{(n-2M)^{3}}x^{2}\right)\right)\\ &\quad.\left(1+iO\left(\frac{n}{(n-2M)^{3/2}}x^{3}\right)+O\left(\frac{n}{(n-2M)^{3}}x^{4}\right)\right)dx\\ &=\sqrt{\frac{\tau}{n}}\int_{-\omega(n)}^{\omega(n)}e^{-\frac{x^{2}}{2}}\left(1+O\left(\frac{n^{2}}{(n-2M)^{3}}x^{4}\right)\right)dx\\ &=\sqrt{\frac{2\pi\tau}{n}}\left(1+O\left(\frac{n^{2}}{(n-2M)^{3}}\right)\right).\end{split}

After simple algebraic manipulations as in the proof of Theorem 3.1 we obtain

\mathrm{Pr}\left[X_{n,M}^{(L)}=k\right]=e^{-\lambda_{L}\left(\frac{2M}{n}\right)}\frac{\lambda_{L}\left(\frac{2M}{n}\right)^{k}}{k!}\left(1+O\left(\mu^{-3}\right)\right).

This proves the first part of the theorem.

We assume now that $\lim_{n}\lambda_{L}\left(\frac{2M}{n}\right)=\infty$ . Set $k=\lambda_{L}\left(\frac{2M}{n}\right)+\rho_{n}\sqrt{\lambda_{L}\left(\frac{2M}{n}\right)}$ with $|\rho_{n}|=o\left(\lambda_{L}\left(\frac{2M}{n}\right)\right)^{1/6}$ . We can apply Theorem 2.1 and obtain

\begin{split}\Pr\left[X_{n,\,M}^{(L)}=k\right]&=\frac{1}{\sqrt{2\pi\lambda_{L}\left(\frac{2M}{n}\right)}}e^{-\rho_{n}^{2}/2}\left(1+\frac{\rho_{n}^{3}-\rho_{n}}{\sqrt{\lambda_{L}\left(\frac{2M}{n}\right)}}+O\left(\frac{1+\rho_{n}^{3}}{\sqrt{\lambda_{L}\left(\frac{2M}{n}\right)}}\right)\right)\,\\ &=\frac{1}{\sqrt{2\pi\lambda_{L}\left(\frac{2M}{n}\right)}}e^{-\rho_{n}^{2}/2}(1+o(1)).\end{split}

The central limit theorem for $X_{n,M}^{(L)}$ follows, that is, for fixed real $y_{0}<y_{1}$ we have

\Pr\left[y_{0}\leqslant\frac{X_{n,M}^{(L)}-\lambda_{L}\left(\frac{2M}{n}\right)}{\sqrt{\lambda_{L}\left(\frac{2M}{n}\right)}}\leqslant y_{1}\right]\to\frac{1}{\sqrt{2\pi}}\int_{y_{0}}^{y_{1}}e^{-u^{2}/2}du,\qquad\hbox{as $n\to\infty$}.

∎

3.3. Critical regime

In this regime we have to take into account the appearance of complex components. Let $p_{k}(n,M;L,r)$ be the probability that $G(n,M)$ has a total excess $r$ with exactly $k$ unicyclic components containing an $L$ -cycle. The following lemma gives an estimate for $p_{k}(n,M;L,r)$ .

Lemma 3.3.

Let $M=\frac{n}{2}(1+\mu n^{-1/3})$ with $\mu=O(1)$ . Let $\alpha$ be the positive solution to $\mu=\frac{1}{\alpha}-\alpha$ . Let

k=\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)+\rho\sqrt{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)},

which satisfies $\rho=\omega\left(\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)^{1/6}\right)$ .

Then for fixed $r$ we have

\begin{split}p_{k}(n,M;L,r)=e^{-\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}\frac{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)^{k}}{k!}\sqrt{2\pi}e_{r}\;A(3r+1/2,\mu)\cdot\left(1+O\left(n^{-1/12}\right)\right),\end{split}

where

e_{r}=\frac{(6r)!}{2^{5r}3^{2r}(3r)!\,(2r)!},\,\,A(y,\mu)=\frac{e^{-\mu^{3}/6}}{3^{(y+1)/3}}\sum_{k\geqslant 0}\frac{(\frac{1}{2}3^{2/3}\mu)^{k}}{k!\Gamma((y+1-2k)/3)}.

Moreover, for $r$ large enough there exist absolute constants $C>0$ and $\varepsilon>0$ such that

p_{k}(n,M;L,r)\leqslant e^{-\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}\frac{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)^{k}}{k!}Ce^{-\varepsilon r}.

(26)

Proof.

The proof is based on analytic techniques introduced in [4] and [6]; see also [9]. The probability $p_{k}(n,M;L,r)$ is given by

p_{k}(n,M;L,r)=\frac{n!}{\binom{\binom{n}{2}}{M}}[x^{n}]\frac{W_{-1}(x)^{n-M+r}}{(n-M+r)!}E_{r}(x)\frac{\lambda_{L}(T(x))^{k}}{k!}\,e^{W_{0}(x)-\lambda_{L}(T(x))},

(27)

where $E_{r}(x)$ is the EGF of complex components with total excess $r$ given by [6, Equation (6.8)]. As shown in [6], when $r=o(n^{1/3})$ , the series $E_{r}(x)$ can be approximated [6, Equation (6.8)] by $\frac{e_{r}}{(1-T(x))^{3r}}$ , where

e_{r}=\frac{(6r)!}{2^{5r}3^{2r}(3r)!\,(2r)!},

and the error term is of order $O\left(\frac{r^{3/2}}{n^{1/2}}\right)$ . In order to evaluate (27) we have to compute the expression

\frac{St(n,M,r)}{2\pi i}\oint(1-z)^{1-3r}e^{nh_{1}(z)}\,\frac{\lambda_{L}(z)^{k}}{k!}\,e^{W_{0}(z)-\lambda_{L}(z)}\,E_{r}(z)\,\frac{dz}{z},

(28)

where

	$\displaystyle St(n,M,r)$	$\displaystyle=$	$\displaystyle\frac{n!}{\binom{\binom{n}{2}}{M}}\frac{2^{-n+M-r}e^{n}e_{r}}{(n-M+r)!},$		(29)
	$\displaystyle h_{1}(z)$	$\displaystyle=$	$\displaystyle z-1-\log z+\left(1-\frac{M}{n}\right)\log(2z-z^{2})\,.$		(30)

We remark the difference between $h_{1}(z)$ and the function $h(z)$ defined in Equation (13). Note also that $h_{1}(z)$ is exactly the same as in [6, Equation (10.12)], which satisfies $h_{1}(1)=h_{1}^{\prime}(1)=0$ and also $h_{1}^{\prime\prime}(1)=0$ if $M=n/2$ . We now follow the method of the proof of [6, Lemma 3] in order to compute our integral by choosing as path of integration

z=z(t)=e^{-\alpha n^{-1/3}-itn^{-1/2}},

(31)

where $\alpha$ is the unique positive solution of $\mu=\frac{1}{\alpha}-\alpha$ , and $t$ belongs to the interval

\left(-\pi n^{1/4}\lambda_{L}^{\prime}(e^{-\alpha n^{-1/3}})^{-1/2},\pi n^{1/4}\lambda_{L}^{\prime}(e^{-\alpha n^{-1/3}})^{-1/2}\right).

Given that

\begin{split}&\frac{\lambda_{L}(e^{-\alpha n^{-1/3}-itn^{-1/2}})^{k}}{k!}e^{-\lambda_{L}(e^{-\alpha n^{-1/3}-itn^{-1/2}})}=\\ &\frac{\lambda_{L}(e^{-\alpha n^{-1/3}})^{k}}{k!}e^{-\lambda_{L}(e^{-\alpha n^{-1/3}})}\qquad\times\\ &\left(1+iO\left(\frac{k}{\lambda_{L}(e^{-\alpha n^{-1/3}})}\frac{\lambda_{L}^{\prime}\left(e^{-\alpha n^{-1/3}}\right)}{n^{1/2}}t\right)+O\left(\frac{k^{2}}{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)^{2}}\frac{\lambda_{L}^{\prime}\left(e^{-\alpha n^{-1/3}}\right)^{2}}{n}t^{2}\right)\right)\end{split}

(32)

as long as $k=O\left(\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)\right)$ , our choice ensures that the $O$ terms in (32) can be moved out of the integral. By following the proof of [6, Equation (10.1) of Lemma 3] we obtain that, for fixed values of $r$

p_{k}(n,M;L,r)=e^{-\lambda_{L}(e^{-\alpha n^{-1/3}})}\frac{\lambda_{L}(e^{-\alpha n^{-1/3}})^{k}}{k!}\sqrt{2\pi}e_{r}A(3r+1/2,\mu)\left(1+O\left(n^{-1/12}\right)+O\left(\frac{\mu^{4}}{n^{1/3}}\right)\right).

(33)

Since $k=O\left(\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)\right)$ in the $O$ terms above we have

\frac{\lambda_{L}^{\prime}\left(e^{-\alpha n^{-1/3}}\right)}{n^{1/2}}t=O\left(\frac{\lambda_{L}^{\prime}\left(e^{-\alpha n^{-1/3}}\right)^{1/2}}{n^{1/4}}\right)=O\left(\frac{1}{(1-e^{-\alpha n^{-1/3}})^{1/2}}\frac{1}{n^{1/4}}\right)=O\left(n^{-1/12}\right).

This proves the first statement of the theorem.

Next let us assume that $r\to\infty$ . We know that $E_{r}(z)\preceq\frac{e_{r}}{(1-T(z))^{3r}}$ (see for instance [6, Lemma 4]). From (27) we have

p_{k}(n,M;L,r)\leqslant\frac{n!}{\binom{\binom{n}{2}}{M}}[z^{n}]\frac{W_{-1}(x)^{n-M+r}}{(n-M+r)!}\frac{\lambda_{L}(T(z))^{k}}{k!}\,e^{W_{0}(z)-\lambda_{L}(T(z))}\frac{e_{r}}{(1-T(z))^{3r}}.

Then, we obtain

p_{k}(n,M;L,r)\leqslant\frac{St(n,M,r)}{2\pi i}\oint\frac{z^{r}(2-z)^{r}}{(1-z)^{3r}}e^{nh_{1}(z)}\frac{\lambda_{L}(z)^{k}}{k!}e^{\lambda(z)-\lambda_{L}(z)}\frac{dz}{z},

(34)

with $h_{1}$ is defined by (30). In this case we take as contour of integration the circle $\{\delta e^{i\theta}:\theta\in[-\pi,\pi)\}$ with $\delta=1-\frac{r^{1/3}}{n^{1/3}}<1$ . On this circle, since $r\geqslant 1$ , for some constant $C$ and function $f(n)$ with $\lim_{n}f(n)=+\infty$ , we have

\begin{split}\frac{\lambda_{L}(\delta)^{k}}{k!}e^{-\lambda_{L}(\delta)}&\frac{\delta}{2\pi}\left(\frac{\delta(2-\delta)}{(1-\delta)^{3}}\right)^{r}e^{nh_{1}(\delta)}(1-\delta)^{1/2}\int_{-\pi}^{\pi}e^{-f(n)\theta^{2}}d\theta<\frac{C}{\sqrt{n}}\,\delta^{r}\left(\frac{\delta(2-\delta)}{(1-\delta)^{3}}\right)^{r}e^{nh_{1}(\delta)}.\end{split}

Note that $r\leqslant M=\frac{n}{2}(1+\mu n^{-1/3})$ . Then for $n$ large enough

\frac{\delta^{r}(2-\delta)^{r}}{(1-\delta)^{3r}}<\frac{n^{r}}{r^{r}},\,nh_{1}(\delta)<\frac{13}{12}r+\frac{11}{6}\mu r^{2/3}.

(35)

Using Stirling’s formula we find that

\frac{n!}{\binom{\binom{n}{2}}{M}(n-M+r)!}e^{n}2^{-n+M-r}<\frac{n^{1/2}}{n^{r}}e^{-\mu^{3}/6+3/4}2^{-r},

and for $r\to\infty$ , we have

e_{r}=\frac{(6r)!}{2^{5r}3^{2r}(3r)!\,(2r)!}\leqslant\frac{1}{r^{1/2}}\left(\frac{3r}{2e}\right)^{r}.

(36)

Combining (35) and (36) in (34), we deduce that

p_{k}(n,M;L,r)<\frac{c_{0}}{r^{1/2}}\exp\left(-\frac{\mu^{3}}{6}+\frac{11}{6}\mu r^{2/3}+\left(\frac{13}{12}+\log\frac{3}{4}-1\right)r\right),

for some constant $c_{0}>0$ . Since $\frac{13}{12}+\log\frac{3}{4}-1<0$ , when $r\to\infty$ we deduce

p_{k}(n,M;L,r)\leqslant e^{-O(r)}.

∎

We can now proof the main result in the critical regime.

Theorem 3.4.

Let $M=\frac{n}{2}(1+\mu n^{-1/3})$ where $\mu=O(1)$ . Let $\alpha$ be the positive solution to $\mu=\frac{1}{\alpha}-\alpha$ . Let $L\subseteq\mathbb{N}_{\geqslant 3}$ and let $\lambda_{L}(z)=\sum_{k\in L}\frac{z^{k}}{2k}$ . Then the random variable $X_{n,\,M}^{(L)}$ equal $L$ -cycles in $G(n,M)$ satisfies

\mathrm{Pr}\left[X_{n,M}^{(L)}=k\right]=e^{-\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}\frac{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)^{k}}{k!}\left(1+O\left(n^{-1/12}\right)\right).

(37)

Moreover, assume that $\lim_{n\to\infty}\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)=+\infty$ . Then, for each choice of real $y_{0}<y_{1}$

\Pr\left[y_{0}\leqslant\frac{X_{n,M}^{(L)}-\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}{\sqrt{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}}\leqslant y_{1}\right]\to\frac{1}{\sqrt{2\pi}}\int_{y_{0}}^{y_{1}}e^{-u^{2}/2}du,\qquad\hbox{ when }n\to\infty.

(38)

Proof.

By Lemma 3.3 and the dominated convergence theorem, $\Pr\left[X_{n,\,M}^{(L)}=k\right]$ is equal to

\begin{split}\sum_{r\geqslant 0}p_{k}(n,M;L,r)=\sum_{r\geqslant 0}e^{-\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)}\frac{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)^{k}}{k!}\sqrt{2\pi}e_{r}\;A(3r+1/2,\mu)\cdot\left(1+O\left(n^{-1/12}\right)\right).\end{split}

For $\mu=O(1)$ Janson, Knuth, Łuczak and Pittel [6, Equation (13.17) and Corollary p. 61] have shown that the probability that $G(n,\,M)$ has total excess $r$ is asymptotically $\sqrt{2\pi}e_{r}A(3r+1/2,\mu)$ , and that the $s$ -th moment of the excess $r$ satisfies $\sum_{r\geqslant 0}\sqrt{2\pi}e_{r}r^{s}A(3r+1/2,\mu)=O(\mu^{3s})=O(1)$ . Hence $\sum_{r\geqslant 0}\sqrt{2\pi}e_{r}A(3r+1/2,\mu)=1$ . This shows relation (37).

In order to prove (38), we apply Theorem 2.1 by choosing

k=\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)+\rho_{n}\sqrt{\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)},

with $\lambda_{L}\left(e^{-\alpha n^{-1/3}}\right)^{1/6}=o(\rho_{n}).$ ∎

4. Acknowledgments

Part of this research was done when the J.R. was visiting IRIF – Université Paris Denis Diderot in July 2018. J.R. thanks the hospitality of the institution during his research stay. V.R. was partially supported by grants ANR 2010 BLAN 0204 (Magnum). V.R. and J.R. were supported by the Project PHC Procope ID-57134837 ‘Analytic, probabilistic and geometric Methods for Random Constrained graphs’. J.R. was partially supported by the FP7-PEOPLE-2013-CIG project CountGraph (ref. 630749). Finally, M.N. and J.R. were supported by the Spanish project MTM2017-82166-P and by the H2020-MSCA-RISE-2020 project RandNET (ref. 101007705).

References

[1] N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Third edition.
[2] H. Daudé and V. Ravelomanana. Random 2-xorsat phase transition. Algorithmica, Special issue of LATIN 2008:1–18, 2009.
[3] P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5:17–61, 1960.
[4] P. Flajolet, D. E. Knuth, and B. Pittel. The first cycles in an evolving graph. Discrete Mathematics, 75(1-3):167–215, 1989.
[5] P. Flajolet and B. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
[6] S. Janson, D. E. Knuth, T. Łuczak, and B. Pittel. The Birth of the Giant Component. Random Structures and Algorithms, 4(3):233–358, 1993.
[7] S. Janson, T. Łuczak, and A. Ruciński. Random Graphs. Wiley-Interscience, 2000.
[8] V. F. Kolchin. Random Graphs. Cambridge University Press, 1998.
[9] Marc Noy, Vlady Ravelomanana, and Juanjo Rué. On the probability of planarity of a random graph near the critical point. Proc. Amer. Math. Soc., 143(3):925–936, 2015.