# First Order Logic of Sparse Graphs with Given Degree Sequences

Alberto Larrauri, Guillem Perarnau

(May 2023)

###### Abstract

We consider limit probabilities of first order properties in random graphs
with a given degree sequence. Under mild conditions on the degree sequence, we
show that the closure set of limit probabilities is a finite union of closed
intervals. Moreover, we characterize the degree sequences for which this
closure set is the interval $[0,1]$, a property that is intimately related
with the probability that the random graph is acyclic. As a side result, we
compile a full description of the cycle distribution of random graphs and
study their fragment (disjoint union of unicyclic components) in the
subcritical regime. Finally, we amend the proof of the existence of limit
probabilities for first order properties in random graphs with a given degree
sequence; this result was already claimed by Lynch [IEEE LICS 2003] but his
proof contained some inaccuracies.

##  1 Introduction

Since the seminal work of Erdős and Rényi [7], random graphs have been central
objects of study in probabilistic combinatorics. In this area it is common to
ask, given a graph property $\varphi$ and a sequence of random graphs
$\mathbb{G}_{n}$ increasing in order, what is the limit probability that
$\mathbb{G}_{n}$ satisfies $\varphi$. Of course, this limit may or may not
exist, and the question about its existence is interesting on its own. In a
related direction, for families $\mathcal{L}$ of “well-behaved” graph
properties, one may want to obtain a procedure (i.e., an algorithm) that given
some property $\varphi$ in $\mathcal{L}$ computes the limit probability
$p(\varphi):=\lim_{n\to\infty}\mathbb{P}(\mathbb{G}_{n}\text{ satisfies
}\varphi)$, if it exists.

The model-theoretical approach to the questions above is to classify graph
properties according to the formal languages that can express them, and obtain
convergence results for the entire language rather than for individual
properties. One such language is the first order (FO) language of graphs,
which consists of first order logic, where variables represent vertices, plus
a binary adjacency relation, which is meant to be symmetric and anti-
reflexive. Fagin [8] and, independently, Glebski et. al. [9] showed that
$p(\varphi)\in\\{0,1\\}$ for all FO-properties $\varphi$ in the case that
$\mathbb{G}_{n}=\mathbb{G}_{n}(1/2)$, the _binomial random graph_ on $n$
vertices, obtained by including each edge independently with probability
$1/2$. Even more, there is a procedure to determine the limit probability for
any given FO-property. This result, which gave rise to the model-theoretical
study of random graphs, is an example of a zero-one law. A more general kind
of result is a convergence law, which simply states that for a given sequence
of random graphs $\mathbb{G}_{n}$ and a given language $\mathcal{L}$, the
limit probability $p(\varphi)$ exists for all properties $\varphi$ expressible
in $\mathcal{L}$. This work continues a line of research [11, 17] that studies
the geometry of the set of limit probabilities in settings where a convergence
law holds.

In this paper we deal with the case where $\mathbb{G}_{n}$ is a random graph
whose degree sequence has been fixed a priori. A degree sequence of length $n$
is a sequence ${\bm{d}}_{n}=(d_{i})_{i\in[n]}$ where $d_{i}$ is a non-negative
integer with $d_{i}<n$ for all $i\in[n]$ and $\sum_{i\in[n]}d_{i}$ is even. We
call ${\bm{d}}_{n}$ feasible, if there is at least one graph $G$ with
$V(G)=[n]$ whose degree sequence is ${\bm{d}}_{n}$, meaning that for all
$v\in[n]$, it has degree $d_{v}$. Given a feasible degree sequence
${\bm{d}}_{n}$ on $n$ vertices, $\mathbb{G}_{n}({\bm{d}}_{n})$ denotes the
uniform random graph with vertex set $[n]$ and whose degree sequence is
${\bm{d}}_{n}$. A sequence of degree sequences is
${\bm{d}}=({\bm{d}}_{n})_{n\in\mathbb{N}}$, where
${\bm{d}}_{n}=(d_{n,i})_{i\in[n]}$ is a degree sequence on $n$ vertices. By
convention, we set $d_{n,i}=0$ for each $i\geq n$, and, if the context is
clear, we use $d_{i}=d_{n,i}$. Given ${\bm{d}}$, we define the sequence of
random graphs
$\mathbb{G}({\bm{d}})=(\mathbb{G}_{n}({\bm{d}}_{n}))_{n\in\mathbb{N}}$.

In order to study $\operatorname{\textsc{FO}}$ logic on
$\mathbb{G}({\bm{d}})$, we will need to impose some regularity conditions on
${\bm{d}}$. These conditions are better stated in terms of degree
distributions. For $k\geq 0$, define $n_{k}=n_{n,k}=|\\{i\in[n]\mid
d_{n,i}=k\\}|$. Given $n\in\mathbb{N}$ and ${\bm{d}}$, the degree distribution
$D_{n}=D_{n}({\bm{d}})$ is given by $\mathbb{P}(D_{n}=k)=n_{n,k}/n$.
Equivalently, $D_{n}$ is the probability distribution of the degree of a
uniform random vertex in $\mathbb{G}_{n}({\bm{d}}_{n})$. The following is our
main assumption, used throughout this paper.

######  Assumption 1.1.

There exists a probability distribution $D=D({\bm{d}})$ on $\mathbb{N}_{0}$
such that

  1. (i)

${\bm{d}}_{n}$ is feasible for all $n\in\mathbb{N}$;

  2. (ii)

$D_{n}\rightarrow D$, in distribution;

  3. (iii)

$\lim_{n\to\infty}\mathbb{E}\left[D_{n}\right]$ (resp.,
$\lim_{n\to\infty}\mathbb{E}\left[D_{n}^{2}\right]$), exists, is bounded and
equals to $\mathbb{E}\left[D\right]$ (resp., $\mathbb{E}\left[D^{2}\right]$);

  4. (iv)

if $\mathbb{P}(D=k)=0$ for some $k\in\mathbb{N}_{0}$, then $n_{n,k}=0$ for all
$n\in\mathbb{N}$.

In this context a convergence law for $\operatorname{\textsc{FO}}$-properties
holds.

######  Theorem 1.2.

Suppose that ${\bm{d}}$ satisfies 1.1. Then for any property $\varphi$ in the
$\operatorname{\textsc{FO}}$ language of graphs, the following limit exists

$p(\varphi,{\bm{d}}):=\lim_{n\to\infty}\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{
satisfies }\varphi).$ (1)

The proof of this theorem is not the primary goal of this paper and is
sketched in Section 8. Very similar results were established by Lynch in two
closely related articles [18, 20]. The difference between Lynch’s articles is
the assumptions imposed on ${\bm{d}}$. These assumptions are non-comparable
with 1.1. However, due to a slight oversight, both Lynch’s proofs are
incorrect. Even more, the convergence law does not always exist under any of
his two assumptions. Nevertheless, under 1.1 his proof strategy can be used
correctly and this assumption is essentially the weakest condition required to
have a convergence law.

Given that the limit in 1 exists for all
$\operatorname{\textsc{FO}}$-properties $\varphi$, our object of interest is
the set of limits. Define

$L({\bm{d}}):=\\{p(\varphi,{\bm{d}})\,\mid\,\varphi\text{
$\operatorname{\textsc{FO}}$-property}\\}.$ (2)

We are interested in the geometry of the topological closure
$\overline{L({\bm{d}})}$ (i.e. the union of the points in the set and its
limit points). Observe that $\overline{L({\bm{d}})}$ is a symmetric subset of
the interval $[0,1]$ (i.e, $p\in\overline{L({\bm{d}})}$ if and only if
$1-p\in\overline{L({\bm{d}})}$), since the negation of an
$\operatorname{\textsc{FO}}$-property is also an
$\operatorname{\textsc{FO}}$-property.

The main result of the paper is the following.

######  Theorem 1.3.

Suppose that ${\bm{d}}$ satisfies 1.1. Define

$p_{\mathrm{acyc}}({\bm{d}}):=\lim_{n\to\infty}\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{
is acyclic}).$ (3)

Then, $\overline{L({\bm{d}})}$ is a finite union of closed intervals, and

  1. (1)

if $p_{\mathrm{acyc}}({\bm{d}})<1/2$, then $\overline{L({\bm{d}})}\neq[0,1]$;

  2. (2)

if $p_{\mathrm{acyc}}({\bm{d}})\geq 1/2$, then $\overline{L({\bm{d}})}=[0,1]$.

We devote the rest of the introduction to discuss some aspects of our results.

######  Remark 1.4 (Discussion on 1.1).

Assumption (i) is necessary in order to define $\mathbb{G}({\bm{d}})$.
Assumptions (ii) and (iii) allow us to study $\mathbb{G}_{n}({\bm{d}}_{n})$ by
looking at the limit degree distribution $D$. They imply that the average
degree and the second moment of the degree sequence are bounded in
probability, which in particular imply that the maximum degree is
$o(\sqrt{n})$. These two assumptions are usual in the setting of random graphs
with given degree sequence. The infinite degree variance case exhibits a very
different behaviour (see e.g. [13]) and it remains as an open problem to prove
if in such case $\mathbb{G}({\bm{d}})$ has a convergence law for the
$\operatorname{\textsc{FO}}$ language. Finally, Assumption (iv) rules out the
existence of vertices with low-frequency degrees. Otherwise such vertices
would pose an obstacle to a convergence law for $\operatorname{\textsc{FO}}$
logic on graphs: for instance, consider ${\bm{d}}_{n}$ containing a single
vertex of degree $3$ for odd $n$, and none for even $n$, and $\varphi$ the FO-
property “the graph contains a vertex of degree $3$”, then
$p(\varphi,{\bm{d}})$ does not exist. For our purposes, assumption (iv) could
be weakened replacing “for all $n$” by “for all sufficiently large $n$”.
However, we use the stronger version for convenience.

######  Remark 1.5 (The configuration model).

As it is usually the case, instead of studying directly the graph
$\mathbb{G}_{n}({\bm{d}}_{n})$ we will study $\mathbb{CM}_{n}({\bm{d}}_{n})$,
a related random (multi)graph known as the configuration model, and introduced
in Section 2. Theorems 1.2 and 1.3 also hold for $\mathbb{CM}({\bm{d}})$, as
it will be discussed later.

######  Remark 1.6 (Probability of being acyclic).

The cycle distribution and the limit probability that
$\mathbb{G}_{n}({\bm{d}}_{n})$ (or $\mathbb{CM}_{n}({\bm{d}}_{n})$) is acyclic
have been studied in the literature (see Section 4.1). It is well-known that,
provided that ${\bm{d}}$ satisfies 1.1, the number of cycles of length $k$
converges to a Poisson variable with parameter $\nu^{k}/(2k)$, and they are
asymptotically independent (see Lemma 4.3). Here, $\nu$ is a limit parameter
defined on ${\bm{d}}$, see (7), which in fact is a fundamental parameter of
random graphs with a given degree sequence. For instance, the phase transition
for the existence of a giant component is located at $\nu=1$ [15, 22]. As a
consequence, $p_{\mathrm{acyc}}({\bm{d}})$ exists and only depends on $\nu$:

$p_{\mathrm{acyc}}({\bm{d}})=\sqrt{1-\nu}\cdot
e^{\frac{\nu}{2}+\frac{\nu^{2}}{4}}\qquad\text{for }\nu\in(0,1),$ (4)

and $p_{\mathrm{acyc}}({\bm{d}})=0$ if $\nu\geq 1$ (see Lemma 4.6). In (4),
the term $\sqrt{1-\nu}$ accounts for the probability that
$\mathbb{CM}_{n}({\bm{d}}_{n})$ is acyclic: it has no cycles of length $k$,
for all $k\geq 1$. However, our object of interest is
$\mathbb{G}_{n}({\bm{d}}_{n})$ which, by definition, is simple: it has neither
cycles of length one (loops) nor cycles of length two (multiedges). The
correction terms $e^{{\nu}/{2}}$ and $e^{{\nu^{2}}/{4}}$ can be thought as
deducting the contribution of loops and multiedges, respectively, from the
configuration model acylic probability.

Alternatively, taking the Taylor series of $\ln(\sqrt{1-\nu})$, we can rewrite
(4) as

$p_{\mathrm{acyc}}({\bm{d}})=\exp\left(-\sum_{k\geq
3}\frac{\nu^{k}}{2k}\right)\qquad\text{for }\nu\in(0,1).$ (5)

This is not a closed-form expression but it has a more straightforward
interpretation: $\mathbb{G}_{n}({\bm{d}}_{n})$ is acyclic if and only if it
has no cycles of length three (term $e^{-\nu^{3}/6}$), no cycles of length
four (term $e^{-\nu^{4}/8}$), and so on. In particular, note that
$p_{\mathrm{acyc}}({\bm{d}})\in(0,1)$ for $\nu\in(0,1)$.

The second part of Theorem 1.3 locates a threshold at
$p_{\mathrm{acyc}}({\bm{d}})=1/2$. Let $\nu_{0}\in[0,1]$ be the unique root of

$\sqrt{1-\nu}\cdot e^{\frac{\nu}{2}+\frac{\nu^{2}}{4}}=\frac{1}{2}.$ (6)

Indeed, the previous equation has exactly one solution in $[0,1]$ as its LHS
is monotonically decreasing in this interval and evaluates to $1$ at $\nu=0$
and to $0$ at $\nu=1$. Numerically, we obtain $\nu_{0}\approx 0.9368317$,
which coincides with the threshold value for $c$ in $\mathbb{G}_{n}(c/n)$
obtained in [17]. To our best knowledge, the value $\nu_{0}$ has not been
identified yet as a threshold for any other property of
$\mathbb{G}_{n}({\bm{d}}_{n})$.

##  2 Preliminaries

###  2.1 Notation

From now on we fix ${\bm{d}}$ that satisfies 1.1. We introduce some additional
notation that will be used throughout the paper. For $k\geq 0$ and
$n\in\mathbb{N}$, define $\lambda_{n,k}:=\mathbb{P}(D_{n}=k)$ and
$\lambda_{k}:=\mathbb{P}(D=k)$, where $D_{n}$ is the degree distribution
corresponding to ${\bm{d}}_{n}$ and $D$ is the limiting degree distribution
(which exists by 1.1). Additionally, define
$\widehat{\lambda}_{n}:=1-\lambda_{n,0}-\lambda_{n,1}$, and
$\widehat{\lambda}:=\lim_{n\to\infty}\widehat{\lambda}_{n}$. Similarly, define
$\widehat{n}:=|\left\\{i\in[n]\mid d_{n,i}\geq
2\right\\}|=n\widehat{\lambda}_{n}$, the number of vertices whose degree in
${\bm{d}}_{n}$ is at least $2$.

Define $m_{n}:=\sum_{i\in[n]}d_{n,i}$, twice the number of edges in
$\mathbb{G}_{n}({\bm{d}}_{n})$. Define
$\rho_{n,k}:=\mathbb{E}\left[D_{n}(D_{n}-1)\dots(D_{n}-k+1)\right]$ and
$\rho_{k}:=\mathbb{E}\left[D(D-1)\dots(D-k+1)\right]$, the $k$-th factorial
moments of $D_{n}$ and $D$, respectively. By 1.1.(iii),
$\lim_{n\to\infty}\rho_{n,k}=\rho_{k}$ for $k=1,2$. Define

$\nu:=\nu({\bm{d}})=\frac{\mathbb{E}\left[D(D-1)\right]}{\mathbb{E}\left[D\right]}=\frac{\rho_{2}}{\rho_{1}}.$
(7)

By the convergence of the first and second moments, if
$\nu_{n}:=\tfrac{\mathbb{E}\left[D_{n}(D_{n}-1)\right]}{\mathbb{E}\left[D_{n}\right]}$,
then $\lim_{n\to\infty}\nu_{n}=\nu$.

As we already indicated in Remark 1.6, $\nu$ plays a crucial role in the cycle
distribution and the shape of the limit probability set.

###  2.2 Multigraphs

A multigraph $G$ is a pair $(V(G),E(G))$ where $V(G)$ is its vertex set, and
$E(G)$ is its edge set, a multiset of unordered pairs $\\{u,v\\}$ where
$u,v\in V(G)$. We allow the possibility that $u=v$, in which case the edge is
called a loop. Given $u,v\in V(G)$, the multiplicity of the edge with
endpoints $u,v$ is the number of pairs $\\{u,v\\}$ in the multiset $E(G)$. The
degree $\deg(v)$ of a vertex $v\in V(G)$ is the number of edges $\\{u,v\\}\in
E(G)$ with $u\neq v$, plus twice the number of loops $\\{v,v\\}\in E(G)$.

If $G,H$ are multigraphs, an $H$-copy in $G$ is a _sub-multigraph_
$H^{\prime}\subseteq G$ that is isomorphic to $G$. In the context of
multigraphs, $k$-cycles are defined as usual for $k\geq 3$. For $k=2$, a
$2$-cycle consists of two vertices plus two edges joining them, and for $k=1$,
a $1$-cycle is just a vertex with a loop attached to it.

Define the excess of a multigraph (or graph) $G$ to be
$\operatorname{\mathrm{ex}}(G):=|E(G)|-|V(G)|$. A connected graph $G$ is
unicylic if $\operatorname{\mathrm{ex}}(G)=0$, or, equivalently, when it has
exactly one cycle. A fragment is a disjoint union of unicylic components. The
fragment $\mathrm{Frag}(G)$ of a multigraph (or graph) $G$ is the union of its
unicyclic components. We call a fragment simple if it contains neither loops
nor multiedges, or, in other words, if it contains no cycles of length smaller
than $3$.

Given a multigraph $G$, its number of half-edge automorphisms is

$\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(G):=\operatorname{\mathrm{aut}}(G)2^{\ell}\prod_{u,v\in
V(G)}m({u,v})!,$ (8)

where $\ell$ is the number of loops in $G$, and $m(u,v)$ denotes the
multiplicity of $\\{u,v\\}$ in $E(G)$. In this way,
$\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(C_{k})=2k$, where $C_{k}$ is a
$k$-cycle and $k\geq 1$. Informally,
$\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(G)$ is the number of half-edge
permutations in $G$ that preserve both incidence to the same vertex and the
matching between half-edges.

Other notions related to graphs extend to multigraphs in the natural way.

###  2.3 Configuration Model

We study random graphs with given degree sequence through the so-called
configuration model, introduced by Bollobás [1, 2], which instead yields a
random multigraph with the desired degree sequence. See e.g. [12, 13] for the
basic properties of the model.

Given a degree sequence ${\bm{d}}_{n}$ of length $n$, the configuration model
$\mathbb{CM}_{n}({\bm{d}}_{n})$ is a uniform random matching of $[m_{n}]$
(formally, $\mathbb{CM}_{n}({\bm{d}}_{n})\subseteq\binom{[m_{n}]}{2}$), where
we recall that $m_{n}=\sum_{i\in[n]}d_{i}$. We refer to the elements
$e\in[m_{n}]$ as half-edges. We say that a half-edge $e\in[m_{n}]$ is incident
to a vertex $v\in[n]$ if $\sum_{u<v}d_{u}<e\leq\sum_{u\leq v}d_{u}$. In other
words, the first $d_{1}$ half-edges belong to vertex $1$, the following
$d_{2}$ belong to vertex $2$, and so on. The underlying multigraph of
$\mathbb{CM}_{n}({\bm{d}}_{n})$ has vertex set $[n]$ and the number of edges
between two different vertices $v_{1},v_{2}\in[n]$ is the number of pairs
$\\{h_{1},h_{2}\\}$ in the matching $\mathbb{CM}_{n}({\bm{d}}_{n})$ where
$h_{1},h_{2}$ are incident to $v_{1},v_{2}$, respectively.

In the following, we identify $\mathbb{CM}_{n}({\bm{d}}_{n})$ with its
underlying multigraph. Informally, we obtain the multigraph
$\mathbb{CM}_{n}({\bm{d}}_{n})$ by attaching $d_{v}$ half edges to each vertex
$v\in[n]$, and matching these half-edges randomly afterwards. For a sequence
of degree sequences ${\bm{d}}=({\bm{d}}_{n})_{n\in\mathbb{N}}$, we denote by
$\mathbb{CM}({\bm{d}})=(\mathbb{CM}_{n}({\bm{d}}_{n}))_{n\in\mathbb{N}}$.

The probability that $\mathbb{CM}_{n}({\bm{d}}_{n})=G$ for a fixed multigraph
$G$ with degree sequence ${\bm{d}}_{n}$ depends only on its number of loops
and the multiplicity of its edges. In particular, if ${\bm{d}}$ is feasible,
conditioning $\mathbb{CM}_{n}({\bm{d}}_{n})$ on being simple (i.e. the absence
of loops and multiedges) results in $\mathbb{G}_{n}({\bm{d}}_{n})$. It is thus
natural to compute the probability that $\mathbb{CM}_{n}({\bm{d}}_{n})$ is
simple. The following theorem gives an answer for sequences that satisfy our
assumption (in fact, the theorem holds in a slightly more general setting).
Recall the definition of $\nu$ in (7).

######  Theorem 2.1 (Bollobás [2]; Janson [14, Theorem 1.1]).

Let ${\bm{d}}$ satisfies 1.1. Then

$\displaystyle\liminf_{n\to\infty}\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{
is simple})=e^{-\frac{\nu}{2}-\frac{\nu^{2}}{4}}>0.$ (9)

We will revisit this theorem in forthcoming sections.

Let us also briefly recall the role of $\nu$ in the phase transition of
$\mathbb{CM}({\bm{d}})$. Under 1.1, $\nu$ determines the appearance of a giant
component in $\mathbb{CM}({\bm{d}})$ [15, 22]. Namely,
$\mathbb{CM}_{n}({\bm{d}}_{n})$ a.a.s. contains a linear order component if
and only if $\nu>1$.

###  2.4 Exchange of Limit and Sum Operators

Some of our results rely on the exchange of limit and sum operations. We
recall the notion of tight sequence and an equivalent characterization.

######  Definition 2.2.

Let $(f_{n})_{n\in\mathbb{N}}$ be a sequence of functions
$f_{n}:S\rightarrow[0,\infty)$ where $S$ is a countable set. The sequence
$(f_{n})_{n\in\mathbb{N}}$ is tight if for every $\epsilon>0$ there exists a
finite $T\subset S$ satisfying $\sum_{s\not\in T}f_{n}(s)<\epsilon$ for all
$n\in\mathbb{N}$.

######  Lemma 2.3.

Let $(f_{n})_{n\in\mathbb{N}}$ be a sequence of functions
$f_{n}:S\rightarrow[0,\infty)$ where $S$ is a countable set. Suppose that

  * (1)

for each $s\in S$, $f(s)=\lim_{n\to\infty}f_{n}(s)$ exists and is finite,

  * (2)

$\sum_{s\in S}f(s)$ is finite.

Then $\lim_{n\to\infty}\sum_{s\in S}f_{n}(s)=\sum_{s\in S}f(s)$ if and only if
$(f_{n})_{n\in\mathbb{N}}$ is tight.

###  2.5 Probability preliminaries

In order to study the small cycle distribution of $\mathbb{CM}({\bm{d}})$ we
will need the next auxiliary result [3, Theorem 1.23].

######  Theorem 2.4 (Method of Moments for Poisson random variables ).

Let $k\in\mathbb{N}$. For each $n\in\mathbb{N}$, let $X_{n,1},$
$\dots,X_{n,k}$ be random variables over the same measurable space. Suppose
that there are real positive constants $\lambda_{1},\dots,\lambda_{k}$ such
that for all $a_{1},\dots,a_{k}\in{\mathbb{N}}$

$\lim_{n\to\infty}\mathbb{E}\left[\prod_{i=1}^{k}\binom{X_{n,i}}{a_{i}}\right]=\prod_{i=1}^{k}\frac{\lambda_{i}^{a_{i}}}{a_{i}!}.$

Then $(X_{n,1},\dots,X_{n,k})$ converges in distribution to a vector of
independent Poisson random variables with parameters
$\lambda_{1},\dots,\lambda_{k}$ as $n\to\infty$.

###  2.6 Sets of Partial Sums

Given a convergent series $\sum_{n\in\mathbb{N}}p_{n}$ whose terms are non-
negative, its set of partial sums is defined as $\\{\sum_{n\in A}p_{n}\colon
A\subseteq\mathbb{N}\\}\subseteq[0,+\infty)$. As part of the proof of Theorem
1.3 we need to analyze the geometry of some of these sets. Our tool for this
matter is the following classical result conjectured by Kakeya [16] and later
proven in [23].

######  Lemma 2.5 (Kakeya’s Criterion).

Let $\sum_{n\in\mathbb{N}}p_{n}$ be a convergent series of non-negative real
numbers such that $p_{n}\geq p_{n+1}$ for all $n\in\mathbb{N}$. Then the
following are equivalent:

  * (1)

$p_{i}\leq\sum_{j>i}p_{j}$ for all $i\in\mathbb{N}$.

  * (2)

$\left\\{\sum_{n\in A}p_{n}\colon
A\subseteq\mathbb{N}\right\\}=\left[0,\sum_{n\in\mathbb{N}}p_{n}\right].$

If the condition (1) only holds for all values of $i$ large enough, then the
set $\left\\{\sum_{n\in A}p_{n}\colon A\subseteq\mathbb{N}\right\\}$ is a
finite union of intervals.

##  3 Outline of the proof of Theorem 1.3

Here we briefly outline the proof of our main result. Throughout the proof, we
will suppose that ${\bm{d}}$ satisfies 1.1. For the sake of conciseness, this
will be implicitly assumed in all our statements.

The first step towards the result is to understand the distribution of short
cycle in $\mathbb{G}_{n}({\bm{d}}_{n})$, which is done in Section 4. This
section contains some already known results that are dispersed in the
literature and a secondary goal is to collect them all in a single document.
The most important conclusion of this part is Lemma 4.6, which states that the
asymptotic probability that $\mathbb{G}_{n}({\bm{d}}_{n})$ is acyclic admits a
nice expression in terms of the parameter $\nu$:

$p_{\mathrm{acyc}}({\bm{d}})=\sqrt{1-\nu}\cdot
e^{\frac{\nu}{2}+\frac{\nu^{2}}{4}}.$

The study of the cycle structure gives access to the distribution of the
unicyclic components of $\mathbb{G}_{n}({\bm{d}}_{n})$, which form the
fragment of the random graph. This is done in Section 5. We obtain an
expression for the probability a particular fixed graph is the fragment of
$\mathbb{G}_{n}({\bm{d}}_{n})$ (Corollary 5.2), and show that its size
distribution is tight, provided that $\nu<1$ (Corollary 5.8).

From here on, our strategy is similar to the one used in [17] to deal with the
binomial random graph $\mathbb{G}_{n}(c/n)$, however, the probabilistic
arguments here are more convoluted.

We split the proof of Theorem 1.3 into two parts. In the first part, developed
in Section 6, we show that $\overline{L({\bm{d}})}$ consists of a finite union
of closed intervals when $0<\nu<1$ (Lemma 6.4). Theorem 6.1 establishes that
the subcritical regime the random graph fragment determines whether a given
FO-property is satisfied or not. This is used to prove that
$\overline{L({\bm{d}})}$ is the set of partial sums of fragment probabilities
(Theorem 6.2). The desired result is obtained by Kakeya’s Criterion. Compared
to the approach in [17], fragment probabilities have a more complex structure
that heavily depends on the full degree sequence ${\bm{d}}_{n}$. This rules
out the possibility of using specific examples for fragments in our bounds,
which was the strategy in the binomial case. We overcome this difficulty,
roughly, by classifying fragments into classes depending on the amount of
cycles of each length they contain, and obtaining bounds for each whole class,
rather than for individual fragments.

In the second part, developed in Section 7, we establish a sharp threshold
phenomenon at $\nu=\nu_{0}$ for the property that
$\mathbb{G}_{n}({\bm{d}}_{n})$ has a limit probability set for FO-properties
that is dense in the unit interval, i.e. $\overline{L({\bm{d}})}=[0,1]$. The
constant $\nu_{0}$ is defined as the unique value of $\nu$ such that a random
graph with $\nu=\nu_{0}$ is acyclic with probability exactly $1/2$ (see Remark
1.6). This is done in Lemma 7.1 and its proof is a two-fold application of
Kakeya’s Criterion, distinguishing the cases $0<\nu<\nu_{0}$ and
$\nu\geq\nu_{0}$.

##  4 Cycle distribution

In this section we study the distribution of short cycles in
$\mathbb{CM}({\bm{d}})$. We stress that most of the results presented here are
already known and follow from well-established techniques. However these
results are scattered through the literature, and this section aims to provide
a self-contained compendium of the cycle distribution in the configuration
model. We will prove it under 1.1, but it is worth noticing that the
assumption (iv) is not needed for these results to hold (and similarly in
Section 5).

######  Lemma 4.1.

Let $H$ be a multigraph whose minimum degree is at least $2$. Let $h=|V(H)|$,
$h_{i}=|\\{v\in V(H):\deg(v)=i\\}|$, and $\ell=|E(H)|$. Let $X_{n}(H)$ be the
number of $H$-copies in $\mathbb{CM}_{n}({\bm{d}}_{n})$. Then

$\mathbb{E}\left[X_{n}(H)\right]\leq\Xi_{n}(H)e^{h\xi_{n}},$ (10)

where

$\Xi_{n}(H)\coloneqq\frac{(\widehat{n})_{h}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)\widehat{\lambda}_{n}^{h}\prod_{i=1}^{\ell}(m_{n}-2i+1)}\prod_{i\geq
0}\rho_{n,i}^{h_{i}},$ (11)

and $\xi_{n}=o(1)$ is a sequence depending only on $\Delta_{n}$ and $n$.

######  Remark.

It is significantly easier to prove (10) if we replace $\Xi_{n}(H)$ by

$\Xi^{\prime}_{n}(H)\coloneqq\frac{n^{h}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)\prod_{i=1}^{\ell}(m_{n}-2i+1)}\prod_{i\geq
0}\rho_{n,i}^{h_{i}},$ (12)

However, the stronger bound obtained with $\Xi_{n}(H)$ will be needed to show
the tightness of the random variable counting the number of cycles in the
configuration model.

###### Proof.

We estimate the number of possible sub-configurations $H^{\prime}$ isomorphic
to $H$. Fix a labelling $v_{1},\dots,v_{h}$ of $V(H)$. In order to choose
$H^{\prime}$, we begin by picking the vertices
$v^{\prime}_{1},\dots,v^{\prime}_{h}$ forming $V(H^{\prime})$, each one
labeled after a vertex in $H$.

In order to completely determine $H^{\prime}$, we need to pick a list of
$\deg(v_{i})$ half-edges incident to $v_{i}^{\prime}$ for each $i\in[h]$. This
yields a total of $\prod_{i\in[h]}(a_{i})_{\deg(v_{i})}$ choices of half-edges
for $H^{\prime}$, where $a_{i}=d_{v^{\prime}_{i}}$. Note that this is $0$
unless $d_{v^{\prime}_{i}}(n)\geq\deg(v_{i})$ for all $i\in[h]$. There are
exactly $\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)$ ways of choosing
vertices and half-edges that yield the same sub-configuration $H^{\prime}$.
Hence, the total number of possible sub-configurations of
$\mathbb{CM}_{n}({\bm{d}}_{n})$ isomorphic to $H$ is given by

$\frac{1}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}\sum_{a_{1},\dots,a_{h}\in\mathbb{N}}\sum_{\begin{subarray}{c}\\{v^{\prime}_{1},\dots,v^{\prime}_{h}\\}\in\binom{[n]}{h}\\\
d_{v^{\prime}_{i}}=a_{i},\,i\in[h]\end{subarray}}\prod_{i\in[h]}(a_{i})_{\deg(v_{i})}.$

In the sum, we first pick the degrees $a_{1},\dots,a_{h}$ of
$v^{\prime}_{1},\dots,v^{\prime}_{h}$ before choosing the vertices themselves.

Given any choice of $a_{1},\dots,a_{h}$, we define $b_{1},\dots,b_{k}$ as the
different numbers appearing in $a_{1},\dots,a_{h}$, in increasing order.
Observe that $k\leq\Delta_{n}$.

Given $i\in[k]$ define $c_{i}$ as the number of indices $j\in[h]$ such that
$a_{j}=b_{i}$. Then

$\sum_{\begin{subarray}{c}\\{v^{\prime}_{1},\dots,v^{\prime}_{h}\\}\in\binom{[n]}{h}\\\
d_{v^{\prime}_{i}}=a_{i},i\in[h]\end{subarray}}\prod_{i\in[h]}(a_{i})_{\deg(v_{i})}=\left(\prod_{i\in[k]}\prod_{0\leq
j<c_{i}}(n_{b_{i}}-j)\right)\prod_{i\in[h]}(a_{i})_{\deg(v_{i})}.$ (13)

We going to apply two technical lemmas, whose statement and proof can be found
in Appendix A. These will allow us to replace the expression inside the
parenthesis on the RHS of (13) by something more convenient. Let
$\alpha_{i}=n_{b_{i}}$ and $\beta_{i}=c_{i}$ for all $i\in[k]$ with
$\alpha=\sum_{i\in[k]}\alpha_{i}$ and $\beta=\sum_{i\in[k]}c_{i}=h$. By Lemma
A.1,

$\displaystyle\prod_{i\in[k]}\prod_{0\leq j<c_{i}}(n_{b_{i}}-j)$
$\displaystyle\leq(\alpha)_{h}\left(\prod_{i\in[h]}\frac{n_{a_{i}}}{\alpha}\right)\left(\prod_{h-k+1\leq
j<h}\frac{\alpha}{\alpha-j}\right)$
$\displaystyle\leq(\widehat{n})_{h}\left(\prod_{i\in[h]}\frac{n_{a_{i}}}{\widehat{n}}\right)\left(\prod_{h+1-t\leq
j<h}\frac{\widehat{n}}{\widehat{n}-j}\right),$

where $t=\min(\Delta_{n},h+1)$. For the second inequality we used that
$\alpha\leq\widehat{n}$ (since $H$ has minimum degree $2$) and that $k\leq t$.
Applying Lemma A.2 with $N=\widehat{n}$ and $a=h$, we obtain

$\displaystyle\prod_{i\in[k]}\prod_{0\leq j<c_{i}}(n_{b_{i}}-j)$
$\displaystyle\leq(\widehat{n})_{h}\left(\prod_{i\in[h]}\frac{n_{a_{i}}}{\widehat{n}}\right)e^{h\xi_{n}}=(\widehat{n})_{h}\widehat{\lambda}_{n}^{-h}\left(\prod_{i\in[h]}\frac{n_{a_{i}}}{n}\right)e^{h\xi_{n}},$

for some sequence $\xi_{n}=o(1)$ that only depends on $n$ and $\Delta_{n}$.

Replacing this last inequality into (13) we get

$\sum_{\begin{subarray}{c}\\{v^{\prime}_{1},\dots,v^{\prime}_{h}\\}\in\binom{[n]}{h}\\\
d_{v^{\prime}_{i}}=a_{i},i\in[h]\end{subarray}}\prod_{i\in[h]}(a_{i})_{\deg(v_{i})}\leq(\widehat{n})_{h}\widehat{\lambda}_{n}^{-h}\left(\prod_{i\in[h]}\frac{n_{a_{i}}}{n}(a_{i})_{\deg(v_{i})}\right)e^{\xi_{n}h}.$

Summing over all possible choices of $a_{1},\dots,a_{h}$, the number of
possible sub-configurations of $\mathbb{CM}_{n}({\bm{d}}_{n})$ isomorphic to
$H$ is bounded from above by

$\frac{(\widehat{n})_{h}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)\widehat{\lambda}_{n}^{h}}\left(\prod_{i\in[h]}\rho_{n,\deg(v_{i})}\right)e^{\xi_{n}h}.$

Finally, the probability that a given copy of $H$ is realized is
$1/\prod_{i\in[\ell]}(m_{n}-2i+1)$. We conclude that

$\displaystyle\mathbb{E}\left[X_{n}(H)\right]$
$\displaystyle\leq\frac{(\widehat{n})_{h}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)\widehat{\lambda}_{n}^{h}\prod_{i\in[\ell]}(m_{n}-2i+1)}\left(\prod_{i\in[h]}\rho_{n,\deg(v_{i})}\right)e^{\xi_{n}h}$
$\displaystyle=\Xi_{n}(H)e^{\xi_{n}h}.$

∎

######  Lemma 4.2.

Let $H$ be a multigraph. Using the notation of Lemma 4.1, it holds that

$\mathbb{E}\left[X_{n}(H)\right]=\left(1+O(1/n)\right)\frac{n^{h}}{m_{n}^{\ell}}\prod_{i\geq
0}\rho_{n,i}^{h_{i}}.$

###### Proof.

Recall that we can write

$\mathbb{E}\left[X_{n}(H)\right]=\frac{1}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)\prod_{i\in[\ell]}(m_{n}-2i+1)}\sum_{a_{1},\dots
a_{h}\in\mathbb{N}}\sum_{\begin{subarray}{c}\\{v^{\prime}_{1},\dots,v^{\prime}_{h}\\}\in\binom{[n]}{h}\\\
d_{v^{\prime}_{i}}=a_{i},i\in[h]\end{subarray}}\prod_{i\in[h]}(a_{i})_{\deg(v_{i})}.$

It holds that

$\displaystyle\prod_{i\in[h]}(n_{a_{i}}-h)(a_{i})_{\deg(v_{i})}$
$\displaystyle\leq\\!\\!\\!\sum_{\begin{subarray}{c}\\{v^{\prime}_{1},\dots,v^{\prime}_{h}\\}\in\binom{[n]}{h}\\\
d_{v^{\prime}_{i}}=a_{i},i\in[h]\end{subarray}}\prod_{i\in[h]}(a_{i})_{\deg(v_{i})}\leq\prod_{i\in[h]}n_{a_{i}}(a_{i})_{\deg(v_{i})}.$

Hence, we obtain the desired result

$\displaystyle\mathbb{E}\left[X_{n}(H)\right]$
$\displaystyle=\left(1+O\left(1/n\right)\right)\frac{1}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)m_{n}^{\ell}}\sum_{a_{1},\dots,a_{h}\in\mathbb{N}}\prod_{i\in[h]}n_{a_{i}}(a_{i})_{\deg(v_{i})}$
$\displaystyle=\left(1+O\left(1/n\right)\right)\frac{n^{h}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)m_{n}^{\ell}}\prod_{i\in[h]}\sum_{a_{i}\in\mathbb{N}}\frac{n_{a_{i}}}{n}(a_{i})_{\deg(v_{i})}$
$\displaystyle=\left(1+O\left(1/n\right)\right)\frac{n^{h}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)m_{n}^{\ell}}\prod_{i\in[h]}\rho_{n,\deg(v_{i})}^{h_{i}}.\qed$

From the previous lemma, we recover a classic result on random graphs.

######  Lemma 4.3.

Let $X_{n,k}$ be number of $k$-cycles in $\mathbb{CM}_{n}({\bm{d}}_{n})$.
Then, for any finite collection $k_{1},\dots,k_{l}$, the variables
$X_{n,k_{1}},\dots,X_{n,k_{l}}$ converge in distribution to independent
Poisson variables whose respective means are
$\xi_{k_{i}}:=\nu^{k_{i}}/2k_{i}$. In particular,

$\lim_{n\to\infty}\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{ is
simple})=e^{-\frac{\nu}{2}-\frac{\nu^{2}}{4}}.$ (14)

###### Proof.

We prove the first part of the statement, the second part follows easily from
it. We assume $\rho_{2}>0$. Otherwise, by 1.1.(iv), all vertices have degree
$0$ or $1$ and the result follows trivially. By the method of moments (Theorem
2.4), it suffices to show that for any $a_{1},\dots,a_{l}\in\mathbb{N}$,

$\lim_{n\to\infty}\mathbb{E}\left[\prod_{i=1}^{l}\binom{X_{n,k_{i}}}{a_{i}}\right]=\prod_{i=1}^{l}\frac{\xi_{k_{i}}^{a_{i}}}{a_{i}!}.$
(15)

We say that a multigraph $G$ is a non-degenerate union of unlabeled
multigraphs $H_{1},\dots,H_{t}$ if $G$ contains a copy $H^{\prime}_{i}$ of
$H_{i}$ for each $i\in[t]$, $V(G)=V(H^{\prime}_{1})\cup\dots\cup
V(H^{\prime}_{t})$ (note that this union is not necessarily disjoint), and the
$H_{i}$ are pairwise different (note that the $H_{i}^{\prime}$ can share some
edges). Let $\mathcal{H}$ be the class of all unlabeled multigraphs that are
non-degenerate unions of $a_{1}$ copies of $C_{k_{1}}$, $a_{2}$ copies of
$C_{k_{2}}$, and so on. Let $H_{*}\in\mathcal{H}$ be the graph formed by the
disjoint union of the corresponding cycles. Note that
$\operatorname{\mathrm{ex}}(H_{*})=0$ and $\operatorname{\mathrm{ex}}(H)>0$
for all other $H\in\mathcal{H}$. Given $H\in\mathcal{H}$, let $Y_{n}(H)$ be
the number of $H$-copies in $\mathbb{CM}_{n}({\bm{d}}_{n})$. The LHS in (15)
amounts to
$\sum_{H\in\mathcal{H}}\frac{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H_{*})}\mathbb{E}\left[Y_{n}(H)\right]$.
We show that asymptotically only $\mathbb{E}\left[Y_{n}(H_{*})\right]$
contributes to the value of this sum, and this expectation has the desired
value. Using Lemma 4.2 we get

$\mathbb{E}\left[Y_{n}(H)\right]=(1+O(1/n))\frac{n^{h}\,\prod_{i\in\mathbb{N}}(\rho_{n,i})^{h_{i}}}{(m_{n})^{\ell}\,\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}=O\left(n^{-\operatorname{\mathrm{ex}}(H)}\prod_{i\geq
0}\rho_{n,i}^{h_{i}}\right),$ (16)

where $h=|V(H)|,\ell=|E(H)|$, and $h_{i}=|\\{v\in V(H):\deg(v)=i\\}|$.

Let $H\in\mathcal{H}$ be an arbitrary multigraph different from $H_{*}$. We
show that $\mathbb{E}\left[Y_{n}(H)\right]=o(1)$. By 1.1,
$\Delta_{n}=o(n^{1/2})$ and $\rho_{n,2}=O(1)$. The former implies that
$\rho_{n,i}=o(n^{1/2}\rho_{n,i-1})$ for all $i\geq 2$, and then
$\rho_{n,i}=o(n^{(i-2)/2})$ for all $i\geq 3$. As $H\neq H_{*}$, it contains
some vertex of degree at least $3$ and we obtain

$\prod_{i\geq 0}\rho_{n,i}^{h_{i}}=o\left(\prod_{i\geq
3}n^{h_{i}(i-2)/2}\right)=o\left(n^{\operatorname{\mathrm{ex}}(H)}\right),$
(17)

where we used that $\sum_{i\geq 3}h_{i}(i-2)=\sum_{i\geq
0}h_{i}(i-2)=2\operatorname{\mathrm{ex}}(H)$, as $H$ has minimum degree at
least $2$. Plugging this last equation into (16), we obtain that
$\mathbb{E}\left[Y_{n}(H)\right]=o(1)$.

Now consider the case $H=H_{*}$. Since $H_{*}$ is $2$-regular and
$\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H_{*})=\prod_{i=1}^{l}a_{i}!(2k_{i})^{a_{i}}$,
Lemma 4.2 yields

$\mathbb{E}\left[Y_{n}(H_{*})\right]=\prod_{i=1}^{l}\frac{\xi_{k_{i}}^{a_{i}}}{a_{i}!}+o(1),$
(18)

using that $m_{n}/n=\rho_{n,1}$. Combining (16)–(18), we obtain the first part
of the lemma

$\lim_{n\to\infty}\mathbb{E}\left[\prod_{i=1}^{l}\binom{X_{n,k_{i}}}{a_{i}}\right]=\lim_{n\to\infty}\mathbb{E}\left[Y_{n}(H_{*})\right]=\prod_{i=1}^{l}\frac{\xi_{k_{i}}^{a_{i}}}{a_{i}!}.$

∎

Once we have determined the distribution of short cycles, we proceed to study
the probability of acyclicity. Recall that $\nu=1$ is the threshold for the
existence of a giant component. If $\nu\geq 1$, the largest component w.h.p.
contains an unbounded number of cycles and $p_{\mathrm{acyc}}({\bm{d}})=0$.
Thus we restrict to the subcritical case $\nu<1$.

######  Lemma 4.4.

Fix $k\in\mathbb{N}$. Let $X_{n,k}$ count the number of $k$-cycles in
$\mathbb{CM}_{n}({\bm{d}}_{n})$. Assume that $\nu<1$. Then the sequence
$(\mathbb{E}\left[X_{n,k}\right])_{n\in\mathbb{N}}$ is tight.

###### Proof.

Clearly, adding or removing isolated vertices to
$\mathbb{CM}_{n}({\bm{d}}_{n})$ does not affect the result, so without loss of
generality we may assume $\lambda_{0}=0$. If $\lambda_{1}=1$, by 1.1.(iv) all
vertices have degree $1$ and the result follows trivially as there are no
cycles in the model. Also, note that $\lambda_{1}\neq 0$, as this together
with $\lambda_{0}=0$ would imply that $\nu\geq 1$. So we assume that
$0<\lambda_{1}<1$. From Lemma 4.1 it follows that

$\displaystyle\mathbb{E}\left[X_{n,k}\right]\leq\;$
$\displaystyle\frac{(\widehat{n})_{k}}{2k\widehat{\lambda}_{n}^{k}\prod_{i=1}^{k}(m_{n}-2i+1)}\rho_{n,2}^{k}e^{k\xi_{n}}$
(19)

for all $n,k\in\mathbb{N}$, where the sequence $\xi_{n}=o(1)$ depends only on
$n$. Observe that $m_{n}\geq 2\widehat{n}+\lambda_{n,1}n$, so $m_{n}-1\geq
2\widehat{n}$ for sufficiently large $n$. This implies that
$(\widehat{n}-s)/(m_{n}-2s-1)\leq\widehat{n}/m_{n}=\widehat{\lambda}_{n}/\rho_{n,1}$
for all $0\leq s<n$. Thus, for sufficiently large $n$,

$\mathbb{E}\left[X_{n,k}\right]\leq\frac{(\nu_{n}e^{\xi_{n}})^{k}}{2k}.$

Choose $\nu^{\prime}\in(\nu,1)$. As $\lim_{n\to\infty}\nu_{n}e^{\xi_{n}}=\nu$,
there is some value $n^{\prime}\in\mathbb{N}$ such that
$\nu_{n}e^{\xi_{n}}<\nu^{\prime}$ for all $n\geq n^{\prime}$. Then

$\mathbb{E}\left[X_{n,k}\right]\leq\frac{(\nu^{\prime})^{k}}{2k}$

for all $n\geq n^{\prime}$. As the sum $\sum_{k\geq
1}\frac{(\nu^{\prime})^{k}}{2k}$ converges, this proves the result. ∎

######  Corollary 4.5.

Let $Z_{n}$ count the cycles in $\mathbb{CM}_{n}({\bm{d}}_{n})$. Assume that
$\nu<1$. Then,

$\lim_{n\to\infty}\mathbb{E}\left[Z_{n}\right]=-\frac{1}{2}\,\ln{(1-\nu)}.$
(20)

###### Proof.

Let $X_{n,k}$ count the number of $k$-cycles in
$\mathbb{CM}_{n}({\bm{d}}_{n})$. In Lemma 4.3 we showed that
$\mathbb{E}\left[X_{n,k}\right]=\nu^{k}/2k+o(1)$. By LABEL:{lem:tight} and
Lemma 4.4,

$\lim_{n\to\infty}\mathbb{E}\left[Z_{n}\right]=\lim_{n\to\infty}\sum_{k\geq
1}\mathbb{E}\left[X_{n,k}\right]=\sum_{k\geq
1}\lim_{n\to\infty}\mathbb{E}\left[X_{n,k}\right]=-\frac{1}{2}\,\ln{(1-\nu)}.$
(21)

∎

######  Lemma 4.6.

Assume $\nu<1$. Let $\bm{a}=(a_{\ell})_{\ell\in\mathbb{N}}$ be a sequence of
non-negative integers such that $\sum_{\ell\in\mathbb{N}}a_{\ell}<\infty$. The
following hold true:

  * (1)

Let $A_{n}$ be the event that $\mathbb{CM}_{n}({\bm{d}}_{n})$ contains exactly
$a_{\ell}$ $\ell$-cycles for all $\ell\geq 1$. Then

$\lim_{n\to\infty}\mathbb{P}(A_{n})=\sqrt{1-\nu}\prod_{\ell\in\mathbb{N}}\frac{(\nu^{\ell}/2\ell)^{a_{\ell}}}{a_{\ell}!}.$

In particular,

$\lim_{n\to\infty}\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{ is
acyclic})=\sqrt{1-\nu}.$

  * (2)

Let $B_{n}$ be the event that $\mathbb{G}_{n}({\bm{d}}_{n})$ contains exactly
$a_{\ell}$ $\ell$-cycles for all $\ell\geq 3$. Then

$\lim_{n\to\infty}\mathbb{P}(B_{n})=\sqrt{1-\nu}\cdot
e^{\frac{\nu}{2}+\frac{\nu^{2}}{4}}\prod_{\ell\geq
3}\frac{(\nu^{\ell}/2\ell)^{a_{\ell}}}{a_{\ell}!}.$

In particular,

$\lim_{n\to\infty}\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{ is
acyclic})=\sqrt{1-\nu}\cdot e^{\frac{\nu}{2}+\frac{\nu^{2}}{4}}.$

###### Proof.

We will prove (1). Statement (2) follows from the fact that
$\mathbb{G}_{n}({\bm{d}}_{n})$ is distributed like
$\mathbb{CM}_{n}({\bm{d}}_{n})$ conditioned on the absence of $1$-cycles and
$2$-cycles, whose probability we computed in LABEL:{thm:cycle_distribution}.
Let $X_{n,k}$ count the number of $k$-cycles in
$\mathbb{CM}_{n}({\bm{d}}_{n})$ and $\xi_{k}=\nu^{k}/2k$. Let $\epsilon>0$ be
arbitrarily small. It suffices to prove that, if $n$ is large enough,

$\left|\mathbb{P}(A_{n})-\sqrt{1-\nu}\prod_{\ell\in\mathbb{N}}\frac{\xi_{\ell}^{a_{\ell}}}{a_{\ell}!}\right|<\epsilon.$
(22)

Let $K$ be a sufficiently large constant satisfying both

$\displaystyle\left|\left(\prod_{k=1}^{K}e^{-\xi_{k}}\cdot\frac{\xi_{k}^{a_{k}}}{a_{k}!}\right)-\left(\sqrt{1-\nu}\prod_{k\geq
1}\frac{\xi_{k}^{a_{k}}}{a_{k}!}\right)\right|<\epsilon/3$ (23)

and

$\displaystyle\mathbb{P}\big{(}\sum_{k>K}X_{n,k}>0\big{)}<\epsilon/3,\quad\text{
for all $n\in\mathbb{N}$}.$ (24)

The property in (23) can be attained for a large $K$ because, inside the
absolute value, for $\nu<1$, the right term contains the limit (as
$K\to\infty$) of the left term. The existence of $K$ satisfying (24) follows
from $(\mathbb{E}\left[X_{n,k}\right])_{n\in\mathbb{N}}$ being tight for all
$k\in\mathbb{N}$, as shown in Corollary 4.5, and Markov’s inequality. Indeed,
by tightness, there is some $K$ for which
$\sum_{k>K}\mathbb{E}\left[X_{n,k}\right]<\epsilon/3$ uniformly in $n$, and
then
$\mathbb{P}\big{(}\sum_{k>K}X_{n,k}>0\big{)}\leq\mathbb{E}\left[\sum_{k>K}X_{n,k}\right]\leq\epsilon/3$
uniformly in $n$ as well.

We can write $A_{n}=\bigcap_{k\geq 1}\\{X_{n,k}=a_{k}\\}$, and
$\mathbb{P}(A_{n})=\lim_{k\to\infty}p_{n,k}$, where
$p_{n,k}=\mathbb{P}(\bigcap_{i=1}^{k}\\{X_{n,i}=a_{i}\\})$. The intersection
bound and (24) imply that $\mathbb{P}(A_{n})>p_{n,K}-\epsilon/3$ for all
$n\in\mathbb{N}$. Moreover, the sequence $(p_{n,k})_{k\geq 1}$ is
monotonically decreasing, so $\mathbb{P}(A_{n})\leq p_{n,K}$ for all
$n\in\mathbb{N}$. It follows that,

$\lvert\mathbb{P}(A_{n})-p_{n,K}\rvert<\epsilon/3$ (25)

However, by Lemma 4.3, for $n$ large enough

$\left|p_{n,K}-\prod_{k=1}^{K}e^{-\xi_{k}}\frac{\xi_{k}^{a_{k}}}{a_{k}!}\right|<\epsilon/3.$

Using (23) here yields (22) and completes the proof. ∎

We finally show that there are no complex components (i.e., components with
positive excess).

######  Theorem 4.7.

Assume $\nu<1$. Then a.a.s there are no connected components containing more
than one cycle in $\mathbb{CM}_{n}({\bm{d}}_{n})$.

###### Proof.

As in the proof of Lemma 4.4, we will assume that $\lambda_{0}=0$ and
$\lambda_{1}<1$, which in turn imply that $\rho_{1}>1$ and $n-i/m_{n}-2i+1\leq
1/\rho_{n,1}$ for sufficiently large $n\in\mathbb{N}$ for all $i\geq 1$.

The configuration $\mathbb{CM}_{n}({\bm{d}}_{n})$ has two cycles lying in the
same component if and only if it has some subgraph belonging to one of the
following classes:

  1. (I)

$H^{(1)}_{i,j,k}:$ An $i$-cycle and a $j$-cycle, disjoint, with a path of
length $k\geq 1$ joining a vertex from each cycle.

  2. (II)

$H^{(2)}_{i,j,k}:$ An $i$-cycle and a $j$-cycle sharing a path of length
$k\geq 1$.

  3. (III)

$H^{(3)}_{i,j}:$ An $i$-cycle and a $j$-cycle sharing a single vertex.

We show that w.h.p. none of these subgraphs appear in
$\mathbb{CM}_{n}({\bm{d}}_{n})$ using the first moment method. Let us consider
Class-(I) first. Let $X^{(1)}_{n;i,j,k}$ count the number of copies of
$H^{(1)}_{i,j,k}$ in $\mathbb{CM}_{n}({\bm{d}}_{n})$. The multigraph
$H^{(1)}_{i,j,k}$ has $i+j+k$ edges and $h=i+j+k-1$ vertices, among which two
have degree $3$ and the rest have degree $2$. Observe that if $h>\widehat{n}$
then $\mathbb{E}\left[X^{(1)}_{n;i,j,k}\right]=0$. Suppose otherwise. Choose
some $\nu^{\prime}\in(\nu,1)$. By Lemma 4.2, for sufficiently large $n$,
independently of $h$

$\displaystyle\mathbb{E}\left[X^{(1)}_{n;i,j,k}\right]$
$\displaystyle\leq\;\frac{(\widehat{n})_{h}\widehat{\lambda}_{n}}{\prod_{s\in[h+1]}(m_{n}-2s+1)}\rho_{n,2}^{h-2}\rho_{n,3}^{2}e^{h\xi_{n}}$
$\displaystyle\leq(\nu_{n})^{h}\frac{\Delta_{n}^{2}}{(m_{n}-2h-1)}e^{h\xi_{n}}$
$\displaystyle\leq(\nu^{\prime}_{n})^{h}\frac{\Delta_{n}^{2}}{(\lambda_{n,1}n-1)},$
(26)

where in the second inequality we have used that
$\rho_{n,3}\leq\Delta_{n}\rho_{n,2}$.

Let $X^{(1)}_{n;h}$ be the sum of all variables $X^{(1)}_{n;i,j,k}$ with
$i+j+k-1=h$. There are at most $h^{2}$ such choices for $i,j,k$, so
$\mathbb{E}\left[X^{(1)}_{n;h}\right]=O(h^{2}(\nu_{n}^{\prime})^{h}\Delta_{n}^{2}/n)$.
It follows that

$\sum_{h\geq
3}\mathbb{E}\left[X^{(1)}_{n;h}\right]=O\Big{(}\frac{\Delta_{n}^{2}}{n}\sum_{h\geq
3}h^{2}(\nu_{n}^{\prime})^{h}\Big{)}=O\Big{(}\frac{\Delta_{n}^{2}}{n}\Big{)}=o(1).$

Using Markov’s inequality we obtain that w.h.p. no Class-(I) subgraph occurs
in $\mathbb{CM}_{n}({\bm{d}}_{n})$. In an analogous way, it can be shown that
the expected numbers of Class-(II) and Class-(III) subgraphs in
$\mathbb{CM}_{n}({\bm{d}}_{n})$ are $O\left(\Delta_{n}^{2}/n\right)$, and
w.h.p. $\mathbb{CM}_{n}({\bm{d}}_{n})$ contains no subgraph from those
subclasses either. This proves the result. ∎

###  4.1 Previous results

In this section we included a self-contained description of the cycle
distribution on $\mathbb{CM}({\bm{d}})$ and the probability
$\mathbb{CM}({\bm{d}})$ and $\mathbb{G}({\bm{d}})$ are acyclic. As we
explained, most of these results were already known in the literature and our
aim was to compile them in a single document. To conclude this section, we
give references where some of these results can be found. Note that all the
results that we refer to below, hold w.h.p. and under similar conditions on
${\bm{d}}$ as 1.1, unless otherwise stated.

The expected number of copies of a given small subgraph (Lemma 4.2), as well
as the probability a particular cycle appears, are well-studied in the
literature [4]. The result stated here can be found with a similar proof in
the unpublished notes by Bordenave [5, Theorem 2.4]. The refined upper bound
(Lemma 4.1), needed to show tightness (Lemma 4.4), was not available in the
literature, to our best knowledge.

For graphs other than trees or unicyclic ones, their expected number tends to
zero as $n$ tends to infinity. McKay [21] studied the probability of small
subgraph appearance on dense random graphs with given degrees.

That the joint distribution of cycles up to length $k$ converges to a vector
of independent Poisson random variables is well known. This was originally
proved in regular setting by Bollobás [2], and, independently, by Wormald
[24]. The extension to the configuration model can be found in [5, Theorem
2.18] and [12, Exercise 4.16]. Determining the probability that the
configuration model is simple is one of earliest results in the area [1, 2],
see [14] for the version in Theorem 2.1.

In the subcritical regime, the result that all cycles have length bounded in
probability (LABEL:{lem:cycle_count_conf}), which is equivalent to the
tightness exhibited in Lemma 4.4, can be found in [6, Lemma 5.3]. The
existence of no complex components in $\mathbb{CM}_{n}({\bm{d}}_{n})$, given
by Theorem 4.7, can be found in [10]. It is worth stressing that the proof
strategy there is quite different: they analyze a process that exposes a
connected component in $\mathbb{CM}_{n}({\bm{d}}_{n})$, vertex by vertex,
using martingale concentration inequalities, which requires additional
constraints in the maximum degree, with respect to 1.1.

##  5 Fragment Distribution

In this section we study the distribution of unicyclic components of
$\mathbb{CM}_{n}({\bm{d}}_{n})$ when $\nu<1$. To our best knowledge, this
distribution has not been studied yet.

Let $\mathrm{Frag}^{*}_{n}=\mathrm{Frag}(\mathbb{CM}_{n}({\bm{d}}_{n}))$ and
$\mathrm{Frag}_{n}=\mathrm{Frag}(\mathbb{G}_{n}({\bm{d}}_{n}))$ be the
subgraphs composed by the union of all unicyclic connected components in
$\mathbb{CM}_{n}({\bm{d}}_{n})$ and $\mathbb{G}_{n}({\bm{d}}_{n})$,
respectively.

######  Theorem 5.1.

Suppose $\nu<1$. If $H$ is a fragment, then

$\lim_{n\to\infty}\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq
H)=\frac{\sqrt{1-\nu}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}\prod_{i\geq
0}\left(\frac{\lambda_{i}i!}{\rho_{1}}\right)^{h_{i}},$

where $h_{i}=|\\{v\in V(H):\deg(v)=i\\}|$.

###### Proof.

Let $h=|V(H)|$ and

$V(H)=\\{v_{1},\dots,v_{h}\\}$. For each $v_{i}\in V(H)$, fix some ordering of
the half-edges incident to $v_{i}$. Define $\mathcal{H}_{n}$ as the set of
possible isolated $H$-copies in $\mathbb{CM}_{n}({\bm{d}}_{n})$. In order to
pick a copy $H^{\prime}\in\mathcal{H}_{n}$, we first select the vertices
$v^{\prime}_{1},\dots,v^{\prime}_{h}$. As we want the copy to be isolated, we
require $d_{v^{\prime}_{i}}=\deg(v_{i})$ for all $i\in[h]$. In order to
completely determine $H^{\prime}$ we give an ordering of the half-edges
incident to each vertex $v^{\prime}_{i}$. Afterwards, half-edges should be
matched according to the half-edge orderings defined for $H$. Observe that
there are exactly $\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)$ ways of
picking vertices and half-edge orderings that result in the same
subconfiguration $H^{\prime}$. Hence,

$|\mathcal{H}_{n}|=\frac{\prod_{i\geq
0}(n_{i})_{h_{i}}(i!)^{h_{i}}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}.$
(27)

Given $H^{\prime}\in\mathcal{H}_{n}$, let $A_{n}(H^{\prime})$ be the event

that $H^{\prime}\subseteq\mathbb{CM}_{n}({\bm{d}}_{n})$ and
$\mathbb{CM}_{n}({\bm{d}}_{n})\setminus V(H^{\prime})$ is acyclic. Observe
that the events $A_{n}(H^{\prime})$ are disjoint. Let $P_{n}$ be the event
that no component in $\mathbb{CM}_{n}({\bm{d}}_{n})$ contains more than one
cycle. Then the event $(\mathrm{Frag}^{*}_{n}\simeq H)\cap P_{n}$ coincides
with the union of the events $A_{n}(H^{\prime})$ for all
$H^{\prime}\in\mathcal{H}_{n}$. Thus, by Theorem 4.7,

$\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq
H)=o(1)+\sum_{H^{\prime}\in\mathcal{H}_{n}}\mathbb{P}(A_{n}(H^{\prime})).$
(28)

Recall that $d_{v_{i}^{\prime}}=\deg(v_{i})$ for all
$H^{\prime}\in\mathcal{H}_{n}$ and all $i\in[h]$. Thus, by symmetry, the
probability of $A_{n}(H^{\prime})$ is the same for all
$H^{\prime}\in\mathcal{H}_{n}$. Fix an $H$-copy $H^{\prime}\in\mathcal{H}_{n}$
for each $n\in\mathbb{N}$. Combining (27) and (28) we obtain

$\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq H)=\frac{\prod_{i\geq
0}(n_{i})_{h_{i}}(i!)^{h_{i}}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}\mathbb{P}(A_{n}(H^{\prime}))+o(1).$
(29)

Let us examine now the probability of $A_{n}(H^{\prime})$. Let
$\widehat{G}_{n}=\mathbb{CM}_{n}({\bm{d}}_{n})[[n]\setminus
V(H^{\prime}_{n})]$. As $H$ is a fragment, by definition

$\mathbb{P}(A_{n}(H^{\prime}))=\frac{1}{\prod_{i=1}^{h}(m_{n}-2i+1)}\mathbb{P}\left(\widehat{G}_{n}\text{
is
acyclic}\;\middle|\;H^{\prime}\subseteq\mathbb{CM}_{n}({\bm{d}}_{n})\right).$
(30)

Let $\widehat{{\bm{d}}}_{n-h}$ be the degree sequence obtained by removing the
vertices of $V(H^{\prime}_{n})$ from $[n]$ and relabeling the remaining
vertices as $[n-h]$. Note that $(\widehat{G}_{n}\mid
H^{\prime}_{n}\subseteq\mathbb{CM}_{n}({\bm{d}}_{n}))\sim\mathbb{CM}_{n-h}(\widehat{{\bm{d}}}_{n-h})$.
Clearly, the degree sequence $\widehat{{\bm{d}}}$ satisfies 1.1. Moreover, it
is easy to see that the first and second moments of the related degree
distribution have the same limits as those of ${\bm{d}}$ (that is, $\rho_{1}$
and $\rho_{2}$) as $h=O(1)$. By Lemma 4.6,

$\displaystyle\mathbb{P}\left(\widehat{G}_{n}\text{ is
acyclic}\;\middle|\;H^{\prime}_{n}\subseteq\mathbb{CM}_{n}({\bm{d}}_{n})\right)$
$\displaystyle=\mathbb{P}\left(\mathbb{CM}_{n-h}(\widehat{{\bm{d}}}_{n-h})\text{
is acyclic}\right)$ (31) $\displaystyle=\sqrt{1-\nu}+o(1).$

Putting (29), (30) and (31) together, we conclude the proof of the theorem

$\displaystyle\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq H)$
$\displaystyle=\frac{\sqrt{1-\nu}\prod_{i\geq
0}(n_{i})_{h_{i}}(i!)^{h_{i}}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)\prod_{i=1}^{h}(m_{n}-2i+1)}+o(1)$
(32)
$\displaystyle=\frac{\sqrt{1-\nu}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}\prod_{i\geq
0}\left(\frac{\lambda_{i}i!}{\rho_{1}}\right)^{h_{i}}+o(1).\qed$

The following corollary states that the fragment of
$\mathbb{G}_{n}({\bm{d}}_{n})$ is asymptotically distributed like the fragment
of $\mathbb{CM}_{n}({\bm{d}}_{n})$, ignoring the components containing loops
or double edges.

######  Corollary 5.2.

Assume that $\nu<1$. Let $G$ be a simple fragment. Then

$\lim_{n\to\infty}\mathbb{P}(\mathrm{Frag}_{n}\simeq
G)=\frac{\sqrt{1-\nu}\cdot
e^{\frac{\nu}{2}+\frac{\nu^{2}}{4}}}{\operatorname{\mathrm{aut}}(G)}\prod_{i\geq
0}\left(\frac{\lambda_{i}i!}{\rho_{1}}\right)^{g_{i}},$

where $g_{i}=|\\{v\in V(G):\deg(v)=i\\}|$.

###### Proof.

Let $A_{n}$ be the event that $\mathbb{CM}_{n}({\bm{d}}_{n})$ is simple (i.e.,
it contains neither loops nor multiple edges). By definition,

$\mathbb{P}(\mathrm{Frag}_{n}\simeq G)=\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq
G\,\mid\,A_{n})=\frac{\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq
G\,\cap\,A_{n})}{\mathbb{P}(A_{n})}.$

When $\mathbb{CM}_{n}({\bm{d}}_{n})$ has no complex components, the event
$(\mathrm{Frag}^{*}_{n}\simeq G)\,\cap\,A_{n}$ is equivalent to
$\mathrm{Frag}^{*}_{n}\simeq G$. Therefore, using Theorem 4.7, we obtain

$\mathbb{P}(\mathrm{Frag}_{n}\simeq
G)=\frac{\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq G)}{\mathbb{P}(A_{n})}+o(1).$

By Corollary 4.5, $\mathbb{P}(A_{n})=e^{-\nu/2-\nu^{2}/4}+o(1)$. This,
together with the previous theorem and the fact that
$\operatorname{\mathrm{aut}}(G)=\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(G)$
when $G$ is simple, proves the result. ∎

From now on let $p^{*}_{n}(H)=\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq H)$,
$p_{n}(G)=\mathbb{P}(\mathrm{Frag}_{n}\simeq G)$,
$p^{*}(H)=\lim_{n\to\infty}p^{*}_{n}(H)$, and
$p(G)=\lim_{n\to\infty}p_{n}(G)$, for all unlabeled fragments $H$, and all
unlabeled simple fragments $G$. We recall that, as proven in Theorem 5.1,

$p^{*}(H)=\frac{\sqrt{1-\nu}}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}\prod_{i\geq
0}\left(\frac{\lambda_{i}i!}{\rho_{1}}\right)^{h_{i}},$

where $h_{i}=|\\{v\in V(H):\deg(v)=i\\}|$. Our next goal is to show that the
numbers $p^{*}(H)$ define a distribution over unlabeled fragments, that is
$\sum_{H}p^{*}_{H}=1$.

######  Definition 5.3.

A lexicographically labeled forest (LLFo) is a rooted forest $F$ such that

  * (1)

if $F$ has $r$ components, the roots $v_{1},\dots v_{r}$ are labeled by $[r]$
in an arbitrary way;

  * (2)

if a vertex $v$ with label $\ell\in\mathbb{N}^{*}$ has children
$v_{1},\dots,v_{j}$ (in some arbitrary order), then they are labeled by $\ell
1,\dots,\ell j$ respectively, where by $\ell i$ we mean the concatenation of
the label $\ell$ with $i$.

Given an integer $K\geq 1$, we use $\textsc{Fo}^{K}_{\text{lex}}$ to denote
the set of LLFo with at least $K$ components.

Let $\bm{D}=(D_{r},D)$ where $D_{r}$ and $D$ are two probability distributions
over non-negative integers, and let $F$ be an LLFo. We define

$p^{\bm{D}}(F):=\prod_{i\geq 0}\mathbb{P}(D_{r}=i)^{f^{r}_{i}}\prod_{i\geq
1}\mathbb{P}(D=i-1)^{f_{i}},$ (33)

where $f^{r}_{i}$ denotes the number of roots in $F$ whose degree is $i$ and
$f_{i}$ denotes the number of non-root vertices in $F$ of degree $i$.
Equivalently, $p^{\bm{D}}(F)$ is the probability that $F$ is generated by a
branching process where the first generation has $r$ individuals whose
offspring is distributed as $D_{r}$, and the other elements have offspring
distribution $D$. It is well known that such process has extinction
probability $1$ whenever $\mathbb{E}\left[D\right]<1$ [13, Theorem 3.1]. We
can rephrase that fact as follows.

######  Lemma 5.4.

Let $\bm{D}=(D_{r},D)$ where $D_{r}$ and $D$ are two probability distributions
over non-negative integers satisfying $\mathbb{E}\left[D\right]<1$. Fix an
integer $K\geq 1$. Then

$\sum_{T\in\textsc{Fo}^{K}_{\text{lex}}}p^{\bm{D}}(F)=1.$

Fragments can be seen as collections of cycles where a tree “grows out” from
each vertex. Therefore, we can imagine the edges of the trees as being
oriented towards the cycle in their connected component. For a vertex $v$ in
the fragment that is not in any of the cycles, we define its parent to be its
unique vertex $u$ that $v$ points to.

We now extend the definition of LLFo to fragments.

######  Definition 5.5.

A lexicographically labeled fragment (LLFr) $H$ is a fragment where

  * (1)

if $H$ has $r$ cycles, they are labeled by $[r]$ in a non-decreasing order
according to their lengths (ties are resolved arbitrarily);

  * (2)

if $v_{1},\dots,v_{k}$ are the vertices in a $k$-cycle with label
$\ell\in[r]$, they are labelled by $\ell 1,\dots,\ell k$ following an
arbitrary cyclic ordering;

  * (3)

if a vertex $v$ with label $\ell\in\mathbb{N}^{*}$ has children
$v_{1},\dots,v_{j}$, they are labeled by $\ell 1,\dots,\ell j$ following some
arbitrary order.

Next lemma computes the number of LLFr isomorphic to a given fragment.

######  Lemma 5.6.

Let $H$ be a fragment. For each $k\geq 1$, let $a_{k}$ be the number of
$k$-cycles in $H$. For each $i\geq 1$, let $h^{r}_{i}$ be the number of
vertices of degree $i$ lying in some cycle of $H$, and let $h_{i}$ be the
number of vertices of degree $i$ that are not in any cycle of $H$. Then the
number of LLFr isomorphic to $H$ is

$\gamma(H):=\frac{1}{\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)}\left(\prod_{k\geq
1}a_{k}!(2k)^{a_{k}}\right)\left(\prod_{i\geq
2}(i-2)!^{h^{r}_{i}}\right)\left(\prod_{i\geq 1}(i-1)!^{h_{i}}\right).$ (34)

###### Proof.

First, note that if $\phi:V(H)\rightarrow V(H)$ is an automorphism of some
fragment $H$ and $\hat{H}$ is an LLFr isomorphic to $H$ then permuting the
labels in $\hat{H}$ according to $\phi$ yields the same LLFr. Hence, to derive
$\gamma(H)$ we will count all the ways of labelling $V(H)$ to obtain an LLFr,
and divide that number by $\operatorname{\mathrm{aut}}(H)$. For a fragment $H$
the only multi-edges are those involved in $2$-cycles, which have multiplicity
exactly two. By (8), we can write
$\operatorname{{\mathrm{aut}_{\mathrm{h.e.}}}}(H)=\operatorname{\mathrm{aut}}(H)2^{a_{1}}2^{a_{2}}$,
and the RHS of (34) can be expressed as

$\frac{1}{\operatorname{\mathrm{aut}}(H)}\left(\prod_{k\geq
1}a_{k}!\right)\left(2^{a_{2}}\prod_{k\geq
3}(2k)^{a_{k}}\right)\left(\prod_{i\geq
2}(i-2)!^{h^{r}_{i}}\right)\left(\prod_{i\geq 1}(i-1)!^{h_{i}}\right).$

We argue that the number of ways we can label $H$ to obtain an LLFr
corresponds to the product of the parentheses above. Such labelling is
uniquely given by (1) an ordering of the cycles in $H$ that is non-decreasing
with respect to their lengths, (2) a cyclic ordering of the vertices inside of
each cycle, and (3) an arbitrary ordering of each vertex’s children. There are
$\prod_{k\geq 1}a_{k}!$ ways of achieving (1). Given a $k$-cycle, there are
exactly $2$ cyclic orderings of its vertices when $k=2$, and $2k$ when $k\geq
3$. Thus, there are $2^{a_{2}}\prod_{k\geq 3}(2k)^{a_{k}}$ ways of achieving
(2). Finally, let us consider (3). Given a vertex of degree $i$ lying on a
cycle, there are exactly $(i-2)!$ ways of ordering its children. Similarly,
there are $(i-1)!$ ways of ordering the children of a vertex of degree $i$ not
lying on a cycle. Hence, there are $\left(\prod_{i\geq
2}(i-2)!^{h^{r}_{i}}\right)\left(\prod_{i\geq 1}(i-1)!^{h_{i}}\right)$ ways of
achieving (3). This shows the result.

∎

We can now show that $p^{*}$ is a probability distribution.

######  Theorem 5.7.

Assume $\nu<1$. Then $\sum_{H}p^{*}(H)=1$, where $H$ ranges over all finite
unlabeled fragments.

###### Proof.

Fix $\bm{a}=(a_{k})_{k\geq 1}$ a sequence of non-negative integers and suppose
$A=\sum_{k\geq 1}ka_{k}<\infty$.

Let $\textsc{Fr}^{\bm{a}}$ be the set of all unlabeled fragments containing
exactly $a_{k}$ $k$-cycles for each $k\geq 1$. Then, by Lemma 4.6, to prove
the statement it is enough to show that

$\sum_{H\in\textsc{Fr}^{\bm{a}}}p^{*}(H)=\sqrt{1-\nu}\,\prod_{k\geq
1}\frac{(\nu^{k}/2k)^{a_{k}}}{a_{k}!}.$ (35)

Similarly, let $\textsc{Fr}^{\bm{a}}_{\text{lex}}$ be the set of all LLFr
containing exactly $a_{k}$ $k$-cycles for each $k\geq 1$. By Lemma 5.6, we can
write

$\sum_{H\in\textsc{Fr}^{\bm{a}}}p^{*}(H)=\sum_{H\in\textsc{Fr}^{\bm{a}}_{\text{lex}}}\frac{p^{*}(H)}{\gamma(H)},$
(36)

where $\gamma(H)$ is given in (34). Given
$H\in\textsc{Fr}^{\bm{a}}_{\text{lex}}$ and $i\geq 1$, we write $h^{r}_{i}$
for the number of vertices of degree $i$ lying in some cycle of $H$, and
$h_{i}$ for the number of vertices of degree $i$ in $H$ that are not in a
cycle. Since $\sum_{i\geq 2}h_{i}^{r}=\sum_{k\geq 1}ka_{k}$, it follows that,

$\displaystyle\frac{p^{*}(H)}{\gamma(H)}\,$
$\displaystyle=\,\sqrt{1-\nu}\prod_{k\geq
1}\frac{1}{a_{k}!(2k)^{a_{k}}}\prod_{i\geq
2}\left(\frac{\lambda_{i}i(i-1)}{\rho_{1}}\right)^{h^{r}_{i}}\prod_{i\geq
1}\left(\frac{\lambda_{i}i}{\rho_{1}}\right)^{h_{i}}$
$\displaystyle=\,\sqrt{1-\nu}\prod_{k\geq
1}\frac{\nu^{ka_{k}}}{a_{k}!(2k)^{a_{k}}}\prod_{i\geq
2}\left(\frac{\lambda_{i}i(i-1)}{\rho_{2}}\right)^{h^{r}_{i}}\prod_{i\geq
1}\left(\frac{\lambda_{i}i}{\rho_{1}}\right)^{h_{i}}.$ (37)

Let $v_{1},\dots,v_{A}$ be the vertices belonging to the cycles in $H$,
ordered in lexicographical order. We define the LLFo $F_{H}$, as the one
containing $A$ trees, corresponding to the ones growing out of
$v_{1},\dots,v_{A}$ in that order. Observe that the map $H\mapsto F_{H}$ is a
bijection between $\textsc{Fr}^{\bm{a}}_{\text{lex}}$ and the set
$\textsc{Fo}^{A}_{\text{lex}}$ of LLFo consisting of $A$ components. See
Figure 1 for an example.

Consider the following distributions $D$ and $D_{r}$ over non-negative
integers:

$\displaystyle\mathbb{P}(D_{r}=i-2)$
$\displaystyle=\frac{i(i-1)\lambda_{i}}{\rho_{2}},\;\text{ for all }i\geq 2,$
$\displaystyle\mathbb{P}(D=i-1)$
$\displaystyle=\frac{i\lambda_{i}}{\rho_{1}},\quad\qquad\,\text{ for all
}i\geq 1.$

Using (33), we can rewrite (37) as

$\frac{p^{*}(H)}{\gamma(H)}=\sqrt{1-\nu}\Big{(}\prod_{k\geq
1}\frac{\nu^{ka_{k}}}{a_{k}!(2k)^{a_{k}}}\Big{)}p_{F_{H}}^{\bm{D}}.$

From (36) and using the observation that $H\mapsto F_{H}$ is a bijection
between $\textsc{Fr}^{\bm{a}}_{\text{lex}}$ and
$\textsc{Fo}^{A}_{\text{lex}}$, we obtain

$\sum_{H\in\textsc{Fr}^{\bm{a}}}p^{*}(H)=\sqrt{1-\nu}\prod_{k\geq
1}\frac{(\nu^{k}/2k)^{a_{k}}}{a_{k}!}\sum_{F\in\textsc{Fo}^{A}_{\text{lex}}}p_{F}^{\bm{D}}=\sqrt{1-\nu}\prod_{k\geq
1}\frac{(\nu^{k}/2k)^{a_{k}}}{a_{k}!}.$

In the last equality we used that
$\sum_{F\in\textsc{Fo}^{A}_{\text{lex}}}p_{F}^{\bm{D}}=1$ by Lemma 5.4, since
$\mathbb{E}\left[D\right]=\nu<1$.

(a) An LLFr.

(b) The corresponding LLFo.

Figure 1: Example of the map $H\mapsto F_{H}$.

∎

######  Corollary 5.8.

Assume $\nu<1$. Let Fr be the class of unlabeled fragments and let
$H\in\textsc{Fr}$. Then the sequences $(H\mapsto
p^{*}_{n}(H))_{n\in\mathbb{N}}$ and $(H\mapsto p_{n}(H))_{n\in\mathbb{N}}$ of
real maps over Fr are tight. In particular, for all sequences $\omega_{n}$
tending to infinity as $n\to\infty$,
$\mathbb{P}(|\mathrm{Frag}^{*}_{n}|\geq\omega_{n})=o(1)$ and
$\mathbb{P}(|\mathrm{Frag}_{n}|\geq\omega_{n})=o(1)$.

###### Proof.

The last part of the statement follows from the definition of tight sequences.
The fact that $(H\mapsto p^{*}_{n}(H))_{n\in\mathbb{N}}$ is tight follows from
Theorem 5.7. To see that $(H\mapsto p_{n}(H))_{n\in\mathbb{N}}$ is tight as
well, note that by definition

$p_{n}(H)\leq\frac{\mathbb{P}(\mathrm{Frag}^{*}_{n}\simeq
H)}{\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{ is simple})}$ (38)

and $\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{ is simple})\geq
e^{-\nu/2-\nu^{4}/4}-o(1)>0$. Thus $p_{n}(H)\leq Cp^{*}_{n}(H)$ and since the
latter sequence is tight, so is the former one. ∎

##  6 First part of Theorem 1.3: A finite union of intervals

In this section we show that $\overline{L({\bm{d}})}$, the closure of the
limit probabilities, is a union of closed intervals. We postpone the
supercritical and critical cases $\nu\geq 1$ for the next section, and focus
on the subcritical case $0<\nu<1$. The key point is that, in the subcritical
regime, the $\operatorname{\textsc{FO}}$ properties of
$\mathbb{G}_{n}({\bm{d}}_{n})$ are determined w.h.p. by its fragment
$\mathrm{Frag}_{n}$. This is (implicitly) stated in [18, Lemma 3.12]. However,
the results in [18, 20] contain slight inaccuracies, that will be discussed in
Section 8.

######  Theorem 6.1 (Zero-one Law for FO in
$\mathbb{G}({\bm{d}})=(\mathbb{G}_{n}({\bm{d}}_{n}))_{n\in\mathbb{N}}$).

Suppose that $\nu<1$. Let $H\in\textsc{Fr}$ be an unlabelled fragment, and
$\varphi\in\operatorname{\textsc{FO}}$ be a sentence. Then

$\lim_{n\to\infty}\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{ satisfies
}\varphi\,\mid\,\mathrm{Frag}_{n}\simeq H)\in\\{0,1\\}.$

Recall that when $\nu<1$ and $H\in\textsc{Fr}$,
$p_{n}(H)=\mathbb{P}(\mathrm{Frag}_{n}\simeq H)$, and
$p(H)=\lim_{n\to\infty}p_{n}(H)$. We now prove that $L({\bm{d}})$ equals the
set of partial sums of fragment probabilities.

######  Theorem 6.2.

Assume $\nu<1$. Then

$\overline{L({\bm{d}})}=\left\\{\sum_{H\in\mathcal{U}}p_{H}\;\middle|\;\mathcal{U}\subseteq\textsc{Fr}\right\\}.$
(39)

###### Proof.

Let $S({\bm{d}})$ be the set of partial sums in the RHS of (39).

We first show that $\overline{L({\bm{d}})}\subseteq S({\bm{d}})$. It is a
known fact (see e.g. [16, 23]) that $S({\bm{d}})$ is closed and has no
isolated points. Thus, $\overline{S({\bm{d}})}=S({\bm{d}})$, and it suffices
to show $L({\bm{d}})\subseteq S({\bm{d}})$. Let
$\phi\in\operatorname{\textsc{FO}}$ be a sentence. For each $H\in\textsc{Fr}$,
define

$\displaystyle p_{n}(\phi,H)$
$\displaystyle=\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{ satisfies
}\phi,\,\mathrm{Frag}_{n}\simeq H)$
$\displaystyle=\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{ satisfies
}\phi\mid\mathrm{Frag}_{n}\simeq H)\,p_{n}(H).$

Define $p(\phi)=\lim_{n\to\infty}\sum_{H\in\textsc{Fr}}p_{n}(\phi,H)$. As
$p_{n}(\phi,H)\leq p_{n}(H)$, the sequence of real maps over Fr, $(H\mapsto
p_{n}(\phi,H))_{n\in\mathbb{N}}$ is tight, and the sum and limit in the
definition of $p(\phi)$ may be exchanged. By Theorem 6.1, we know that
$\lim_{n\to\infty}\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{ satisfies
}\phi\mid\mathrm{Frag}_{n}\simeq H)\in\\{0,1\\}$. Let
$\mathcal{U}=\mathcal{U}_{\phi}\subseteq\textsc{Fr}$ be the set of fragments
for which this limit is $1$. We conclude

$p(\phi)=\sum_{H\in\textsc{Fr}}\lim_{n\to\infty}p_{n}(\phi,H)=\sum_{H\in\mathcal{U}}p(H)\in
S({\bm{d}}).$

We now show that $\overline{L({\bm{d}})}\supseteq S({\bm{d}})$. Let
$\mathcal{U}\subseteq\textsc{Fr}$ be an arbitrary family of fragments. We give
a sequence of $\operatorname{\textsc{FO}}$ sentences $\phi_{k}(\mathcal{U})$
satisfying
$\lim_{k\to\infty}p(\phi_{k}(\mathcal{U}))=\sum_{H\in\mathcal{U}}p(H)$. For
each $H\in\textsc{Fr}$ and $k\in\mathbb{N}$, let
$\phi_{k}(H)\in\operatorname{\textsc{FO}}$ be the sentence stating that the
graph $G$ contains an isolated copy of $H$, and that no $k$-tuple of vertices
outside this copy induce a cycle. Suppose that $\mathcal{U}$ is infinite. Let
$(\mathcal{U}_{i})_{i\in\mathbb{N}}$ be a monotonically increasing chain of
finite sets $\mathcal{U}_{i}\subset\mathcal{U}$ satisfying
$\bigcup_{i\in\mathbb{N}}\mathcal{U}_{i}=\mathcal{U}$. Define
$\phi_{k}(\mathcal{U})=\bigvee_{H\in\mathcal{U}_{k}}\phi_{k}(H)$. The union of
disjoint events $\left(\bigvee_{H\in\mathcal{U}_{k}}\mathrm{Frag}_{n}\simeq
H\right)$ implies $\mathbb{G}_{n}({\bm{d}}_{n})\text{ satisfies
}\phi_{k}(\mathcal{U})$. Let $A_{n,k}$ be the event that
$\mathbb{G}_{n}({\bm{d}}_{n})$ contains a cycle of length larger than $k$.
Then, $(\mathbb{G}_{n}({\bm{d}}_{n})\text{ satisfies
}\phi_{k}(\mathcal{U}))\wedge(\neg A_{n,k})$ implies
$\left(\bigvee_{H\in\mathcal{U}_{k}}\mathrm{Frag}_{n}\simeq H\right)$ as well.
Thus,

$\displaystyle\lvert
p_{n}(\phi_{k}(\mathcal{U}))-\sum_{H\in\mathcal{U}_{k}}p_{n}(H)\rvert\leq\mathbb{P}(A_{n,k}).$
(40)

By Corollary 4.5 and Markov inequality,
$\lim_{k\to\infty}\lim_{n\to\infty}\mathbb{P}(A_{n,k})=0$.

Taking limits in both sides of (40), first with respect to $n\to\infty$ and
then to $k\to\infty$, we obtain,

$\lim_{k\to\infty}\left(p(\phi_{k}(\mathcal{U}))-\sum_{H\in\mathcal{U}_{k}}p(H)\right)=0.$

By the definition of infinite sum this proves that

$\sum_{H\in\mathcal{U}}p(H)=\lim_{k\to\infty}p(\phi_{k}(\mathcal{U}))\in\overline{L({\bm{d}})}.$

If $\mathcal{U}$ is finite, then the proof follows from a simpler argument, by
defining $\phi_{k}(\mathcal{U})=\bigvee_{H\in\mathcal{U}}\phi_{k}(H)$. ∎

The desired results about $\overline{L({\bm{d}})}$ follow from analysing the
set of fragment probabilities and using Kakeya’s Criterion (Lemma 2.5). A
technical difficulty that arises in the proof is that fragment probabilities
depend on many more features of ${\bm{d}}$ other than the parameter $\nu$. In
order to circumvent this issue, we use the following lemma.

######  Lemma 6.3.

Suppose that $\nu<1$. Define $Q=Q(\nu)=\sqrt{1-\nu}\cdot e^{\nu/2+\nu^{2}/4}$.
Let $\bm{a}=(a_{n})_{n\geq 3}$ be a sequence of natural numbers
$a_{n}\in\mathbb{N}$ with $\sum_{n\geq 3}a_{n}<\infty$. Consider

$\textsc{Fr}_{\bm{a}}=\\{H\in\textsc{Fr}\mid H\text{ contains exactly $a_{i}$
$i$-cycles for each $i\geq 3$}\\}.$

Then

$\sum_{H\in\textsc{Fr}_{\bm{a}}}p(H)=Q\prod_{i\geq
3}\frac{(\nu^{i}/2i)^{a_{i}}}{a_{i}!}.$ (41)

In particular, $p(H)$ is maximized when $H$ is the empty fragment.

###### Proof.

Let $B_{n}$ be the event that $\mathbb{G}_{n}({\bm{d}}_{n})$ contains exactly
$a_{i}$ $i$-cycles for each $i\geq 3$. By Lemma 4.6 it holds that

$\mathbb{P}(B_{n})=Q\prod_{i\geq 3}\frac{(\nu^{i}/2i)^{a_{i}}}{a_{i}!}+o(1).$

For each $H\in\textsc{Fr}$, let

$q_{n}(H)=\mathbb{P}(B_{n}\mid\mathrm{Frag}_{n}\simeq
H)\mathbb{P}(\mathrm{Frag}_{n}\simeq H).$

By the law of total probability
$\mathbb{P}(B_{n})=\sum_{H\in\textsc{Fr}}q_{n}(H)$. Moreover, observe that
$q_{n}(H)\leq p_{n}(H)$ for all $H\in\textsc{Fr}$, so the sequence of maps
$(H\mapsto q_{n}(H))_{n\in\mathbb{N}}$ is tight. This way

$\displaystyle\lim_{n\to\infty}\mathbb{P}(B_{n})=\sum_{H\in\textsc{Fr}}\lim_{n\to\infty}q_{n}(H).$
(42)

By Theorem 4.7, we know that w.h.p. all cycles in
$\mathbb{G}_{n}({\bm{d}}_{n})$ lie in $\mathrm{Frag}_{n}$.

This implies that $q_{n}(H)=p(H)+o(1)$ if $H\in\textsc{Fr}_{\bm{a}}$ and
$q_{n}(H)=o(1)$ otherwise. Using this in (42), we obtain (41).

It remains to show that $p(H)$ is maximized at the empty fragment. Let
$H\in\textsc{Fr}$ be non-empty, and let $\bm{a}=(a_{i})_{i\geq 3}$ be the
sequence where $a_{i}$ is the number of $i$-cycles in $H$ for each $i\geq 3$.
By Equation 41,

$p(H)\leq Q\prod_{i\geq 3}\frac{(\nu^{i}/2i)^{a_{i}}}{a_{i}!}.$

However, as $\nu<1$, the expression on the right is at most $Q$, which is the
probability of the empty fragment. This completes the proof. ∎

For the remainder of this subsection, we number the fragments in Fr as
$H_{1},H_{2},\dots$ in such a way that $p(H_{i})\geq p(H_{j})$ for all $i<j$.
For convenience we define $p_{i}=p(H_{i})$. For each $i>1$, let $k=k(i)$ be
the number satisfying

$\frac{Q\nu^{k}}{2k}\geq p_{i}>\frac{Q\nu^{k+1}}{2(k+1)},$ (43)

where $Q=Q(\nu)=\sqrt{1-\nu}\cdot e^{\nu/2+\nu^{2}/4}$ as in last lemma. We
impose the condition $i>1$, because $H_{1}$ corresponds to the empty fragment
and $p_{1}=Q$ by Lemma 4.6, so $k(1)$ is not well-defined. Observe that Lemma
6.3 implies $k(i)\geq 3$ for all $i>1$. Finally, the probabilities $p_{i}$ are
non-increasing by definition and have limit zero, so $k(i)$ is non-decreasing
and tends to infinity with $i\to\infty$.

######  Lemma 6.4.

Assume $\nu<1$. Then $\overline{L({\bm{d}})}$ is a finite union of intervals
in $[0,1]$.

###### Proof.

Let $i_{0}$ be the smallest index $i>1$ for which
$\sum_{j=3}^{k(i)-2}(1/j)\geq 4/\nu$, which exists as the harmonic series
diverges. We prove that $p_{i}\leq\sum_{j>i}p_{j}$ for any $i\geq i_{0}$. By
Kakeya’s Criterion, this implies the result. Let $i>i_{0}$, $k=k(i)$. For each
$3\leq\ell\leq\lfloor\frac{k+1}{2}\rfloor$, let $\textsc{Fr}_{\ell}$ be the
set of unlabeled fragments containing an $\ell$-cycle, a $(k-\ell+1)$-cycle,
and no other cycle. By Lemma 6.3, it holds that

$\sum_{H\in\textsc{Fr}_{\ell}}p(H)=\begin{cases}Q^{\prime}/2&\text{if $k$ is
odd and }\ell=\frac{k+1}{2},\\\ Q^{\prime}&\text{otherwise},\par\end{cases}$
(44)

where $Q^{\prime}=\frac{Q\nu^{k+1}}{4\ell(k-\ell+1)}$. For any $\ell$, this
sum is at most $\frac{Q\nu^{k+1}}{2(k+1)}$, which is at most $p_{i}$ by (43).
In particular, $p(H)<p_{i}$ for all $H\in\textsc{Fr}_{\ell}$ and

$\bigcup_{\ell=3}^{\lfloor\frac{k+1}{2}\rfloor}\textsc{Fr}_{\ell}\subset\\{H_{j}\mid
j>i\\}.$

By the choice of $i_{0}$ and $i\geq i_{0}$, and by (43), we obtained the
desired condition

$\displaystyle\sum_{j>i}p_{j}\geq$
$\displaystyle\sum_{\ell=3}^{\lfloor\frac{k+1}{2}\rfloor}\sum_{H\in\textsc{Fr}_{\ell}}p(H)$
$\displaystyle=\frac{Q\,\nu^{k+1}}{8}\sum_{\ell=3}^{k-2}\frac{1}{\ell(k-\ell+1)}$
$\displaystyle\geq\frac{Q\,\nu^{k+1}}{8k}\sum_{\ell=3}^{k-2}\frac{1}{\ell}$
$\displaystyle\geq\frac{Q\,\nu^{k}}{2k}\geq p_{i}.\qed$

##  7 Second part of Theorem 1.3: Phase transition at $\nu_{0}$

We recall that $\nu_{0}$ is defined as the unique root in $[0,1]$ of

$\sqrt{1-\nu}\cdot e^{\frac{\nu}{2}+\frac{\nu^{2}}{4}}=1/2.$ (45)

######  Lemma 7.1.

The following hold.

  1. (1)

if $0<\nu<\nu_{0}$, then $\overline{L({\bm{d}})}$ has at least one gap, and

  2. (2)

if $\nu\geq\nu_{0}$, then $\overline{L({\bm{d}})}=[0,1]$.

###### Proof.

The case $\nu\geq 1$ can be proven exactly as in [17, Section 3.1], using our
results about the distribution of small cycles in
$\mathbb{G}_{n}({\bm{d}}_{n})$ described in Section 4. We thus assume that
$\nu<1$.

As in the previous subsection, let $H_{1},H_{2},\dots$ be an enumeration of
the class of fragments Fr satisfying $p(H_{1})\geq p(H_{2})\geq\dots$, and let
$p_{i}=p(H_{i})$ for all $i\geq 1$. By Kakeya’s Criterion,
$\overline{L({\bm{d}})}=[0,1]$ if and only if

$p_{i}\leq\sum_{j>i}p_{j},$ (46)

for all $i\geq 1$.

We first show (1). Recall that $\nu_{0}$ is defined as the only solution to
$Q(\nu_{0})=1/2$, which lies in the interval $[0,1]$. As $Q(\nu)$ is
monotonically decreasing in $[0,1]$ (see (5)) and $0<\nu<\nu_{0}$, it holds
that $Q(\nu)>1/2$. Recall that $H_{1}$ corresponds to the empty fragment. By
Lemma 6.3,

$p_{1}=Q>1/2>1-Q=\sum_{j>1}p_{j}.$

and (46) does not hold for $i=1$, which implies that $\overline{L({\bm{d}})}$
contains at least one gap.

Now we proceed to show (2). In this case, $\nu_{0}\leq\nu<1$, and (46) holds
for $i=1$, because $Q\leq 1/2$. We show that (46) holds for $i>1$ as well. Fix
$i>1$ and let $k=k(i)$. For all $\ell\geq 3$, we define $\textsc{Fr}_{\ell}$
as the set of unlabeled fragments containing an $\ell$-cycle and no other
cycles. By Lemma 6.3,
$\sum_{H\in\textsc{Fr}_{\ell}}p_{H}=Q\nu^{\ell}/(2\ell)$. We have

$\sum_{j>i}p_{j}\geq\sum_{\ell>k}\sum_{H\in\textsc{Fr}_{\ell}}p_{H}=Q\sum_{\ell>k}\frac{\nu^{\ell}}{2\ell}\geq\frac{Q\nu^{k}}{2k}\sum_{m\geq
1}\left(\frac{\nu k}{k+1}\right)^{m},$ (47)

where the last inequality follows from the fact that if
$a_{\ell}=\nu^{\ell}/(2\ell)$, then $a_{\ell+1}\geq\frac{\nu
k}{k+1}\,a_{\ell}$ for all $\ell\geq k$. Since $k(i)\geq 3$ for all $i>1$,
then $\frac{k}{k+1}\geq 3/4$. Note that $\nu_{0}\geq 3/4$, so the LHS of (47)
can be bounded as

$\sum_{j>i}p_{j}\geq\frac{Q\nu^{k}}{2k}\sum_{m\geq
1}(3/4)^{2m}=\frac{9}{7}\cdot\frac{Q\nu^{k}}{2k}>\frac{Q\nu^{k}}{2k}\geq
p_{i},$

where we used (43) in the last step. The criterion implies that
$\overline{L({\bm{d}})}=[0,1]$.

∎

##  8 Remarks About the Convergence Law

In this section we discuss the convergence law studied by Lynch in [18,
lynchConvergenceLawRandom2003a]. His main result states that, under some
conditions on the asymptotic degree sequence ${\bm{d}}$, the limit of
$\mathbb{P}(\mathbb{G}_{n}({\bm{d}}_{n})\text{ satisfies }\phi)$ exists for
any $\operatorname{\textsc{FO}}$ sentence $\phi$. We note that Lynch’s
requirements on ${\bm{d}}$ are non-comparable with 1.1.

######  Definition 8.1.

We call an asymptotic degree sequence ${\bm{d}}$ smooth if it satisfies
conditions (i), (ii) and (iv) from 1.1, as well as the following weakening of
(iii):

$\lim_{n\to\infty}\mathbb{E}\left[D_{n}\right]\text{ exists, is bounded and
equals }\mathbb{E}\left[D\right].$

Both papers [18, lynchConvergenceLawRandom2003a] deal with smooth degree
sequences. However, there is no condition on the convergence of
$\mathbb{E}\left[D_{n}^{2}\right]$ to a finite quantity. Instead, this is
replaced by a bound on the maximum degree: the existence of a cutoff function
$\omega(n)$ satisfying $\Delta(n)\leq\omega(n)$. In
[lynchConvergenceLawRandom2003a], $\omega(n)=n^{\alpha}$, where $\alpha<1/4$,
while in [18], $\omega(n)$ was sub-polynomial (that is,
$\omega(n)=o(n^{\alpha})$ for all $\alpha>0$). Observe that neither cutoff is
enough to guarantee that $\mathbb{E}\left[D_{n}^{2}\right]$ converges to a
finite quantity (in fact, no diverging cutoff function is enough). This is
relevant because of next result.

######  Lemma 8.2.

Let ${\bm{d}}={\bm{d}}_{n}$ be a smooth asymptotic degree sequence with
$\mathbb{E}\left[D^{2}_{n}\right]\to\infty$ as $n\to\infty$. Then
$\mathbb{CM}_{n}({\bm{d}}_{n})$ a.a.s. contains a loop.

###### Sketch of the proof.

Let $X_{n}$ count the number of loops in $\mathbb{CM}_{n}({\bm{d}}_{n})$. Then

$\mathbb{E}\left[X_{n}\right]=\frac{1}{2}\sum_{v\in[n]}\frac{d_{v}(d_{v}-1)}{2m_{n}-1}=\frac{1}{2}\cdot\frac{\rho_{n,2}}{\rho_{n,1}-1/n}.$

Using that $\rho_{n,2}$ diverges and ${\bm{d}}$ is smooth we get that
$\mathbb{E}\left[X_{n}\right]\to\infty$. The result follows from proving that
$\mathrm{Var}\left(X_{n}\right)=o(\mathbb{E}\left[X_{n}^{2}\right])$ and using
the second moment method. ∎

The approach followed in [18, lynchConvergenceLawRandom2003a] consists of
proving a FO convergence law for the multigraph
$\mathbb{CM}_{n}({\bm{d}}_{n})$, and transferring this result to
$\mathbb{G}_{n}({\bm{d}}_{n})$ afterwards by conditioning
$\mathbb{CM}_{n}({\bm{d}}_{n})$ to the event of being simple. In order to make
this work, it was taken for granted that the probability that
$\mathbb{CM}_{n}({\bm{d}}_{n})$ is simple was bounded away from zero. However,
because of last lemma, this is not true unless the second moment
$\mathbb{E}\left[D^{2}_{n}\right]$ is bounded.

However, we claim that a $\mathbb{G}({\bm{d}})$ satisfies a FO convergence law
whenever ${\bm{d}}$ follows 1.1. Our aim is not to give a full proof of this
statement, but we sketch it in the rest of the section.

In [19] Lynch showed that the binomial graph $\mathbb{G}_{n}(p_{n})$ satisfies
a FO convergence law when $p_{n}\sim c/n$ for any real constant $c>0$.
Informally, this follows from three facts about $\mathbb{G}_{n}(c/n)$. The
$r$-core $\operatorname{\mathrm{Core}}_{r}(G)$ of a graph $G$ is the graph
induced by the $r$-neighborhood of all its cycles of size at most $2r+1$, and
define $\operatorname{\mathrm{Core}}_{n,r}$ as the $r$-core of
$\mathbb{G}_{n}(c/n)$. Then for any fixed $r>0$ the following hold:

  1. (I)

w.h.p. any rooted tree of height at most $r$ appears as the $r$-neighbourhood
of some vertex in $\mathbb{G}_{n}(c/n)$ more than $K$ times, for any fixed
integer $K>0$,

  2. (II)

w.h.p. $\operatorname{\mathrm{Core}}_{n,k}$ is a disjoint union of unicyclic
graphs (i.e., a fragment),

  3. (III)

and $\operatorname{\mathrm{Core}}_{n,r}$ has a well-defined asymptotic
distribution.

We claim that the same three facts hold true in the multigraph
$\mathbb{CM}_{n}({\bm{d}}_{n})$, with small changes. Let
$\operatorname{\mathrm{Core}}_{n,r}^{*}$ denote the $r$-core of
$\mathbb{CM}_{n}({\bm{d}}_{n})$.

For Fact (I) we consider only rooted trees without forbidden degrees according
to ${\bm{d}}$: those that do not have vertices of degree $k$, where $k$
satisfies the condition (iv) of 1.1. To see that this holds it is enough to
observe that the $r$-neighbourhood of an arbitrary tuple of vertices in
$\mathbb{CM}_{n}({\bm{d}}_{n})$ converges in distribution to a branching
process with as many roots as vertices in the tuple, whose root offspring
distribution is $D$ and general offspring distribution is $\widehat{D}$.
Alternatively, one can use the second moment to show that there are many
copies of any valid tree; this is precisely the part of the proof that
requires condition (iv).

Fact (II) follows from a simple first-moment argument: a multigraph consisting
of two small cycles that intersect has positive excess. The same holds true
for two cycles joined by a short path. The proof is as Theorem 4.7 but
simpler: as we bound the size of the cycles and the paths, then there is only
a finite number of forbidden configurations to be considered.

Fact (III) is the more convoluted one, we sketch the argument in what follows.
The small-cycle distribution of $\mathbb{CM}_{n}({\bm{d}}_{n})$ converges to a
vector of independent Poisson random variables, as shown in Lemma 4.3.
Consider an arbitrary disjoint union of cycles $H$, each of size at most
$2r+1$. Let $A_{H}=A_{n,H}$ be the event that the union of cycles of size at
most $2r+1$ in $\mathbb{CM}_{n}({\bm{d}}_{n})$ is isomorphic to $H$, and let
$\mathbb{CM}_{n}^{H}({\bm{d}})$ denote $\mathbb{CM}_{n}({\bm{d}}_{n})$
conditioned on that event. Now, let $v_{1},\dots,v_{\ell}$ be the fixed
vertices lying on the $H$-copy of $\mathbb{CM}^{H}_{n}({\bm{d}})$. Delete the
edges of $H$ and denote by $F$ the $r$-neighbourhood of $v_{1},\dots,v_{\ell}$
in the resulting multigraph. Then $F$ converges in distribution to the first
$r$-generations of a multi-rooted branching process with $\ell$ roots,
offspring distribution $\hat{D}$ and root offspring distribution $\tilde{D}$
given by

$\mathbb{P}(\tilde{D}=i-2)=\frac{i(i-1)\mathbb{P}(D=i)}{\rho_{2}}.$

Indeed, for each vertex in $H$, which correspond to the roots of $F$, we
delete two edges. This shows that $\operatorname{\mathrm{Core}}_{n,r}^{*}$
converges in distribution to a random fragment where the cycle counts are
given by appropriate Poisson distributions, and the trees that grow out of the
cycles follow the distribution given by the branching process described above,
proving (III). Compare this with the interpretation of the limit distribution
of the fragment obtained in Theorem 5.7, and observe the similarities. A
random fragment $H$ following that distribution is constructed as follows:
First generate the set of cycles of $H$, letting the number of $k$-cycles in
$H$ follow a Poisson random variable with parameter $\nu^{k}/2k$,
independently for each $k\geq 1$. Afterwards, attach to each vertex lying on a
cycle an independent copy of the branching process with offspring distribution
$\hat{D}$ and root offspring distribution $\tilde{D}$. In the setting of
Theorem 5.7, the generated fragment was guaranteed to be finite because
$\nu<1$. Here we do not have this assumption, but instead we bound the maximum
size of the generated cycles to $2r+1$, and only consider the first $r$
generations of each branching process.

Facts (I), (II), and (III) for $\mathbb{CM}({\bm{d}})$ show a
$\operatorname{\textsc{FO}}$-convergence law in the configuration model in the
same fashion as shown in [19]. Let $\varphi$ be a
$\operatorname{\textsc{FO}}$-sentence, let $k$ be its quantifier rank and let
$r=(3^{k}-1)/2$. Let $\Omega_{r}$ be the set of unlabeled fragments consisting
of cycles of size at most $2r+1$ with trees of height at most $r$ attached to
them. Using pebble games and Fact (I) one can show that

$\lim_{n\to\infty}\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{ satisfies
}\varphi\,\mid\,\operatorname{\mathrm{Core}}_{n,r}^{*}\simeq H)\in\\{0,1\\},$
(48)

for any $H\in\Omega_{r}$. Facts (II) and (III) show that
$\operatorname{\mathrm{Core}}_{n,r}^{*}$ converges in distribution to a random
graph from $\Omega_{r}$. Hence,

$\displaystyle\lim_{n\to\infty}$
$\displaystyle\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{ satisfies
}\varphi)=$
$\displaystyle\sum_{H\in\Omega_{r}}\lim_{n\to\infty}\mathbb{P}(\mathbb{CM}_{n}({\bm{d}}_{n})\text{
satisfies }\varphi\,\mid\,\operatorname{\mathrm{Core}}_{n,r}^{*}\simeq
H)\cdot\mathbb{P}(\operatorname{\mathrm{Core}}_{n,r}^{*}\simeq H).$

In the last sum, each of the first factors converge to either zero or one by
(48), and the right factors converge to a fixed probability by (III). This
shows that the probability $\mathbb{CM}_{n}({\bm{d}}_{n})$ satisfies $\varphi$
converges, as desired.

## References

  * [1] E.. Bender and E.. Canfield  “The Asymptotic Number of Labeled Graphs with given Degree Sequences”  In _Journal of Combinatorial Theory, Series A_ 24.3, 1978  DOI: 10.1016/0097-3165(78)90059-6
  * [2] B. Bollobás  “A probabilistic proof of an asymptotic formula for the number of labelled regular graphs”  In _European Journal of Combinatorics_ 1.4 Elsevier, 1980, pp. 311–316
  * [3] B. Bollobás  “Random Graphs”, Cambridge Studies in Advanced Mathematics  Cambridge: Cambridge University Press, 2001  DOI: 10.1017/CBO9780511814068
  * [4] B. Bollobás and B.D. McKay  “The number of matchings in random regular graphs and bipartite graphs”  In _Journal of Combinatorial Theory, Series B_ 41.1 Elsevier, 1986, pp. 80–91
  * [5] C. Bordenave  “Lecture notes on random graphs and probabilistic combinatorial optimization.”, https://www.math.univ-toulouse.fr/ bordenave/coursRG.pdf, 2016
  * [6] S. Dhara, D. Mukherjee and S. Sen  “Phase transitions of extremal cuts for the configuration model”  In _Electron. J. Probab_ 22.86, 2017, pp. 1–29
  * [7] P. Erdős and A. Rényi  “On the evolution of random graphs”  In _Publ. math. inst. hung. acad. sci_ 5.1, 1960, pp. 17–60
  * [8] R. Fagin  “Probabilities on Finite Models”  In _The Journal of Symbolic Logic_ 41.1 Association for Symbolic Logic, 1976  DOI: 10.2307/2272945
  * [9] Y.. Glebskii, D.. Kogan, M.. Liogon’kii and V.. Talanov  “Range and Degree of Realizability of Formulas in the Restricted Predicate Calculus”  In _Cybernetics_ 5.2, 1969  DOI: 10.1007/BF01071084
  * [10] H. Hatami and M. Molloy  “The scaling window for a random graph with a given degree sequence”  In _Random Structures & Algorithms_ 41.1 Wiley Online Library, 2012, pp. 99–123
  * [11] P. Heinig, T. Müller, M. Noy and A. Taraz  “Logical Limit Laws for Minor-Closed Classes of Graphs”  In _Journal of Combinatorial Theory, Series B_ 130, 2018  DOI: 10.1016/j.jctb.2017.12.002
  * [12] R. van der Hofstad  “Random Graphs and Complex Networks”, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, 2016  DOI: 10.1017/9781316779422
  * [13] R. van der Hofstad  “Random Graphs and Complex Networks: Volume 2”, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, 2024  URL: https://books.google.es/books?id=p7sn0AEACAAJ
  * [14] S. Janson  “The Probability That a Random Multigraph Is Simple”  In _Combinatorics, Probability and Computing_ 18.1-2 Cambridge University Press, 2009, pp. 205–225  DOI: 10/bg4m2c
  * [15] S. Janson and M.. Luczak  “A new approach to the giant component problem”  In _Random Structures & Algorithms_ 34, 2009, pp. 197–216
  * [16] S. Kakeya  “On the Partial Sums of an Infinite Series”  In _Tohoku Sci. Rep_ 3.4, 1914
  * [17] A. Larrauri, T. Müller and M. Noy  “Limiting Probabilities of First Order Properties of Random Sparse Graphs and Hypergraphs”  In _Random Structures & Algorithms_ 60.3, 2022  DOI: 10.1002/rsa.21041
  * [18] J.. Lynch  “Convergence Law for Random Graphs With Specified Degree Sequence”  In _ACM Transactions on Computational Logic_ 6.4, 2005
  * [19] J.. Lynch  “Probabilities of Sentences about Very Sparse Random Graphs”  In _Random Structures & Algorithms_ 3.1, 1992  DOI: 10.1002/rsa.3240030105
  * [20] J.F. Lynch  “Convergence Law for Random Graphs with Specified Degree Sequence”  In _18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings._ , 2003  DOI: 10.1109/LICS.2003.1210070
  * [21] B.. McKay  “Subgraphs of dense random graphs with specified degrees”  In _Combinatorics, Probability and Computing_ 20.3 Cambridge University Press, 2011, pp. 413–433
  * [22] M. Molloy and B. Reed  “A Critical Point for Random Graphs with a given Degree Sequence”  In _Random Structures & Algorithms_ 6.2-3, 1995  DOI: 10.1002/rsa.3240060204
  * [23] J. Nymann and R. Sáenz  “On a Paper of Guthrie and Nymann on Subsums of Infinite Series”  In _Colloquium Mathematicae_ 83.1, 2000
  * [24] N. Wormald  “The asymptotic distribution of short cycles in random regular graphs”  In _Journal of Combinatorial Theory, Series B_ 31.2 Elsevier, 1981, pp. 168–182

lynchConvergenceLawRandom2003alynchConvergenceLawRandom2003

##  Appendix A Proof of auxiliary lemmas

######  Lemma A.1.

Let
$\alpha_{1},\alpha_{2},\dots,\alpha_{k},\beta_{1},\beta_{2},\dots,\beta_{k}$
be positive integers satisfying $\alpha_{i}\geq\beta_{i}$ for all $i\in[k]$.
Define $\alpha=\sum_{i\in[k]}\alpha_{i}$, and $\beta=\sum_{i\in[k]}\beta_{i}$.
Then

$\prod_{i\in[k]}\prod_{0\leq
j<\beta_{i}}(\alpha_{i}-j)\leq\frac{(\alpha)_{\beta}}{\alpha^{\beta}}\Big{(}\prod_{\beta-k+1\leq
j<\beta}\frac{\alpha}{\alpha-j}\Big{)}\prod_{i\in[k]}\alpha_{i}^{\beta_{i}}.$
(49)

###### Proof.

The proof is by induction on $\beta$ for each $k$ and
$\alpha_{1},\dots,\alpha_{k}$ fixed. For $\beta=k$ the result is trivial.
Suppose now that $\beta>k$. Then, for some $t\in[k]$ it must be that
$\beta_{t}-1\geq(\beta-k)\alpha_{t}/\alpha$. This is because

$\sum_{i\in[k]}\beta_{i}-1=\beta-k=\sum_{i\in[k]}(\beta-k)\alpha_{i}/\alpha.$

In particular, this means that

$\frac{\alpha_{t}}{\alpha_{t}-\beta_{t}+1}\geq\frac{\alpha}{\alpha-\beta+k}.$
(50)

Observe that our assumption $\beta>k$ implies $\beta_{t}>1$. Additionally, by
the induction hypothesis

$\prod_{i\in[k]}\prod_{0\leq
j<\beta^{\prime}_{i}}\frac{\alpha_{i}}{\alpha_{i}-j}\geq\prod_{0\leq
j<\beta^{\prime}-k+1}\frac{\alpha}{\alpha-j},$

where $\beta^{\prime}_{i}=\beta_{i}$ for $i\neq t$,
$\beta^{\prime}_{t}=\beta_{t}-1$, and $\beta^{\prime}=\beta-1$. Multiplying by
(50) yields

$\prod_{i\in[k]}\prod_{0\leq
j<\beta_{i}}\frac{\alpha_{i}}{\alpha_{i}-j}\geq\prod_{0\leq
j<\beta-k+1}\frac{\alpha}{\alpha-j}.$ (51)

Rearranging we obtain

$\prod_{i\in[k]}\prod_{0\leq j<\beta_{i}}(\alpha_{i}-j)\leq\prod_{0\leq
j<\beta-k+1}\frac{\alpha-j}{\alpha}\prod_{i\in[k]}\alpha_{i}^{\beta_{i}}.$
(52)

Multiplying and dividing by $(\alpha)_{\beta}$ on the right hand side of the
previous equation yields the desired result. ∎

######  Lemma A.2.

Let $\Delta=\Delta_{N}$ be a function on $N$ satisfying
$\Delta_{N}=o(\sqrt{N})$. There is a sequence $\xi_{N}$ tending to $0$ as
$N\to\infty$ such that:

  * (i)

for all $0\leq a<\Delta$,

$\frac{N^{a}(N-a)!}{N!}\leq e^{a\xi_{N}}.$

  * (ii)

for all $\Delta\leq a<N$,

$\frac{N^{\Delta}(N-a)!}{(N+\Delta-a)!}\leq e^{a\xi_{N}}.$

###### Proof.

We begin with the proof of (ii), so suppose that $\Delta\leq a<N$. By
Stirling’s approximation, we know that for all $k>0$

$\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}e^{\frac{1}{12k+1}}\leq
k!\leq\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}e^{\frac{1}{12k}}.$

Hence

$\frac{N^{\Delta}(N-a)!}{(N+\Delta-a)!}\leq CD,$

where

$\displaystyle C$ $\displaystyle=$
$\displaystyle\left(1+\frac{a-\Delta}{N+\Delta-a}\right)^{\Delta}\left(1-\frac{\Delta}{N+\Delta-a}\right)^{N-a}e^{\Delta},$
(53) $\displaystyle D$ $\displaystyle=$
$\displaystyle\sqrt{\frac{N-a}{N+\Delta-a}}e^{\frac{1}{12(N-a)}-\frac{1}{12(N-a+\Delta)+1}}.$
(54)

Clearly $D\leq e^{1/12}$ for all $\Delta\leq a<N$, so $\ln(D)/a$ tends to zero
uniformly with $N$. Now we need to prove the same for $\ln(C)/a$. We consider
two cases. First, suppose that $N-a\leq N^{2/3}$. Since $\Delta=o(\sqrt{N})$,
we have for $N$ large enough

$C\leq e^{\Delta}(N/\Delta)^{\Delta}\leq e^{N^{2/3}}$

Since $N\sim a$, we have that $\ln(C)/a$ tends to zero.

Otherwise, suppose that $N-a\geq N^{2/3}$. Using the inequality $1+x\leq
e^{x}$ for all $x\in\mathbb{R}$, we get that

$C\leq\exp\left[\Delta\frac{(a-\Delta)-(N+a)+(N-a+\Delta)}{N-a+\Delta}\right]=\exp\left[\frac{\Delta
a}{N-a+\Delta}\right].$

Thus, all $\Delta\leq a\leq\Delta\sqrt{N}$,

$\frac{\ln(C)}{a}=\frac{\Delta}{N-a+\Delta}\leq\frac{\Delta}{N^{2/3}},$

which tends to zero because $\Delta=o(\sqrt{N})$.

Now let us show (i), so suppose that $0\leq a<\Delta$. It holds that

$\frac{N^{a}(N-a)!}{N!}\leq\left(\frac{N}{N-a}\right)^{a}\leq
e^{a^{2}/(N-a)}\leq e^{a\frac{\Delta}{N-\Delta}},$

where we have used that $a<\Delta<N$ in the last inequality. The function
$\frac{\Delta}{N-\Delta}$ tends to zero with $N$ and depends only on $N$ and
$\Delta$, as we wanted.

∎