# Subgraph densities and scaling limits of random graphs with a prescribed
modular decomposition

Théo Lenoir

###### Abstract.

We consider large uniform labeled random graphs in different classes with
prescribed decorations in their modular decomposition. Our main result is the
estimation of the number of copies of every graph as an induced subgraph. As a
consequence, we obtain the convergence of a uniform random graph in such
classes to a Brownian limit object in the space of graphons.

Our proofs rely on combinatorial arguments, computing generating series using
the symbolic method and deriving asymptotics using singularity analysis.

##  1\. Introduction

###  1.1. Motivation

This article lays at the interface of graph theory and combinatorial
probability.

The first motivation comes from modular decomposition, which is a standard
tool in graph theory. This notion will be reviewed in a comprehensive way in
Section 2. Roughly speaking, it is a decomposition of a graph into disjoint
subsets of vertices called _modules_. The modules can be thought of as
generalizations of connected components. Since a module can contain a proper
module, the modular decomposition is a recursive decomposition of a graph. It
is analogous to prime factor decomposition of integers: graphs without trivial
modules cannot be decomposed, and thus will be called prime for the modular
decomposition.

From an algorithmic perspective, the modular decomposition can be computed in
linear time [9], making it an essential tool for quickly solving various
problems such as determining belonging to several graph classes (_e.g._
cographs, $P_{4}$-sparse graphs, permutations graphs, etc). We refer the
readers to [8] and [13] for more details.

The study of modular decomposition from a probabilistic point of view started
very recently. The case with no prime graphs, _i.e._ cographs, has been
studied simultaneously in [5] and [20]. In a somewhat different context, the
author [16] used modular decomposition to study the case of graphs with few
$P_{4}$’s (for $k\geq 2$, $P_{k}$ denotes the graph consisting of a line with
$k$ vertices). The aim of this article is to generalize these results: we will
study the structure of large typical random graphs defined by a set of prime
graphs allowed in its modular decomposition.

The second motivation is the study of classes of graphs with forbidden induced
subgraphs. Indeed, our results can be interpreted in terms of forbidden
induced subgraphs, as the interdiction of some prime induced subgraphs is
heavily connected to the modular decomposition. Examples of classes covered by
our results include those with a finite number of prime induced subgraphs
allowed, or classes where all prime induced subgraphs are lines.

The asymptotic study of random graphs has been a well-established subject of
research for several decades. Depending on the graph models and graph
parameters of interest, several notions of limit can be considered.

  * •

A first point of view consists in studying the local limit of the graph around
a typical vertex. This gives information on local neighborhoods (_e.g._
degrees). See [15] for more details.

  * •

Alternatively, we can adopt a global viewpoint, in at least two very different
frameworks.

    * –

We may consider the scaling limit of graphs viewed as metric spaces, by
assigning distances to edges. This gives estimates of typical distances or
diameters. In this context, a universal object arises: the Continuum Random
Tree (CRT). For examples, refer to [2, 1, 19].

    * –

Instead, we may consider occurrences of induced subgraphs, the proper
framework for which is graphons. Introduced in [7], graphon convergence can be
seen as convergence of renormalized adjacency matrices for the so-called cut
metric (a good reference on graphon theory is [17]). This sometimes also gives
estimation on typical degrees [5], on extremal statistics (cliques and
independent sets as in [4]), or on the growth rate of classes of graphs [14].

The last two frameworks answer very different questions and are adapted
respectively to sparse graphs (graphs with a linear number of edges) and dense
graphs (graphs with a quadratic number of edges).

###  1.2. Main results

For a set of prime graphs $\mathcal{P}$, let $\mathcal{G}_{\mathcal{P}}$ be
the set of graphs $G$ such that every prime subgraph in the modular
decomposition of $G$ is in $\mathcal{P}$: the aim of this article is to study
the structure of a uniform graph of size $n$ in $\mathcal{G}_{\mathcal{P}}$
when $n$ tends towards $+\infty$. We only consider the case where
$\mathcal{P}$ is stable by automorphism. Let
$P(z)=\sum\limits_{H\in\mathcal{P}}\frac{z^{|H|}}{|H|!}$ be the exponential
generating function associated to a given set $\mathcal{P}$ and let
$R_{0}\in[0,+\infty]$ be the radius of convergence of $P$. Set
$\Lambda(w):=P(\exp(w)-1)+\exp(w)-1-w$, $\Lambda$ is a power series with
nonnegative coefficients. An important condition which will be crucial on
$\Lambda$ is the following:

######  Condition (C).

$R_{0}>0$ and $\Lambda^{\prime}\left(\log(1+R_{0})\right)>1$

(By convention, we set $\Lambda^{\prime}\left(\log(1+R_{0})\right)=+\infty$ if
the series $\Lambda^{\prime}$ diverges at $\log(1+R_{0})$.) This condition
implies that the number of graphs of size $n$ in $\mathcal{P}$ does not grow
too fast, see Section 1.3 for more details.

Let $\mathbf{G}^{(n)}$ be a graph of size $n$ taken uniformly at random in
$\mathcal{G}_{\mathcal{P}}$. For any graph $H$, denote by
$\mathrm{Occ}_{H}(\mathbf{G}^{(n)})$ the number of labeled induced subgraphs
of $\mathbf{G}^{(n)}$ isomorphic to $H$. Our first contribution is the
estimation of the expected number of copies of $H$ in $\mathbf{G}^{(n)}$,
_i.e._ $\mathbb{E}[\mathrm{Occ}_{H}(\mathbf{G}^{(n)})]$.

######  Theorem 1.1.

Let $\mathcal{P}$ be a set of prime graphs stable by automorphism such that
Condition (C) holds. Let $\mathbf{G}^{(n)}$ be a graph of size $n$ taken
uniformly at random in $\mathcal{G}_{\mathcal{P}}$.

Then for every graph $H$ there exists $K_{H}\geq 0$ such that:

$\mathbb{E}[\mathrm{Occ}_{H}(\mathbf{G}^{(n)})]\sim K_{H}n^{|H|-\beta(H)}$

where the constant $K_{H}$ is given in 6.2 and $\beta(H)$ is defined in Eq. 1.

Let us briefly comment on the theorem.

  * •

The quantity $\beta(H)$ is nonnegative, does not depend on $\mathcal{P}$, and
is equal to $0$ if and only if $H$ is a cograph. Thus at fixed size, the
graphs $H$ that appear the most as induced subgraphs of $\mathbf{G}^{(n)}$ are
the cographs. Informally, the quantity $\beta(H)$ can be thought of how far
$H$ is from cographs.

  * •

We have that $K_{H}>0$ if and only if each prime subgraph in the modular
decomposition of $H$ is an induced subgraph of an element of $\mathcal{P}$.
This criterion will follow from the expression of $K_{H}$ given in 6.2.

  * •

Applying 1.1 with the graph $H$ consisting of a single edge, we get that
$\mathbb{E}[\\#\text{edges}\ \text{of}\ \mathbf{G}^{(n)}]=\Theta(n^{2})$: thus
$\mathbf{G}^{(n)}$ is in the dense regime.

1.1 has an important consequence in terms of scaling limit: since we are in
the dense regime, we use the framework of graphons. Graphon convergence is
equivalent to the joint convergence of subgraphs density. More formally,
Diaconis and Janson provided in [10] a criterion for the convergence of random
graphs in the sense of graphons: the convergence of a family
$(\mathbf{H}^{(n)})_{n\geq 1}$ of random graphs is characterized by the
convergence in distribution of
$\frac{\mathrm{Occ}_{H}(\mathbf{H}^{(n)})}{n^{|H|}}$ for every finite graph
$H$. Therefore 1.1 ensures that $\mathbf{G}^{(n)}$ has a limit in the sense of
graphons. All the needed materials for the convergence of graphons will be
presented in Section 3.

For the case of cographs (_i.e._ $\mathcal{P}=\varnothing$), studied
simultaneously in [5] and [20], the authors exhibit a Brownian limit object
for a uniform cograph, called the Brownian cographon, which can be explicitly
constructed from the Brownian excursion.

Our second contribution is that, for all sets $\mathcal{P}$ satisfying
Condition (C), the scaling limit is a one parameter deformation of the
Brownian cographon. This answers partially a question in [5].

######  Theorem 1.2.

Let $\mathbf{G}^{(n)}$ be a graph of size $n$ taken uniformly at random in
$\mathcal{G}_{\mathcal{P}}$. Under Condition (C), $\mathbf{G}^{(n)}$ converges
in distribution towards $\mathbf{W}^{p}$ in the sense of graphons, where
$\mathbf{W}^{p}$ is the Brownian cographon of parameter $p$, and $p$ is a
parameter in $[0,1]$ depending on $\mathcal{P}$ whose expression is given in
Eq. 23.

This theorem shows $\mathbf{W}^{p}$ for various $p\neq 1/2$ as a scaling limit
of natural combinatorial objects.

###  1.3. Discussion on Condition (C)

First observe that Condition (C) is verified in many situations, for example
when:

  * •

$\mathcal{P}$ is finite, _i.e._ $P$ is a polynomial;

  * •

$P$ has a radius of convergence greater than $1$;

  * •

$P^{\prime}$ diverges in $R_{0}$;

  * •

the number of graphs in $\mathcal{P}_{n}$ grows as $Bn!R^{n}n^{a}$ with
$B,R>0$ and $a\geq-2$;

  * •

$P$ is rational.

As we will see in 4.12, Condition (C) implies that the graphs in
$\mathcal{G}_{\mathcal{P}}$ all share the universal exponent $-3/2$ in the
sense that the number of graphs of size $n$ in $\mathcal{G}_{\mathcal{P}}$ is
asymptotically equivalent to

$D\frac{n!}{R^{n}n^{3/2}},$

with $D>0$ and $R>0$ explicit constants depending on $\mathcal{P}$, as proved
in 4.12. All the details on the exponential generating functions and
asymptotics will be given in Section 4.

Let us illustrate the connection between 1.2 and our initial motivation for
graphs with forbidden induced subgraphs.

  * •

The case where all but finitely many prime induced subgraphs are forbidden
corresponds to a family of graphs $\mathcal{G}_{\mathcal{P}}$ where
$\mathcal{P}$ is finite thus Condition (C) is clearly verified.

  * •

The case where all prime subgraphs except lines are forbidden corresponds to
the family of graphs $\mathcal{G}_{\mathcal{P}}$ where $\mathcal{P}$ is the
set of lines of size at least $4$. Thus $P=\frac{z^{4}}{2(1-z)}$ and Condition
(C) is verified. The parameter $p$ of 1.2 is approximately $0.288$.

This work can be seen as the counterpart for graphs to the study of limits of
substitution-closed permutations in [6]. However multiple additional
difficulties (graph automorphisms, encoding of graphs in
$\mathcal{G}_{\mathcal{P}}$ by _non_ -plane trees through the modular
decomposition) arise, making the enumeration of $\mathcal{G}_{\mathcal{P}}$
more involved.

Condition (C) is necessary in 1.2 in the sense that if it is not verified,
other behaviors can appear: under other general assumptions on the generating
series, we can get a very different scaling limit where each induced subgraph
may appear in the limiting object. In particular, $\mathbb{G}_{n}$ does not
converge to the Brownian cographon.

###  1.4. Proof strategy

Proofs are essentially combinatorial: we use the tree encoding of the modular
decomposition to obtain exact enumerations for a large family of graph
classes. We exploit those enumerative results with tools from analytic
combinatorics to get asymptotic estimates like the ones of the number of
graphs of size $n$ in each class.

The most challenging part of the proofs is the one of 5.8, giving the
combinatorial decomposition of graphs in $\mathcal{G}_{\mathcal{P}}$ with a
given induced subgraph. This theorem is the key theorem to get the needed
asymptotic estimates.

###  1.5. Outline of the paper

  * •

In Section 2 we define the encoding of graphs with trees, the modular
decomposition, which is used throughout the different proofs.

  * •

Section 3 presents the necessary material on graphons.

  * •

Sections 4 and 5 are about calculating generating series related to our graph
classes: in Section 4 we compute several generating series, and obtain the
asymptotic of the number of graphs of size $n$ under Condition (C) and Section
5 deals with the generating series of graphs with a given induced subgraph.

  * •

Section 6 concludes the proofs of 1.2 and 1.1.

##  2\. Background on modular decomposition

This section is composed of classical results around modular decomposition. In
the last subsection, we prove an enumerative result that will be useful at the
end of the paper.

###  2.1. Labeled graphs

In the following all the graphs considered are simple and finite. Each time a
graph $G$ is defined, we denote by $V$ its set of vertices and $E$ its set of
edges. Whenever there is an ambiguity, we denote by $V_{G}$ (resp. $E_{G}$)
the set of vertices (resp. edges) of $G$.

######  Definition 2.1.

We say that $G=(V,E)$ is a _weakly-labeled graph_ if every element of $V$ has
a distinct label in $\mathbb{N}$ and that $G=(V,E)$ is a _labeled graph_ if
every element of $V$ has a distinct label in $\\{1,\dots,|V|\\}$.

The _size of a graph_ $G$, denoted by $|G|$, is its number of vertices.

The _minimum of a graph_ $G$, denoted $\mathrm{min}(G)$, is the minimal label
of its vertices.

In the following, every graph is labeled, otherwise we mention explicitly that
the graph is weakly-labeled.

######  Remark.

We do not identify a vertex with its label. A vertex of label $i$ is denoted
$v_{i}$. The label of a vertex $v$ is denoted $\ell(v)$.

######  Definition 2.2.

For any weakly-labeled object (graph or tree) of size $n$, we call _reduction_
the operation that reduces its labels to the set $\\{1,\dots,n\\}$ while
preserving the relative order of the labels.

For example if $G$ labels $2,4,12,63$ then the reduced version of $G$ is a
copy of $G$ in which $2,4,12,63$ are respectively replaced by $1,2,3,4$.

######  Definition 2.3.

Let $G$ be a graph and $\pi$ be a permutation of $\\{1,\dots,|G|\\}$. The
_$\pi$ -relabeling_ of $G$ is the graph $G^{\prime}$ such that:

  * •

$V_{G^{\prime}}=V_{G}$

  * •

for every vertex $v$ in $V_{G^{\prime}}$, we replace the label of the leaf $v$
by $\pi(\ell(v))$.

We write $G\sim G^{\prime}$ if $|G|=|G^{\prime}|$ and there exists a
permutation $\pi$ of $\\{1,\dots,|G|\\}$ such that $G$ is isomorphic to the
$\pi$-relabeling of $G^{\prime}$.

Note that $\sim$ is an equivalence relation.

######  Definition 2.4 (Induced subgraph).

Let $G$ be a graph, $k$ a positive integer and $\mathfrak{I}$ a partial
injection from the set of labels of $G$ to $\mathbb{N}$. The _labeled subgraph
$G_{\mathfrak{I}}$_ of $G$ induced by $\mathfrak{I}$ is defined as:

  * •

The vertices of $G_{\mathfrak{I}}$ are the vertices of $G$ whose label $\ell$
is in the domain of $\mathfrak{I}$. For every such vertex, we replace the
label $\ell$ of the vertex by $\mathfrak{I}(\ell)$;

  * •

For two vertices $v$ and $v^{\prime}$ of $G_{\mathfrak{I}}$, $(v,v^{\prime})$
is an edge of $G_{\mathfrak{I}}$ if and only if it is an edge of $G$.

######  Definition 2.5.

For every pair of graphs $(G,H)$, let _$\mathrm{Occ}_{G}(H)$_ be the number of
partial injection $\mathfrak{I}$ from the vertex labels of $H$ to $\mathbb{N}$
such that $H_{\mathfrak{I}}$ is isomorphic to $G$.

######  Definition 2.6.

Let $k$ be a nonnegative integer We say that $G$ is a _graph with $k$ blossom_
if, for every $j\in\\{1,\dots,k\\}$, exactly one vertex of $G$ is labeled
$*_{j}$, and the remaining vertices have a distinct label in
$\\{1,\dots,|V|-k\\}$.

######  Remark.

For $k=0$ a graph with $0$ blossom is simply a graph.

######  Definition 2.7.

Let $G$ be a graph with $k$ blossoms and $v$ a vertex of $G$ which is not a
blossom. We define _$\mathrm{blo}_{v}(G)$_ to be the labeled graph obtained
after the following transformations:

  * •

$v$ is now labeled $*_{k+1}$;

  * •

the graph obtained is replaced by its reduction as defined in 2.2.

###  2.2. Encoding graphs with trees

A key construction to make the modular decomposition effective is the graph
substitution (also called substitution-composition).

######  Definition 2.8 (Graph substitution).

Let $G$ be a graph of size $n$ and $H_{1},\dots,H_{n}$ be weakly-labeled
graphs such the vertices of $H_{1},\dots,H_{n}$ have mutually distinct labels.
The graph _$G[H_{1},\dots,H_{n}]=(V,E)$_ is the graph whose set of vertices is
$V=\bigcup_{i=1}^{n}V_{H_{i}}$ and such that:

  * •

for every $i\in\\{1,\dots,n\\}$ and every pair $(v,v^{\prime})\in
V_{H_{i}}^{2}$, $\\{v,v^{\prime}\\}\in E$ if and only if
$\\{v,v^{\prime}\\}\in E_{H_{i}}$;

  * •

For every $(i,j)\in\\{1,\dots,n\\}$ with $i\neq j$, and every pair
$(v,v^{\prime})\in V_{H_{i}}\times V_{H_{j}}$, $\\{v,v^{\prime}\\}\in E$ if
and only if $\\{v_{i},v_{j}\\}\in E_{G}$.

######  Notation.

In the following we use the shortcut $\oplus$ for the complete graph of size
$n$. Thus $\oplus[H_{1},\dots,H_{n}]$ is the graph obtained from copies of
$H_{1},\dots,H_{n}$ in which for every $i\neq j$ every vertex of $H_{i}$ is
connected to every vertex of $H_{j}$. This graph is called the _join_ of
$H_{1},\dots,H_{n}$

We use the shortcut $\ominus$ for the graph with no edge of size $n$. Thus
$\ominus[H_{1},\dots,H_{n}]$ is the graph given by the disjoint union of
$H_{1},\dots,H_{n}$ This graph is called the _union_ of $H_{1},\dots,H_{n}$.

This construction allows us to transform non-plane labeled trees with internal
nodes decorated with graphs, $\oplus$ and $\ominus$ into graphs.

######  Definition 2.9.

Let $\mathcal{T}_{0}$ be the set of rooted non-plane trees whose leaves have
distinct labels in $\mathbb{N}$ and whose internal nodes carry decorations
satisfying the following constraints:

  * •

internal nodes are decorated with $\oplus$, $\ominus$ or a graph;

  * •

If a node is decorated with some graph $G$ then $|G|\geq 2$ and this node has
$|G|$ children. If a node is decorated with $\oplus$ or $\ominus$ then it has
at least 2 children.

A tree $t\in\mathcal{T}_{0}$ is called a _substitution tree_ if the labels of
its leaves are in $\\{1,\dots,|t|\\}$.

We call _linear_ the internal nodes decorated with $\oplus$ or $\ominus$ and
_non-linear_ the other ones.

######  Notation.

For a non-plane rooted tree $t$, and an internal node $\mathfrak{n}$ of $t$,
let $t_{\mathfrak{n}}$ be the multiset of trees attached to $\mathfrak{n}$ and
let $t[\mathfrak{n}]$ be the non-plane tree rooted at $\mathfrak{n}$
containing only the descendants of $\mathfrak{n}$ in $t$.

######  Convention.

We only consider non-plane trees. However it is sometimes convenient to order
the subtrees of a given node. The convention is that for some $\mathfrak{n}$
in a tree $t$ the trees of $t_{\mathfrak{n}}$ are ordered according to their
minimal leaf labels.

######  Definition 2.10.

Let $t$ be an element of $\mathcal{T}_{0}$, the weakly-labeled graph
_$\mathrm{Graph}(t)$_ is inductively defined as follows:

  * •

if $t$ is reduced to a single leaf labeled $j$, $\mathrm{Graph}(t)$ is the
graph reduced to a single vertex labeled $j$;

  * •

otherwise, the root $r$ of $t$ is decorated with a graph $H$, and

$\mathrm{Graph}(t)=H[\mathrm{Graph}(t_{1}),\dots,\mathrm{Graph}(t_{|H|})]$

where $t_{i}$ is the $i$-th tree of $t_{r}$.

If $G$ is a graph and $t_{0}$ is a tree in $\mathcal{T}_{0}$, we say that
$t_{0}$ is a substituion tree of $G$ if $\mathrm{Graph}(t_{0})=G$.

Figure 1. A substitution tree $t_{0}$ and the corresponding graph
$\mathrm{Graph}(t_{0})$.

Note that if $t$ is a substitution tree then $\mathrm{Graph}(t)$ is a labeled
graph.

###  2.3. Modular decomposition

In this short section we gather the main definitions and properties of modular
decomposition. The historical reference is [12], the interested reader may
also look at [8] or [18].

The next definitions and theorems allow to get a unique recursive
decomposition of any graph in the sense of 2.10, the modular decomposition,
and to encode it by a tree.

######  Definition 2.11.

Let $G$ be a graph (labeled or not). A _module_ $M$ of $G$ is a subset of $V$
such that for every $(x,y)\in M^{2}$, and every $z\in V\backslash M$,
$\\{x,z\\}\in E$ if and only if $\\{y,z\\}\in E$.

######  Remark.

Note that $\emptyset,V$ and $\\{v\\}$ for $v\in V$ are always modules of $G$.
Those sets are called the trivial modules of $G$.

######  Definition 2.12.

A graph $G$ is _prime_ if it has at least $3$ vertices and its only modules
are the trivial ones.

######  Definition 2.13.

A graph is called _$\ominus$ -indecomposable_ (resp.  _$\oplus$
-indecomposable_) if it cannot be written as $\ominus[G_{1},\dots,G_{k}]$
(resp. $\oplus[G_{1},\dots,G_{k}]$) for some $k\geq 2$ and weakly-labeled
graphs $G_{1},\dots,G_{k}$.

Note that a graph is $\ominus$-indecomposable if and only if it is connected,
and $\oplus$-indecomposable if and only if its complementary is connected.

######  Theorem 2.14 (Modular decomposition, [12]).

Let $G$ be a graph with at least $2$ vertices, there exists a unique partition
$\mathcal{M}=\\{M_{1},\dots,M_{k}\\}$ for some $k\geq 2$ (where the $M_{i}$’s
are ordered by their smallest element), where each $M_{i}$ is a module of $G$
and such that either

  * •

$G=\oplus[M_{1},\dots,M_{k}]$ and the $(M_{i})_{1\leq i\leq k}$ are
$\oplus$-indecomposable;

  * •

$G=\ominus[M_{1},\dots,M_{k}]$ and the $(M_{i})_{1\leq i\leq k}$ are
$\ominus$-indecomposable;

  * •

there exists a unique prime graph $P$ such that $G=P[M_{1},\dots,M_{k}]$.

This decomposition can be used to encode graphs by specific trees to get a
one-to-one correspondence.

######  Definition 2.15.

Let $t$ be a substitution tree. We say that $t$ is a _modular decomposition
tree_ if its internal nodes are either $\oplus$, $\ominus$ or prime graphs,
and if there is no child of a node decorated with $\oplus$ (resp. $\ominus$)
which is decorated with $\oplus$ (resp. $\ominus$).

To a graph $G$ we associate a modular decomposition tree by recursively
applying the decomposition of 2.14 to the modules $(M_{i})_{1\leq i\leq k}$,
until they are of size $1$. First of all, at each step, we order the different
modules increasingly according to their minimal vertex labels. Doing so, a
labeled graph $G$ can be encoded by a modular decomposition tree. The internal
nodes are decorated with the different graphs that are encountered along the
recursive decomposition process ($\oplus$ if $G=\oplus[M_{1},\dots,M_{k}]$,
$\ominus$ if $G=\ominus[M_{1},\dots,M_{k}]$, $P$ if $G=P[M_{1},\dots,M_{k}]$).
At the end, every module of size $1$ is converted into a leaf labeled by the
label of the vertex.

This construction provides a one-to-one correspondence between labeled graphs
and modular decomposition trees that maps the size of a graph to the size of
the corresponding tree.

######  Proposition 2.16.

Let $G$ be a graph, and $t$ its modular decomposition tree, then $t$ is the
only modular decomposition tree such that $\mathrm{Graph}(t)=G$.

######  Remark.

It is crucial to consider modular decomposition trees as non-plane: otherwise,
since prime graphs appearing in the decorations can have several labelings,
there would be several modular decomposition trees associated with the same
graph.

###  2.4. Expanded trees

An important tool that will be used in Section 6 to prove 1.1 is the notion of
expanded trees, which are substitution trees corresponding to a fixed graph
and maximizing the number of edges. The aim of this subsection is to prove
2.20, which will be the only result used later.

######  Definition 2.17.

Let $G$ be a graph. An _expanded tree_ of $G$ is a substitution tree $t_{0}$
of $G$ whose non-linear nodes are decorated with prime graphs and all linear
nodes have exactly two children.

We introduce the inflation operation to build expanded tree from any given
tree, and to count later the number of expanded tree corresponding to a graph.
Let $t$ be a substitution tree, $\mathfrak{n}$ an internal node of $t$ and
$\tau$ a substitution tree of the decoration of $\mathfrak{n}$. Consider the
following modifications of $t$:

  * •

the node $\mathfrak{n}$ is replaced by $\tau$;

  * •

for every $j$, the $j$-th leaf of $\tau$ is replaced by the $j$-th tree of
$t[\mathfrak{n}]$.

The resulting tree is called the inflation of $t$ at $\mathfrak{n}$ with
$\tau$. Note that it is still a substitution tree of $\mathrm{Graph}(t)$, and
that every inflation increases the number of edges if it does change $t$. See
Fig. 2 for an example of inflation.

Figure 2. From left to right: a tree $\tau$, $\tau_{0}$ the inflation of
$\tau$ at $\mathfrak{n_{0}}$ with $t_{0}$, $\tau_{1}$ the inflation of
$\tau_{0}$ at $\mathfrak{n_{1}}$ with $t_{1}$ which is an expanded tree.

######  Lemma 2.18.

Let $G$ be a graph and $t$ a substitution tree of $G$. The tree $t$ can be
transformed into an expanded tree of $G$ by applying successive inflations.

###### Proof.

For every non-linear node $\mathfrak{n}$ whose decoration is not prime, we can
perform the inflation operation with the modular decomposition tree of the
decoration of $\mathfrak{n}$ to get a tree whose non-linear nodes are all
prime. Then for every linear nodes that has $k>2$ children, we can perform the
inflation operation with a binary non-plane tree with $k$ leaves, and whose
internal nodes are all decorated with $\oplus$. We thus get an expanded tree.
∎

######  Lemma 2.19.

Let $G$ be a graph and $t$ the modular decomposition tree of $G$. Every
expanded tree of $G$ can be obtained by inflating every linear node
$\mathfrak{n}$ of $t$ of size $k$ with a binary tree with $k$ leaves.

###### Proof.

Take one expanded tree $t^{\prime}$ of $G$. We can merge every connected
component of internal nodes of $t^{\prime}$ decorated with $\oplus$ (resp.
$\ominus$) into one single node decorated with $\oplus$ (resp. $\ominus$), and
get a tree $\tau$ such that $\tau$ is a modular decomposition tree: since
$t^{\prime}$ is an expanded tree, the non-linear nodes of the resulting tree
are prime, and by construction, two successive linear nodes cannot share the
same decoration. Moreover $\mathrm{Graph}(t)=\mathrm{Graph}(t^{\prime})=G$:
thus $\tau=t$. Doing the reverse operation of merging is exactly the infation
of every linear node $\mathfrak{n}$ of $t$. Since in $t^{\prime}$ every linear
nodes has two children, these inflations are done with binary trees. ∎

######  Corollary 2.20.

Let $G$ be a graph of size $n$, $\tau$ its modular decomposition tree. Let $k$
(resp. $j$) be the number of linear (resp. non-linear) nodes of $\tau$. We
arbitrarily order the linear (resp. non-linear) nodes of $\tau$: let $d_{i}$
(resp. $e_{i}$) be the number of children of the $i$-th linear (resp. non-
linear) node of $\tau$ for $1\leq i\leq k$ (resp. $1\leq i\leq j$). Then there
are exactly $\prod\limits_{i=1}^{k}(2d_{i}-3)!!$ expanded trees of $G$, each
having $2n-2-\sum\limits_{i=1}^{j}(e_{i}-2)$ edges.

###### Proof.

2.19 imply that there are exactly

$\prod\limits_{i=1}^{k}\\#\\{\text{Non-plane trees with}\ d_{i}\
\text{vertices}\\}$

expanded trees of $G$.

Note that unrooted non-plane trees with $r+1$ vertices are in bijection with
rooted non-plane trees with $r$ vertices (by deleting the leaf of label $r+1$
and choosing the root to be its only neighbour in the tree). From [3], there
are $(2r-3)!!$ rooted non-plane trees with $r$ vertices. Thus there exists
$(2r-3)!!$ non-plane trees with leaves labeled from $1$ to $r+1$ and there are
exactly $\prod\limits_{i=1}^{k}(2d_{i}-3)!!$ expanded trees of $G$.

Note that $\\#\text{edge}=\\#\text{internal node}+\\#\text{leave}-1$. Thus
$\\#\text{internal node}=\\#\text{edge}-(n-1)$. Moreover, the number of edges
is also the sum of the numbers of children of every internal nodes. Since all
non-linear nodes are binary,
$\sum\limits_{i=1}^{j}|e_{i}|-2=\\#\text{edge}-2\\#\text{internal node}$. Thus
$2n-2-\sum\limits_{i=1}^{j}(e_{i}-2)=\\#\text{edge}$. ∎

In the following, with the notations of 2.20, we denote for every graph $G$

(1) $\displaystyle\beta(G):=\frac{1}{2}\sum\limits_{i=1}^{j}(e_{i}-2).$

Note that $\beta(G)$ is positive if and only if $G$ is not a cograph.

##  3\. Background on graphons

We now review the necessary material on graphons. We refer the reader to [17]
for a comprehensive presentation of deterministic graphons, while [10] studies
specifically the convergence of random graphs in the sense of graphons. Here
we only recall the properties needed to prove the convergence of random graphs
towards the Brownian cographon (see [5]).

######  Definition 3.1.

A graphon is an equivalence class of symmetric functions
$f:[0,1]^{2}\mapsto[0,1]$, under the equivalence relation $\sim$, where $f\sim
g$ if there exists a measurable function $\phi:[0,1]\mapsto[0,1]$ that is
invertible and measure preserving such that, for almost every
$(x,y)\in[0,1]^{2}$, $f(\phi(x),\phi(y))=g(x,y)$. We denote by
$\tilde{\mathcal{W}}$ the set of graphons.

Intuitively graphons can be seen as continuous analogous of graph adjacency
matrices, where graphs are considered up to relabeling (hence the quotient by
$\sim$). There is a natural way to embed a finite graph into graphons:

######  Definition 3.2.

Let $G$ be a (random) graph of size $n$. We define the (random) graphon
$W_{G}$ to be the equivalence class of $w_{G}:[0,1]^{2}\mapsto[0,1]$ defined
by:

$\displaystyle\forall(x,y)\in[0,1]^{2}\quad w_{G}(x,y)$
$\displaystyle:=1_{\lceil nx\rceil\text{connected to}\lceil ny\rceil}$

There exists a pseudo-metric $\delta_{\square}$ on the set of graphons. If
$\tilde{\mathcal{W}}$ is the set of graphons quotiented by the equivalence
relation $W\equiv W^{\prime}$ if $\delta_{\square}(W,W^{\prime})=0$, we get
that $(\tilde{\mathcal{W}},\delta_{\square})$ is compact [17, Chapter 8].

Now we introduce random variables that play the role of margins in the space
of graphons. For $k\geq 1$ and $\mathbf{W}$ a random graphon, we denote by
$\mathrm{Sample}_{k}(\mathbf{W})$ the unlabeled random graph built as follows:
$\mathrm{Sample}_{k}(W)$ has vertex set $\\{v_{1},v_{2},\dots,v_{k}\\}$ and,
letting $(X_{1},\dots,X_{k})$ be i.i.d. uniform random variables in $[0,1]$,
we connect vertices $v_{i}$ and $v_{j}$ with probability $w(X_{i},X_{j})$
(these events being independent, conditionally on $(X_{1},\cdots,X_{k})$ and
$\mathbf{W}$). The construction does not depend on the representation of the
graphon, and is compatible with the quotient. Moreover, if $\mathbf{W}$ is a
random graphon, $(\mathrm{Sample}_{k}(\mathbf{W}))_{k\geq 0}$ determines the
law of $\mathbf{W}$.

Since $(\tilde{\mathcal{W}},\delta_{\square})$ is compact, we can define for
$\delta_{\square}$ the convergence in distribution of a random graphon. If
$(\mathbf{G}^{(n)})_{n\geq 1}$ is a sequence of random graphs, there exists a
simple criterion [10, Theorem 3.1] characterizing the convergence in
distribution of $(W_{\mathbf{G}^{(n)}})$ with respect to $\delta_{\square}$:

######  Theorem 3.3 (Rephrasing of [10], Theorem $3.1$).

For any $n$, let $\mathbf{G}^{(n)}$ be a random graph of size $n$. Denote by
$W_{\mathbf{G}^{(n)}}$ the random graphon associated to ${\mathbf{G}^{(n)}}$
and $\mathbf{W}$ a random graphon. The following assertions are equivalent:

  1. (a)

The sequence of random graphons $(W_{\mathbf{G}^{(n)}})_{n\geq 1}$ converges
in distribution to $\mathbf{W}$.

  2. (b)

The random infinite vector
$\left(\frac{\mathrm{Occ}_{H}(\mathbf{G}^{(n)})}{n^{|H|}}\right)_{H\text{
finite graph}}$ converges in distribution in the product topology to

$\left(\mathbb{P}(\mathrm{Sample}_{|H|}(\mathbf{W})=H\ |\
\mathbf{W})\right)_{H\text{ finite graph}}.$

  3. (c)

For every finite graph $H$, there is a constant $\Delta_{H}\in[0,1]$ such that

$\mathbb{E}\left[\frac{\mathrm{Occ}_{H}(\mathbf{G}^{(n)})}{n^{|H|}}\right]\xrightarrow{n\to\infty}\mathbb{P}(\mathrm{Sample}_{|H|}(\mathbf{W})=H).$

  4. (d)

For every $\ell\geq 1$, denote by $\mathbf{\mathfrak{I}_{\ell}}^{(n)}$ be a
uniform partial injection from $\\{1,\dots,n\\}$ whose image is
$\\{1,\dots,\ell\\}$ Then the subgraph of $\mathbf{G}^{(n)}$ induced by
$\mathbf{\mathfrak{I}_{\ell}}^{(n)}$ converges in distribution to
$\mathrm{Sample}_{\ell}(\mathbf{W})$.

For every $p\in[0,1]$, the article [5] introduces a random graphon
$\mathbf{W}^{p}$ called the Brownian cographon which can be explicitly
constructed as a function of a realization of a Brownian excursion. Besides,
[5, Proposition 5] states that the distribution of the Brownian cographon is
characterized111This characterization is strongly linked to the remarkable
property that $k$ uniform leaves in the CRT induce a uniform binary tree with
$k$ leaves, see again [5, Section 4.2]. by the fact that for every $k\geq 2$,
$\mathrm{Sample}_{k}(\mathbf{W}^{p})$ has the same law as the unlabeled
version of $\mathrm{Graph}(\mathbf{b}_{k}^{p})$ with $\mathbf{b}_{k}^{p}$ a
uniform labeled binary tree with $k$ leaves and i.i.d. uniform decorations in
$\\{\oplus,\ominus\\}$, such that the probability of an internal node being
decorated with $\oplus$ is $p$.

A consequence of this characterization is a simple criterion for convergence
to the Brownian cographon.

######  Lemma 3.4 (Generalization of [5] Lemma $4.4$).

For every $n\geq 1$, let $\mathcal{T}_{n}$ be a subset of trees in
$\mathcal{T}_{0}$ with $n$ leaves. For every positive integer $n$, let
$\mathbf{T}^{(n)}$ be a uniform random tree in $\mathcal{T}_{n}$ with $n$
vertices. For every positive integer $\ell$,
$\mathbf{\mathfrak{I}_{\ell}}^{(n)}$ be a uniform partial injection from
$\\{1,\dots,n\\}$ to $\mathbb{N}$ whose image is $\\{1,\dots,\ell\\}$ and
independent of $\mathbf{T}^{(n)}$. Denote by
$\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}$ the subtree induced by
$\mathbf{\mathfrak{I}_{\ell}}^{(n)}$.

Suppose that for every $\ell$ and for every binary non-plane tree $\tau$ with
$\ell$ leaves and having $V_{+}$ (resp. $V_{-}$) internal nodes decorated with
$\oplus,$ (resp. $\ominus$),

(2)
$\mathbb{P}(\mathbf{T}_{\mathbf{\mathfrak{I}}^{(n)}}^{(n)}=\tau)\xrightarrow[n\to\infty]{}\frac{(\ell-1)!}{(2\ell-2)!}p^{V_{+}}(1-p)^{V_{-}}.$

Then $W_{\mathrm{Graph}(\mathbf{T}^{(n)})}$ converges as a graphon to the
Brownian cographon $\mathbf{W}^{p}$ of parameter $p$.

###### Proof.

The proof is very similar to the proof of Lemma $4.4$ in [5]. Let $\tau$ be a
binary tree, $\ell$ its number of tree, $V_{+}$ (resp. $V_{-}$) its number of
internal nodes decorated with $\oplus,$ (resp. $\ominus$). Since there are
$\frac{(2\ell-2)!}{((\ell-1)!}$ binary non-plane tree with $\ell$ leaves,
$\mathbb{P}(b_{k}^{p}=\tau)=\frac{(\ell-1)!}{(2\ell-2)!}p^{V_{+}}(1-p)^{V_{-}}$.
Thus we have the following convergence as random labeled graphs:

$\mathrm{Graph}(\mathbf{T}_{\mathbf{\mathfrak{I}}^{(n)}}^{(n)})\stackrel{{\scriptstyle(d)}}{{\longrightarrow}}\mathrm{Graph}(b_{k}^{p})\
\overset{\text{(d)}}{{=}}\ \mathrm{Sample}_{k}(\mathbf{W}^{p}).$

After forgetting the labels, we get that criterion $(d)$ in 3.3 is verified
for $\left(\mathrm{Graph}(\mathbf{T}^{(n)})\right)_{n}$, which converges to
$\mathbf{W}^{p}$. ∎

##  4\. Graphs in $\mathcal{G}_{\mathcal{P}}$: enumerative results

The aim of this section is to compute several exponential generating series of
graph classes which will be used in Section 5.

###  4.1. Exact enumeration

Throughout this section, we consider a fixed set $\mathcal{P}$ of prime graphs
stable by relabeling. Let
$P(z)=\sum\limits_{G\in\mathcal{P}}\frac{z^{|G|}}{|G|!}$ be the exponential
generating function associated to a given set $\mathcal{P}$.

######  Definition 4.1.

Let $\mathcal{T}_{\mathcal{P}}$ be the set of modular decomposition trees
whose node are either linear or in $\mathcal{P}$. Let
$\mathcal{G}_{\mathcal{P}}$ be the set of graphs whose modular decomposition
tree is in $\mathcal{T}_{\mathcal{P}}$.

For $n\in\mathbb{N}$, let $\mathcal{P}_{n}$ be the set of graphs $G$ in
$\mathcal{P}$ of size $n$.

Let $T$ be the exponential generating function of $\mathcal{T}_{\mathcal{P}}$
counted by their number of leaves. Denote by
$\mathcal{T}_{\mathrm{not}\oplus}$ the set of all
$t\in\mathcal{T}_{\mathcal{P}}$ whose root is not decorated with $\oplus$
(resp. $\ominus$) and by $T_{\mathrm{not}\oplus}$ (resp.
$T_{\mathrm{not}\ominus}$) the corresponding exponential generating function.
(Regarding generating functions, we skip the dependence on $\mathcal{P}$.)
Throughout section $2.1$, all generating functions are considered as formal
power series.

######  Theorem 4.2.

The exponential generating function $T_{\mathrm{not}\oplus}$ verifies the
following equation:

(3) $\displaystyle T_{\mathrm{not}\oplus}=$ $\displaystyle
z+P(\exp(T_{\mathrm{not}\oplus})-1)+\exp(T_{\mathrm{not}\oplus})-1-T_{\mathrm{not}\oplus},$

and the series $T$ and $T_{\mathrm{not}\ominus}$ are simply given by the
following equations:

(4) $\displaystyle T=\exp(T_{\mathrm{not}\oplus})-1$ (5) $\displaystyle
T_{\mathrm{not}\ominus}=T_{\mathrm{not}\oplus}$

Moreover, Eq. 3 with $T_{\mathrm{not}\oplus}(0)=0$ determines (as a formal
series) uniquely the generating function $T_{\mathrm{not}\oplus}$.

###### Proof.

Note that there is a natural involution on $\mathcal{T}_{\mathcal{P}}$: the
decoration of every linear node can be changed to its opposite: $\oplus$ to
$\ominus$, and $\ominus$ to $\oplus$. Therefore
$T_{\mathrm{not}\oplus}=T_{\mathrm{not}\ominus}$.

First, we prove that

(6) $\displaystyle T_{\mathrm{not}\oplus}$
$\displaystyle=z+P(T)+(\exp(T_{\mathrm{not}\oplus})-1-T_{\mathrm{not}\oplus}).$

We split the enumeration of the trees $t\in\mathcal{T}_{\mathrm{not}\oplus}$
according to the different possible cases.

  * •

The tree $t$ is a single leaf (which gives the $z$ in Eq. 6).

  * •

The tree $t$ has a root decorated with a graph $H$ belonging to $\mathcal{P}$.
The exponential generating function for a fixed $H$ is $\frac{T^{|H|}}{|H|!}$.
Summing over all $H$ and all $n$ gives the term $P(T)$ in Eq. 6.

  * •

The tree $t$ has a root $r$ decorated with $\ominus$ and having $k$ children
with $k\geq 2$. In this case, the generating function of the set of the $k$
subtrees of $t_{r}$ is $\frac{T_{\mathrm{not}\oplus}^{k}}{k!}$. Summing over
all $k$ implies that the exponential generating function of all trees in case
$(D3)$ with a root decorated with $\oplus$ is
$\exp(T_{\mathrm{not}\oplus})-1-T_{\mathrm{not}\oplus}$.

Summing all terms gives Eq. 6.

We split the enumeration of the trees $t\in\mathcal{T}_{\mathcal{P}}$
according to the different possible cases.

  * •

The root is not decorated with $\oplus$: the exponential generating function
is $T_{\mathrm{not}\oplus}$

  * •

The root is decorated with $\oplus$. The exponential generating function is
$\exp(T_{\mathrm{not}\oplus})-1-T_{\mathrm{not}\oplus}$

Summing gives Eq. 4. Then Eq. 3 is an easy consequence from Eqs. 4 and 6.

Note that Eq. 3 can be rewritten as:

(7) $\displaystyle T_{\mathrm{not}\oplus}$ $\displaystyle=z+\sum\limits_{k\geq
3}|\mathcal{P}_{k}|\left(\sum\limits_{\ell\geq
1}T_{\mathrm{not}\oplus}^{\ell}\right)^{k}+\sum\limits_{k\geq
2}\frac{T_{\mathrm{not}\oplus}^{k}}{k!}.$

For every $n\geq 1$, the coefficient of degree $n$ of $T_{\mathrm{not}\oplus}$
only depends on coefficients of lower degree as $T_{\mathrm{not}\oplus}(0)=0$.
Thus Eq. 3 combined with $T_{\mathrm{not}\oplus}(0)=0$ determines uniquely
$T_{\mathrm{not}\oplus}$.∎

We are going to define the notions of trees with marked leaves, and of
blossomed trees, which will be crucial in the next section. We insist on the
fact that the size parameter counts the number of leaves including the marked
ones but not the blossoms.

######  Definition 4.3.

A _marked tree_ is a pair $(t,\mathfrak{I})$ where $t$ is a tree and
$\mathfrak{I}$ a partial injection from the set of labels of leaves of $t$ to
$\mathbb{N}$. The number of marked leaves is the size of the domain of
$\mathfrak{I}$ denoted by $|(t,\mathfrak{I})|$, and a leaf is marked if its
label $j$ is in the domain, its mark being $\mathfrak{I}(j)$.

######  Remark.

In the following, we consider marked trees $(t,\mathfrak{I})$, and subtrees
$t^{\prime}$ of $t$. The marked tree $(t^{\prime},\mathfrak{I})$ refers to the
marked tree $(t^{\prime},\mathfrak{I}^{\prime})$ where $\mathfrak{I}^{\prime}$
is the restriction of $\mathfrak{I}$ to the set of labels of leaves of
$t^{\prime}$.

######  Remark.

Let
$\mathcal{F}\in\\{\mathcal{T}_{\mathcal{P}},\mathcal{T}_{\mathrm{not}\ominus}\\}$,
and $F$ be its generating exponential function. The exponential generating
function of trees in $\mathcal{F}$ with a marked leaf is $zF^{\prime}(z)$: if
there are $f_{n}$ trees of size $n$ in $\mathcal{F}$, there are $nf_{n}$ trees
with a marked leaf. Thus the generating exponential function is
$\sum\limits_{n\geq 1}\frac{nf_{n}}{n!}z^{n}=zF^{\prime}(z)$.

#### Blossoming transformation

Let $t$ be a tree in $\mathcal{T}_{\mathcal{P}}$and $\ell$ a leaf of $t$. We
introduce an operation called the _blossoming_ of $(t,\ell)$ as follows:

  * •

For every non-linear node $\mathfrak{n}$ belonging to the shortest path
between $\ell$ and the root, let $i$ be the only integer such that $\ell$ is
in the $i$-th tree of $t_{\mathfrak{n}}$. We replace the label $i$ of the
decoration of $\mathfrak{n}$ by $*$, and do the reduction on the decoration of
$\mathfrak{n}$;

  * •

We replace the label of $\ell$ by $*$ and do the reduction on $t$.

We extend this operation to internal node: if $\mathfrak{n}$ is a internal
node, we replace $t[\mathfrak{n}]$ by its leaf of smallest label, and do the
blossoming operation on the tree obtained. The resulting tree is still called
the _blossoming_ of $t$ at $\mathfrak{n}$ (see example in Fig. 3.

Figure 3. Left: a tree $t\in\mathcal{T}_{\mathcal{P}}$. Right: the blossoming
of $t$ at the leaf of label $4$.

######  Definition 4.4.

A _blossomed tree_ is a tree that can be obtained by the blossoming of a tree
in $\mathcal{T}_{\mathcal{P}}$. Its size is its number of leaves without
blossom.

A blossom is _$\oplus$ -replaceable_ (resp.  _$\ominus$ -replaceable_) if its
parent is not decorated with $\oplus$ (resp. $\ominus$).

######  Remark.

Similarly to a tree, a blossomed tree can be marked by a partial injection
$\mathfrak{I}$.

We denote $\mathcal{T}^{b}$ and $\mathcal{T}_{a}^{b}$ with
$a\in\\{\mathrm{not}\oplus,\mathrm{not}\ominus\\}$, and
$b\in\\{\oplus,\ominus,\mathsf{blo}\\}$ the set of trees whose root is not
$\oplus$ (resp. $\ominus$) if $a=\mathrm{not}\oplus$ (resp.
$a=\mathrm{not}\ominus$), and with one blossom that is $b$-replaceable if
$b=\oplus$ or $\ominus$, or just with one blossom if $b=\mathsf{blo}$.

We define $T^{b}$ and $T_{a}^{b}$ to be the corresponding exponential
generating functions of trees, counted by the number of non blossomed leaves.

However, we take the convention that
$T_{\mathrm{not}\oplus}^{\oplus}(0)=0=T_{\mathrm{not}\ominus}^{\ominus}$. In
other words, a single leaf is neither in
$\mathcal{T}_{\mathrm{not}\oplus}^{\oplus}$ nor in
$\mathcal{T}_{\mathrm{not}\ominus}^{\ominus}$. The other series have constant
coefficient $1$.

######  Remark.

From the previously defined involution, it follows that
$T_{\mathrm{not}\oplus}^{\ominus}=T_{\mathrm{not}\ominus}^{\oplus}$,
$T_{\mathrm{not}\oplus}^{\oplus}=T_{\mathrm{not}\ominus}^{\ominus}$ et
$T^{\oplus}=T^{\ominus}$ and
$T_{\mathrm{not}\oplus}^{\mathrm{blo}}=T_{\mathrm{not}\ominus}^{\mathrm{blo}}$.

######  Proposition 4.5.

The functions $T^{\mathrm{blo}},T_{\mathrm{not}\oplus}^{\mathrm{blo}}$ are
given by the following equations:

(8) $\displaystyle T^{\mathrm{blo}}=T^{\prime}$ (9) $\displaystyle
T_{\mathrm{not}\oplus}^{\mathrm{blo}}=T_{\mathrm{not}\oplus}^{\prime}=T^{\prime}\exp(-T_{\mathrm{not}\oplus})$

###### Proof.

Let
$\mathcal{F}\in\\{\mathcal{T}_{\mathcal{P}},\mathcal{T}_{\mathrm{not}\ominus}\\}$,
and $F$ be its generating exponential function. The exponential generating
function of blossomed trees in $\mathcal{F}$ is $F^{\prime}(z)$: if there are
$f_{n}$ trees of size $n$ in $\mathcal{F}$, there are $nf_{n}$ trees with a
marked leaf. Since $\mathcal{P}$ is stable by relabeling, every blossomed tree
of size $n-1$ can be obtained from exactly $n$ trees with a marked leaf (after
blossoming the marked leaf). Thus there are $f_{n}$ blossomed trees of size
$n-1$, the generating exponential function is $\sum\limits_{n\geq
1}\frac{f_{n}}{(n-1)!}z^{n-1}=F^{\prime}(z)$ which implies Eqs. 8 and 9 (the
last equality of Eq. 9 comes from differentiating Eq. 4). ∎

######  Theorem 4.6.

The functions
$T^{\oplus},T_{\mathrm{not}\oplus}^{\oplus},T_{\mathrm{not}\ominus}^{\oplus}$
are given by the following equations:

(10) $\displaystyle T^{\oplus}=T^{\prime}\exp(-T_{\mathrm{not}\oplus})$ (11)
$\displaystyle
T_{\mathrm{not}\oplus}^{\ominus}=\frac{1}{\exp(T_{\mathrm{not}\oplus})}T^{\oplus}$
(12) $\displaystyle
T_{\mathrm{not}\oplus}^{\oplus}=\frac{T^{\oplus}-1}{\exp(T_{\mathrm{not}\oplus})}$

###### Proof.

First let’s prove that $T^{\prime}=T^{\oplus}\exp(T_{\mathrm{not}\oplus})$
using that $T^{\prime}$ is the generating function of blossomed trees.

Figure 4. Illustration of the proof of Eq. 10.

A blossomed tree $t$ is in exactly one of both cases:

  * •

the blossom of $t$ is $\oplus$-replaceable, thus the exponential generating
series is $T^{\oplus}$;

  * •

the blossom of $t$ is not $\oplus$-replaceable, let $n$ be its parent. We
define $t^{\prime}$ to be $t$ blossomed at $n$. The exponential generating
function of $t$ is the product of the exponential generating function of
$t^{\prime}$, which is $T^{\oplus}$ as the blossom must be $\oplus$
replaceable, and of the exponential generating function of $t_{n}$ (a forest
of trees whose root is not decorated with $\oplus$, with at least one tree)
which is $\exp(T_{\mathrm{not}\oplus})-1$. Thus the exponential generating
function of blossomed trees whose blossom is not $\oplus$-replaceable is
$T^{\oplus}(\exp(T_{\mathrm{not}\oplus})-1)$

Summing implies $T^{\prime}=T^{\oplus}\exp(T_{\mathrm{not}\oplus})$ which is
equivalent to Eq. 10.

Figure 5. Illustration of the proof of Eq. 11.

Since the proofs of Eq. 11 and Eq. 12 are very similar, we only prove Eq. 12.
Let $t$ be a tree in $\mathcal{T}^{\oplus}$:

  * •

The tree $t$ can be a blossom, whose exponential generating function is $1$;

  * •

The tree $t$ can have a root not decorated with $\oplus$, the corresponding
exponential generating function is $T_{\mathrm{not}\oplus}^{\oplus}$

  * •

The tree $t$ can have a root $r$ decorated with $\oplus$ and having $k$
children with $k\geq 2$. There are $k-1$ subtrees without blossom, and $1$
with a blossom. Thus the generating function of the set of the $k$ subtrees of
$t_{r}$ is
$\frac{T_{\mathrm{not}\oplus}^{k-1}}{(k-1)!}T_{\mathrm{not}\oplus}^{\oplus}$.
Summing over all $k$ gives that the exponential generating function of all
trees in case $(D3)$ with a root decorated with $\ominus$ is

$\sum\limits_{k\geq
2}\frac{T_{\mathrm{not}\oplus}^{k-1}}{(k-1)!}T_{\mathrm{not}\oplus}^{\oplus}=(\exp(T_{\mathrm{not}\oplus})-1)T_{\mathrm{not}\oplus}^{\oplus}$

Summing gives
$T^{\oplus}=1+\exp(T_{\mathrm{not}\oplus})T_{\mathrm{not}\oplus}^{\oplus}$
which implies Eq. 12. ∎

###  4.2. Asymptotic enumeration

In the following, we derive from the previously obtained equations the radii
of the different series introduced, the asymptotic behavior of the different
series in $R$ and an equivalent of the number of graphs in
$\mathcal{G}_{\mathcal{P}}$

From now on, we assume that $P$ has a positive radius of convergence $R_{0}$.
Denote by $P(R_{0})$ the limit in $[0,+\infty]$ of $P$ at $R_{0}^{-}$ (which
exists as $H$ has nonnegative coefficients and radius of convergence at least
$R_{0}$). Define $\Lambda(w)=P(\exp(w)-1)+\exp(w)-1-w$

######  Lemma 4.7.

The radius of convergence of $\Lambda$ is $R_{\Lambda}:=\log(1+R_{0})$.

###### Proof.

$\Lambda$ has positive coefficients and no singularity in $[0,\log(1+R_{0}))$
as $P$ has no singularity in $[0,R_{0})$, thus it has radius of convergence at
least $\log(1+R_{0})$. If $R_{0}=+\infty$, it implies the lemma. Otherwise, by
contradiction assume that the radius of convergence of $\Lambda$ is greater
than $\log(1+R_{0})$. The same holds for $P(\exp(w)-1)$ and
$w\mapsto\exp(w)-1$ can be inverted on a neighbourhood of $\log(1+R_{0})$ as
its derivative is non zero, thus $S$ can be extended to a neighbourhood of
$R_{0}$, which contradicts Pringsheim’s lemma [11, Theorem IV.6, p. 240]. ∎

Denote by $\Lambda^{\prime}(R_{\lambda})$ the limit in $[0,+\infty]$ of
$\Lambda^{\prime}$ in $R_{\Lambda}^{-}$. In the rest of this paper, we assume
that Condition (C) defined Condition (C) is verified. Note that conditon (C)
can be written as:

######  Condition (C).

$\Lambda^{\prime}(R_{\Lambda})>1$

Denote by $\kappa$ the only solution in $[0,R_{\Lambda})$ of the equation:

(13) $\displaystyle\Lambda^{\prime}(\kappa)=1$

Let $K:=\exp(\kappa)-1$, the equation $\Lambda^{\prime}(\kappa)=1$ can be
rewritten as follows:

(14) $\displaystyle(1+K)(P^{\prime}(K)+1)=2$

Recall that a formal series $A$ is _aperiodic_ if there does not exist two
integers $r\geq 0$ and $d\geq 2$ and $B$ a formal series such that
$A(z)=z^{r}B(z^{d})$.

######  Lemma 4.8.

The functions $T$, $T_{\mathrm{not}\oplus}$, $T^{\oplus}$,
$T_{\mathrm{not}\oplus}^{\ominus}$, $T_{\mathrm{not}\oplus}^{\oplus}$,
$T^{\mathrm{blo}}$, $T_{\mathrm{not}\oplus}^{\mathrm{blo}}$ are aperiodic.

###### Proof.

One can easily check that for each of the previous series, the coefficients of
degree $3$ and $4$ are positive, and thus all the series are aperiodic.∎

######  Definition 4.9.

A set $\Delta$ is a $\Delta$-domain at $1$ if there exist two positive numbers
$R$ and $\frac{\pi}{2}<\phi<\pi$ such that

$\Delta=\\{z\in\mathbb{C}||z|\leq R,z\neq 1,|\mathrm{arg}(1-z)|<\phi\\}$

For every $w\in\mathbb{C}^{*}$, a set is a $\Delta$-domain at $w$ if it is the
image of a $\Delta$-domain by the mapping $z\mapsto zw$.

######  Definition 4.10.

A power series $U$ is said to be _$\Delta$ -analytic_ if it has a positive
radius of convergence $\rho$ and there exists a $\Delta$-domain $D$ at $\rho$
such that $U$ has an analytic continuation on $D$.

######  Proposition 4.11.

Under Condition (C) defined p.Condition (C), both $T$ and
$T_{\mathrm{not}\oplus}$ have $R:=\kappa-\Lambda(\kappa)$ as radius of
convergence and a unique dominant singularity at $R$. They are
$\Delta$-analytic. Their asymptotic expansions near $R$ are:

(15) $\displaystyle
T_{\mathrm{not}\oplus}(z)=\kappa-\frac{2R}{\mu}\sqrt{1-\frac{z}{R}}+O\left(1-\dfrac{z}{R}\right)$
(16) $\displaystyle
T(z)=K-(1+K)\frac{2R}{\mu}\sqrt{1-\frac{z}{R}}+O\left(1-\dfrac{z}{R}\right)$
(17) $\displaystyle
T^{\oplus}=\frac{1}{\mu}\left(1-\frac{z}{R}\right)^{-\frac{1}{2}}+O\left(1\right)$

where $\mu$ and $K$ are the constants given by:

(18) $\displaystyle\mu$
$\displaystyle=\sqrt{2R\Lambda^{\prime\prime}(\kappa)}$ (19) $\displaystyle K$
$\displaystyle=\exp(\kappa)-1$

###### Proof.

First of all, note that since $\Lambda^{\prime}<1$ on $[0,\kappa)$, $R$ is
positive

We begin with the expansion of $T_{\mathrm{not}\oplus}$ for which we apply the
smooth implicit theorem [11, Theorem VII.3, p.467]. Following [11, Sec
VII.4.1] we claim that $T_{\mathrm{not}\oplus}$ satisfies the settings of the
so-called _smooth implicit-function schema_ : $T_{\mathrm{not}\oplus}$ is
solution of

$T=G(z,T),$

where $G(z,w)=z+P(\exp(w)-1)+(\exp(w)-1-w)=z+\Lambda(w)$.

The singularity analysis of $T_{\mathrm{not}\oplus}$ goes through the study of
the characteristic system:

$\begin{cases}&G(r,s)=s,\\\ &G_{w}(r,s)=1\end{cases}\qquad\text{ with }0<r<R,\
s>0$

where $F_{x}=\frac{\partial F}{\partial x}$.
Note that $(r,s)=\left(R,\kappa\right)$ is a solution of the characteristic
system of $G$ since

  * •

$G_{w}(r,s)=\Lambda^{\prime}(\kappa)=1$

  * •

$G(r,s)=R+\Lambda(\kappa)=\kappa=s$

Moreover

  * •

$G_{z}(r,s)=1$

  * •

$G_{w,w}(r,s)=\Lambda^{\prime\prime}(\kappa)$

The expansion of $T$ is then a consequence of Eq. 4 and of the expansion of
$T_{\mathrm{not}\oplus}$.

For the expansion of $T^{\oplus}$, since $T$ and $T_{\mathrm{not}\oplus}$ can
be extended to a $\Delta$-domain at $R$, singular differentiation [11, Theorem
VI.8 p.419] yields the announced expansions when $z$ tends to $R$ and that
$T^{\oplus}$ can be extended to a $\Delta$-domain at $R$. These expansions
show that $T^{\oplus}$ a radius of convergence exactly equal to $R$.∎

Applying the Transfer Theorem [11, Corollary VI.1 p.392] to the results of
4.11, we obtain an equivalent of the number of trees of size $n$ in
$\mathcal{T}_{\mathcal{P}}$. Since there is a one-to-one correspondence
between graphs in $\mathcal{G}_{\mathcal{P}}$ and trees in
$\mathcal{T}_{\mathcal{P}}$, we get the following result:

######  Theorem 4.12.

Under Condition (C) defined p.Condition (C), the number of graphs in
$\mathcal{G}_{\mathcal{P}}$ of size $n$ is asymptotically equivalent to

$C\frac{n!}{R^{n}n^{\frac{3}{2}}}\quad\text{where}\quad
C=\frac{(1+K)R}{\mu\sqrt{\pi}}.$

##  5\. Graphs in $\mathcal{G}_{\mathcal{P}}$: enumeration of graphs with a
given induced subgraph

The heart of this section is 5.8, the combinatorial decomposition of graphs in
$\mathcal{G}_{\mathcal{P}}$ with a given induced subgraph.

###  5.1. Induced subtrees and subgraphs

We recall that the size of a graph is its number of vertices, and the size of
a tree is its number of leaves.

######  Definition 5.1 (First common ancestor).

Let $t$ be a rooted tree and let $\ell_{1},\ell_{2}$ be two distinct leaves of
$t$. The _first common ancestor_ of $\ell_{1}$ and $\ell_{2}$ is the internal
node of $t$ that is the furthest from the root and that belongs to the
shortest path from the root to $\ell_{1}$, and the shortest path from the root
to $\ell_{2}$.

The notations of the next definition are illustrated on Fig. 6.

######  Definition 5.2 (Induced subtree).

Let $(t,\mathfrak{I})$ be a marked tree in $\mathcal{T}_{0}$
($\mathcal{T}_{0}$ is defined in 2.9, and the notion of marked tree in 4.3).
The _induced subtree $t_{\mathfrak{I}}$_ of $t$ induced by $\mathfrak{I}$ is
defined as:

  * •

The leaves of $t_{\mathfrak{I}}$ are the leaves of $t$ that are marked. For
every such leaf labeled with an integer $\ell$, the new label of $\ell$ is
$\mathfrak{I}(\ell)$;

  * •

The internal nodes of $t_{\mathfrak{I}}$ are the internal nodes of $t$ that
are first common ancestors of two or more leaves of $t_{\mathfrak{I}}$;

  * •

The ancestor-descendent relation in $t_{\mathfrak{I}}$ is inherited from the
one in $t$;

  * •

For every internal node $\mathfrak{n}$ of $t$ that appears in
$t_{\mathfrak{I}}$, let $H$ be its decoration in $t$. Set

$J=\left\\{k;\ k\text{-th tree of $t_{\mathfrak{n}}$ contains a marked
leaf}\right\\}$

For $k$ in $J$, set

$\mathfrak{L}(k)=\min\left\\{\mathfrak{J}(\ell);\ \ell\ \text{marked leaf in
the}\ k\text{-th tree of $\mathfrak{L}(k)$}\right\\}.$

The decoration of $\mathfrak{n}$ in $t_{\mathfrak{I}}$ is the reduction of
$H_{\mathfrak{L}}$ as defined in 2.4.

For every internal node $\mathfrak{n}$ (resp. leaf $\ell)$ of
$t_{\mathfrak{I}}$, we also define $\phi(\mathfrak{n})$ to be the only
internal node (resp. leaf) of $t$ corresponding to $\mathfrak{n}$.

######  Remark.

When $(t,\mathfrak{I})$ is a marked tree and $t^{\prime}$ is a subtree of $t$,
we denote $t^{\prime}_{\mathfrak{I}}$ the tree induced by the restriction of
$\mathfrak{I}$ to the set of labels of leaves of $t^{\prime}$.

As a consequence of Definitions 2.4 and 5.2, we obtain:

######  Lemma 5.3.

Let $(t,\mathfrak{I})$ be a marked tree in $\mathcal{T}_{0}$. Then

$\mathrm{Graph}(t)_{\mathfrak{I}}=\mathrm{Graph}(t_{\mathfrak{I}}).$

Figure 6. Illustration of 5.3: relations between induced subgraph and induced
subtree. Figure 7. Two occurrences of a $P_{4}$ (line of size $4$) in a
blossomed graph $H$.

######  Definition 5.4.

For every graph $G$ without blossom, set:

$\displaystyle\mathrm{Occ}_{G,\mathcal{P}}(z):=\sum\limits_{H\in\mathcal{P}}\frac{\mathrm{Occ}_{G}(H)z^{|H|-|G|}}{|H|!}$

######  Proposition 5.5.

For every $k\geq 1$:

(20) $\displaystyle\sum\limits_{G:\
|G|=k}\mathrm{Occ}_{G,\mathcal{P}}(z)=P^{(k)}(z)$

Thus for every graph $G$, $\mathrm{Occ}_{G,\mathcal{P}}$, has a radius of
convergence strictly greater than $R$, the radius of convergence of $T$.

###### Proof.

Let $H$ be an element of $\mathcal{P}$. Since there are
$\frac{|H|!}{(|H|-k)!}$ choices of partial injection whose image is
$\\{1,\dots,k\\}$, we have:

$\sum\limits_{G:\
|G|=k}\mathrm{Occ}_{G,\mathcal{P}}(z)=\sum\limits_{H\in\mathcal{P}}\sum\limits_{G:\
|G|=k}\frac{\mathrm{Occ}_{G}(H)z^{|H|-k}}{|H|!}=\sum\limits_{H\in\mathcal{P}}\frac{z^{|H|-k}}{(|H|-k)!}=P^{(k)}(z)$

For every graph $G$, $\mathrm{Occ}_{G,\mathcal{P}}$ has nonnegative
coefficients and for every $k\geq 0$, as mentioned in Section 4.2, $P^{(k)}$
has a radius of convergence at least $R_{0}$, the radius of convergence of
$P$, which is greater than $R$. This implies that
$\mathrm{Occ}_{G,\mathcal{P}}$ has a radius of convergence greater than $R$.∎

###  5.2. Enumerations of trees with a given induced subtree

The key step in the proof of our main theorem is to compute the limiting
probability (when $n\to\infty$) that a uniform induced subtree of a uniform
tree in $\mathcal{T}_{\mathcal{P}}$ with $n$ leaves is a given substitution
tree.

In the following, let $\tau\in\mathcal{T}_{0}$ be a fixed substitution tree of
size at least $2$.

######  Definition 5.6.

We define _$\mathcal{T}_{\tau}$_ to be the set of marked trees
$(t,\mathfrak{I})$ where $t\in\mathcal{T}_{\mathcal{P}}$ and such that
$t_{\mathfrak{I}}$ is isomorphic to $\tau$. We also define $T_{\tau}$ to be
the corresponding exponential generating function (where the size parameter is
the total number of leaves, including the marked ones).

The aim now is to decompose a tree admitting $\tau$ as a subtree in smaller
trees. Let $(t,\mathfrak{I})$ be in $\mathcal{T}_{\tau}$, note that the image
of $\mathfrak{I}$ is $\\{1,\dots,|\tau|\\}$. A prime node $\mathfrak{n}$ of
$\tau$ is such that $\phi(\mathfrak{n})$ must be a prime node. In constrast,
knowing that an internal node $\mathfrak{n}^{\prime}$ of $\tau$ is decorated
with $\oplus$ or $\ominus$ does not give any information about the decoration
of $\phi(\mathfrak{n}^{\prime})$.

In order to state 5.8 below, we need to partition the internal nodes of
$\tau$:

######  Definition 5.7.

Let $(t,\mathfrak{I})$ be in $\mathcal{T}_{\tau}$. We denote by
$\mathcal{N}(t,\mathfrak{I})$ the set of internal nodes $\mathfrak{n}$ of
$\tau$ such that $\phi(\mathfrak{n})$ is non-linear.

Note that the set of non-linear nodes of $\tau$ must be included in
$\mathcal{N}(t,\mathfrak{I})$.

######  Theorem 5.8.

Let $\tau$ be a substitution tree of size at least $2$. Let $\mathfrak{N}$ be
a set of internal nodes of $\tau$ that contains every non-linear node of
$\tau$ and $\overline{\mathfrak{N}}$ the set of internal nodes of $\tau$ not
in $\mathfrak{N}$.

Let $\mathcal{T}_{\tau,\mathfrak{N}}$ be the set of marked trees
$(t,\mathfrak{I})$ in $\mathcal{T}_{\tau}$ such that
$\mathcal{N}(t,\mathfrak{I})=\mathfrak{N}$, and let $T_{\tau,\mathfrak{N}}$ be
its exponential generating function.

Then

(21) $\displaystyle T_{\tau,\mathfrak{N}}=z^{|\tau|}$ $\displaystyle
T^{\mathrm{root}}\left(T_{\mathrm{not}\oplus}^{\oplus}\right)^{d_{=}}\left(T_{\mathrm{not}\oplus}^{\ominus}\right)^{d_{\neq}}\left(T_{\mathrm{not}\oplus}^{\mathsf{blo}}\right)^{d_{\overline{\mathfrak{N}}\to\mathfrak{N}}}\left(T_{\mathrm{not}\oplus}^{{}^{\prime}}\right)^{d_{\overline{\mathfrak{N}}\to\ell}}\exp(n_{L}T_{\mathrm{not}\oplus})$
(22)
$\displaystyle\times(T^{\oplus})^{d_{\mathfrak{N}\to\overline{\mathfrak{N}}}}(T^{\mathsf{blo}})^{d_{\mathfrak{N}\to\mathfrak{N}}}(T^{\prime})^{d_{\mathfrak{N}\to\ell}}\prod\limits_{\mathfrak{n}\in\mathfrak{N}}\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(T)$

and:

  * •

$d_{=}$ is the number of edges between two internal nodes not in
$\mathfrak{N}$ with the same decoration ($\oplus$ and $\oplus$, or $\ominus$
and $\ominus$);

  * •

$d_{\neq}$ is the number of edges between two internal nodes not in
$\mathfrak{N}$ decorated with different decorations ($\oplus$ and $\ominus$);

  * •

$d_{\overline{\mathfrak{N}}\to\mathfrak{N}}$ is the number of edges between an
internal node not belonging to $\mathfrak{N}$ and one of its children
belonging to $\mathfrak{N}$;

  * •

$d_{\mathfrak{N}\to\overline{\mathfrak{N}}}$ is the number of edges between an
internal node belonging to $\mathfrak{N}$ and one of its children not
belonging to $\mathfrak{N}$;

  * •

$d_{\mathfrak{N}\to\mathfrak{N}}$ is the number of edges between an internal
node belonging to $\mathfrak{N}$ and one of its children belonging to
$\mathfrak{N}$;

  * •

$d_{\overline{\mathfrak{N}}\to\ell}$ is the number of edges between an
internal node not in $\mathfrak{N}$ and a leaf;

  * •

$d_{\mathfrak{N}\to\ell}$ is the number of edges between an internal node not
in $\mathfrak{N}$ and a leaf;

  * •

$n_{L}$ is the number of internal nodes not in $\mathfrak{N}$;

  * •

$\mathrm{dec}(\mathfrak{n})$ is the decoration of $\mathfrak{n}$;

  * •

$T^{\mathrm{root}}=T^{\oplus}$ if the root of $\tau$ is not in $\mathfrak{N}$,
$T^{\mathrm{root}}=T^{\mathsf{blo}}$ otherwise.

Figure 8. A substitution tree $\tau$. Vertices in $\mathfrak{N}$ are
surrounded in red. Figure 9. The decomposition of a tree admitting the graph
$\tau$ of Fig. 8 as an induced tree. Roman numerals correspond to the
different cases of the proof of 5.8.

###### Proof.

Let $t$ be a tree in $\mathcal{T}_{\tau,\mathfrak{N}}$. The proof consists in
decomposing $t$ into several disjoint (blossomed) subtrees
($t_{\to\mathrm{root}},t_{\mathfrak{n}\to},t_{\mathfrak{n}\to\mathfrak{n}^{\prime}},t_{\mathfrak{n}\to
f}$) of various kinds (those who arise in the RHS of formula Eq. 21). All
these subtrees are meant to be glued at blossoms, in order to recover the
initial $t$. (Thus they are not counted in the generating function, in order
to avoid counting them twice.) In the following, every defined tree is assumed
to be reduced.

  * •

We define $t_{\to\mathrm{root}}$ to be the tree $t$ blossomed at
$\phi(r_{0})$, where $r_{0}$ is the root of $\tau$.

  * •

For each internal node $\mathfrak{n}$, we define $t_{\mathfrak{n}\to}$ in the
following way:

    * –

If $\mathfrak{n}$ is not in $\mathfrak{N}$, $t_{\mathfrak{n}\to}$ is the
subtree of $t$ containing $\phi(\mathfrak{n})$ and all the trees of
$t_{\phi(\mathfrak{n})}$ that do not contain a marked leaf of $t$.

    * –

If $\mathfrak{n}$ is in $\mathfrak{N}$, $t_{\mathfrak{n}\to}$ is given by the
forest and the graph defined as follows (see Fig. 10):

      * *

The forest is composed of all subtree of $t_{\phi(\mathfrak{n})}$ which do not
contain any marked leaf;

      * *

The graph is $G$ the decoration of $\phi(\mathfrak{n})$, blossomed sucessively
at $v_{1},\dots,v_{k}$, where $v_{1},\dots,v_{k}$ are defined as follows. Let
$t_{\mathfrak{n},1},\dots,t_{\mathfrak{n},k}$ be the trees in
$t_{\mathfrak{n}}$ with a marked leaf, ordered by _minimal mark label_. For
each $j\in\\{1,\dots,k\\}$, we define $v_{j}$ the vertex in $G$ of label the
rank of $t_{\mathfrak{n},j}$ in $t_{\mathfrak{n}}$ _by minimal leaf label_.

  * •

For every internal nodes $\mathfrak{n},\mathfrak{n}^{\prime}$ in $\tau$ such
that $\mathfrak{n}^{\prime}$ is a child of $\mathfrak{n}$, let
$t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ be the unique tree of
$t_{\phi(\mathfrak{n})}$ containing $\phi(\mathfrak{n}^{\prime})$, blossomed
at $\phi(\mathfrak{n}^{\prime})$.

  * •

For every internal node $\mathfrak{n}$ in $\tau$, and every leaf $f$ which is
a child of $\mathfrak{n}$ in $\tau$, we define $t_{\mathfrak{n}\to f}$ to be
the tree of $t_{\phi(\mathfrak{n})}$ containing $\phi(f)$.

Figure 10. Example of the construction of $t_{n\to}$ when $n\in\mathfrak{N}$
(case (x)).

We now characterize the trees that appear in this decomposition and compute
the corresponding exponential generating function. In the rest of the proof,
we say abusively that every blossomed tree belongs to
$\mathcal{T}_{\mathcal{P}}$, and that two nodes both decorated with $\oplus$
or $\ominus$ have the same decoration, even if they do not have the same
number of children.

(i): analysis of $t_{\to\mathrm{root}}$

The tree $t_{\to\mathrm{root}}$ is a tree in $\mathcal{T}_{\mathcal{P}}$, it
has no marked leaf and a unique blossom. If the root is not in $\mathfrak{N}$
and decorated with $\oplus$ (resp. $\ominus$), the blossom is
$\oplus$-replaceable (see 4.4) (resp. $\ominus$-replaceable). If the root is
in $\mathfrak{N}$, the blossom is replaceable.

The corresponding exponential generating function is equal to $T^{\oplus}$ if
the root is not in $\mathfrak{N}$ and equal to $T^{\mathsf{blo}}$ otherwise.

(ii): analysis of $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ where
$\mathfrak{n}\not\in\mathfrak{N}$ and $\mathfrak{n}^{\prime}$ is a child of
$\mathfrak{n}$ not in $\mathfrak{N}$ with the same decoration

The tree $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ is a tree in
$\mathcal{T}_{\mathcal{P}}$ whose root is not decorated with the same
decoration as $\mathfrak{n}$ and with one blossom $\oplus$-replaceable if
$\mathfrak{n}^{\prime}$ is decorated with $\oplus$, $\ominus$-replaceable
otherwise and no marked leaf.

The exponential generating function of such trees is either
$T_{\mathrm{not}\oplus}^{\oplus}$ if both nodes are decorated with $\oplus$ or
$T_{\mathrm{not}\ominus}^{\ominus}$ ($=T_{\mathrm{not}\oplus}^{\oplus}$) if
both nodes are decorated with $\ominus$.

(iii): analysis of $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ where
$\mathfrak{n}\not\in\mathfrak{N}$ and $\mathfrak{n}^{\prime}$ is a child of
$\mathfrak{n}$ not in $\mathfrak{N}$ with a different decoration

The tree $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ is a tree in
$\mathcal{T}_{\mathcal{P}}$ whose root has a different decoration from that of
$\mathfrak{n}$ and with one blossom $\oplus$-replaceable if
$\mathfrak{n}^{\prime}$ is decorated with $\oplus$, $\ominus$-replaceable
otherwise and no marked leaf.

The exponential generating function of such trees is either
$T_{\mathrm{not}\oplus}^{\ominus}$ if $\mathfrak{n}$ is decorated with
$\oplus$ and $\mathfrak{n}^{\prime}$ with $\ominus$ or
$T_{\mathrm{not}\ominus}^{\oplus}$ ($=T_{\mathrm{not}\oplus}^{\ominus}$) if
$\mathfrak{n}$ is decorated with $\ominus$ and $\mathfrak{n}^{\prime}$ with
$\oplus$.

(iv): analysis of $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ where
$\mathfrak{n}\in\mathfrak{N}$ and $\mathfrak{n}^{\prime}$ is a child of
$\mathfrak{n}$ not in $\mathfrak{N}$

The tree $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ is a tree in
$\mathcal{T}_{\mathcal{P}}$ with one blossom $\oplus$-replaceable if
$v^{\prime}$ is decorated with $\oplus$, $\ominus$-replaceable otherwise and
no marked leaf.

The exponential generating function of such trees is either $T^{\oplus}$ if
$\mathfrak{n}^{\prime}$ is decorated with $\oplus$ or $T^{\ominus}$
($=T^{\oplus}$) if $\mathfrak{n}^{\prime}$ is decorated with $\ominus$.

(v): analysis of $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ where
$\mathfrak{n}\not\in\mathfrak{N}$ and $\mathfrak{n}^{\prime}$ is a child of
$\mathfrak{n}$ in $\mathfrak{N}$

The tree $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ is a tree in
$\mathcal{T}_{\mathcal{P}}$ whose root is not decorated with the decoration of
$\mathfrak{n}$ with one blossom and no marked leaf.

The corresponding exponential generating function is
$T_{\mathrm{not}\oplus}^{\mathsf{blo}}$.

(vi): analysis of $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ where
$\mathfrak{n}\in\mathfrak{N}$ and $\mathfrak{n}^{\prime}$ is a child of
$\mathfrak{n}$ in $\mathfrak{N}$

The tree $t_{\mathfrak{n}\to\mathfrak{n}^{\prime}}$ is a tree in
$\mathcal{T}_{\mathcal{P}}$ with one blossom and no marked leaf.

The corresponding exponential generating function is $T^{\mathsf{blo}}$.

(vii): analysis of $t_{\mathfrak{n}\to f}$ where
$\mathfrak{n}\not\in\mathfrak{N}$ and $f$ is a leaf which is a child of
$\mathfrak{n}$

The tree $t_{\mathfrak{n}\to f}$ is a tree in $\mathcal{T}_{\mathcal{P}}$
whose root is not decorated with the decoration of $\mathfrak{n}$ with one
marked leaf and no blossom.

The corresponding exponential generating function is
$zT_{\mathrm{not}\oplus}^{\prime}$.

(viii): analysis of $t_{\mathfrak{n}\to f}$ where
$\mathfrak{n}\in\mathfrak{N}$ and $f$ is a leaf which is a child of
$\mathfrak{n}$

The tree $t_{\mathfrak{n}\to f}$ is a tree in $\mathcal{T}_{\mathcal{P}}$ with
one marked leaf and no blossom.

The corresponding exponential generating function is $zT^{\prime}$.

(ix): analysis of $t_{\mathfrak{n}\to}$ where
$\mathfrak{n}\not\in\mathfrak{N}$

The tree $t_{\mathfrak{n}\to}$ is a tree whose root denoted is decorated with
the same decoration as $\mathfrak{n}$, who has no marked leaf and no blossom.
It verifies all the conditions of being $(\mathcal{P}$-consistent, except that
the root can have $0$ or $1$ child.

The corresponding exponential generating function is $\sum\limits_{k\geq
0}T_{\mathrm{not}\oplus}^{k}=\exp(T_{\mathrm{not}\oplus})$.

(x): analysis of $t_{\mathfrak{n}\to}$ where $\mathfrak{n}\in\mathfrak{N}$
This case is the more subtle one and the main reason we assume $\mathcal{P}$
to be stable by relabelling throughout the paper.

The tree $t_{\mathfrak{n}\to}$ is composed of a graph $G$ with $k$ blossoms,
and a forest of $|G|-|\mathrm{dec}(\mathfrak{n})|$ trees.

Let $n$ be an integer such that $n\geq|\mathrm{dec}(\mathfrak{n})|$. We need
to compute the cardinality of the set $B_{n}$ of all graphs $G$ of size $n$
that can be obtained in $t_{n\to}$. To that extent, we define
$A_{n,\mathrm{dec}(\mathfrak{n})}$ as the set of marked graphs
$(H,\mathfrak{J})$ such that $H$ is in $\mathcal{P}_{n}$ and the subgraph of
$H$ induced by $\mathfrak{J}$ is $\mathrm{dec}(\mathfrak{n})$.

Define the function $\phi:A_{n,\mathrm{dec}(\mathfrak{n})}\to B_{n}$ such that
$\phi(H,\mathfrak{J})$ is the graph with $k$ blossoms obtained after
blossoming successively $H$ at
$\mathfrak{J}^{-1}(1),\dots,\mathfrak{J}^{-1}(k)$. By construction $\phi$ is
well-defined and surjective.

Moreover, for every $G\in B_{n}$ , since $\mathcal{P}$ is stable by
relabelling, the size of $\phi^{-1}(G)$ is the same as the number of choices
of labels of the $k$ blossoms: $\frac{n!}{(n-|\mathrm{dec}(\mathfrak{n})|)!}$.

Thus for every $n\geq|\mathrm{dec}(\mathfrak{n})|$, the number of graphs in
$B_{n}$ is

$\frac{(n-|\mathrm{dec}(\mathfrak{n})|)!}{n!}|A_{n,\mathrm{dec}(\mathfrak{n})}|=\frac{(n-|\mathrm{dec}(\mathfrak{n})|)!}{n!}\sum\limits_{H^{\prime}\in\mathcal{P}_{n}}\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n})}(H^{\prime}).$

Since the generating function of the forest is
$\frac{T^{n-|\mathrm{dec}(\mathfrak{n})|}}{(n-|\mathrm{dec}(\mathfrak{n})|)!}$,
the corresponding generating function of $t_{\mathfrak{n}\to}$ is

$\sum\limits_{H^{\prime}\in\mathcal{P}}\frac{\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n})}(H^{\prime})T^{|H^{\prime}|-|\mathrm{dec}(\mathfrak{n})|}}{|H^{\prime}|!}=\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(T)$

Note that, with all these conditions, the process described in this proof is a
bijection between $\mathcal{T}_{\tau,\mathfrak{N}}$ and the labelled forest of
all previous mentioned trees (without doing reduction). Here is a reciprocal
to recover the original tree.

Simultaneously,

  * •

For every internal node $v$ of $\tau$ in $\mathfrak{N}$, we replace $t_{v\to}$
by a tree whose root is decorated with the graph of $t_{v\to}$ denoted by $G$,
and whose subtrees are composed of the forest in $t_{v\to}$ and all the
different trees of the form $t_{\mathfrak{n},\mathfrak{n}_{0}}$ and
$t_{\mathfrak{n}\to\ell}$. We change the labels of the blossoms of the
decoration such that for every $j$ such that $*_{j}$ is a blossom of the
decoration, the label $*_{j}$ is replaced by the rank of
$t_{\mathfrak{n}\to\mathfrak{n}_{j}}$ in the set of subtrees, where
$\mathfrak{n}_{j}$ is the $j$-th children of $\mathfrak{n}$ in $\tau$. The
other labels are replaced so that the decoration is labeled, and the order
between the previous and the new label stay the same;

  * •

For every internal node $\mathfrak{n}$ of $\tau$ not in $\mathfrak{N}$, we add
to the subtrees of the root of $t_{\mathfrak{n}\to}$ the different trees of
the form $t_{\mathfrak{n},\mathfrak{n}_{0}}$ and $t_{\mathfrak{n}\to\ell}$.

  * •

For every internal node, we replace the blossom of
$t_{\mathfrak{n}^{\prime}\to\mathfrak{n}}$ with $\mathfrak{n}^{\prime}$ the
parent of $v$ (resp. $t_{\to\mathrm{root}}$ if $\mathfrak{n}$ is the root of
$\tau$) by the tree $t_{\mathfrak{n}\to}$ after the previous modifications to
get a tree $t^{\prime}$. For every internal decoration of a node
$\mathfrak{n}_{0}$ blossomed at some
$t_{\mathfrak{n}^{\prime}\to\mathfrak{n}}$, we replace the decoration of the
blossom with the rank $r$ of the tree of $t^{\prime}_{\mathfrak{n}_{0}}$
containing $t_{\mathfrak{n}\to}$, and increase all the labels greater or equal
to $r$ by one.

After these operations, we recover the original tree.

Figure 11. Gluing of two trees.

Thus, $T_{\tau,\mathfrak{N}}$ is the product of the generating functions and
this concludes the proof of the theorem.

∎

######  Corollary 5.9.

With the notations of 5.8,

$\displaystyle T_{\tau,\mathfrak{N}}=z^{|\tau|}$ $\displaystyle
T^{\mathrm{root}}\left(T^{\oplus}\right)^{e}\exp((d_{\mathfrak{N}\to\ell}+d_{\mathfrak{N}\to\mathfrak{N}}+n_{L}-d_{=}-d_{\neq})T_{\mathrm{not}\oplus})\prod\limits_{\mathfrak{n}\in\mathfrak{N}}\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(T)$

where $e$ is the number of edges of $\tau$.

###### Proof.

Simple consequence of Eqs. 3, 4, 10, 11, 12, 8 and 9 and 5.8. ∎

######  Corollary 5.10.

Under Condition (C) defined p.Condition (C), the series
$T_{\tau,\mathfrak{N}}$ has radius of convergence $R$, is $\Delta$-analytic
and its asymptotic expansion near $R$ is:

$T_{\tau,\mathfrak{N}}=\frac{(1+K)}{\mu}C_{\tau,\mathfrak{N}}\left(1-\frac{z}{R}\right)^{-\frac{e+1}{2}}\left(1+o(1)\right)$

where

$C_{\tau,\mathfrak{N}}:=\frac{(1+K)^{f}R^{|\tau|}}{\mu^{e}}\times\prod\limits_{\mathfrak{n}\in\mathfrak{N}}\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)$

where $e$ is the number of edges of $\tau$, $f$ the number of edges between
two nodes $(n,n^{\prime})$ such that $n^{\prime}$ is a child of $n$ and $n$ is
in $\mathfrak{N}$ and $\mu$ and $K$ are defined by Eqs. 18 and 19.

###### Proof.

Note that by counting the edges $(\mathfrak{n},\mathfrak{n}^{\prime})$, where
$\mathfrak{n}^{\prime}$ is a child of $\mathfrak{n}$ and
$\mathfrak{n}^{\prime}$ is not in $\mathfrak{N}$
$n_{L}=d_{=}+d_{\neq}+d_{\mathfrak{N}\to\overline{\mathfrak{N}}}$ if the root
is in $\mathfrak{N}$,
$n_{L}=d_{=}+d_{\neq}+d_{\mathfrak{N}\to\overline{\mathfrak{N}}}+1$ otherwise.
Using this, the corollary is a simple consequence of 5.9 and Eq. 17. ∎

Summing over all choices of $\mathfrak{N}$ gives the following corollary

######  Corollary 5.11.

Under Condition (C) defined p.Condition (C), the series $T_{\tau}$ has radius
of convergence $R$, is $\Delta$-analytic and its asymptotic expansion near $R$
is:

$T_{\tau}=\frac{(1+K)}{\mu}B_{\tau}\left(1-\frac{z}{R}\right)^{-\frac{e+1}{2}}\left(1+o(1)\right)$

where

$B_{\tau}:=\frac{R^{|\tau|}}{\mu^{e}}\times\prod\limits_{\mathfrak{n}\in\mathfrak{N}_{\mathrm{nl}}}\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)\prod\limits_{\mathfrak{n}\in\mathfrak{N}_{\mathrm{l}}}\left(\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)(1+K)^{d_{\mathfrak{n}}}+1\right)$

where $e$ is the number of edges of $\tau$, $d_{\mathfrak{n}}$ the number of
children of $\mathfrak{n}$ for every internal node $v$,
$\mathfrak{N}_{\mathrm{nl}}$ is the set of non-linear nodes of $\tau$ and
$\mathfrak{N}_{\mathrm{l}}$ is the set of linear nodes of $\tau$.

##  6\. Main results

######  Theorem 6.1.

Let $\tau$ be a tree with $\ell\geq 2$ leaves. For $n\geq\ell$ and
$\mathbf{T}^{(n)}$ be a uniform random tree in $\mathcal{T}_{\mathcal{P}}$
with $n$ vertices. Let $\mathbf{\mathfrak{I}_{\ell}}^{(n)}$ be a uniform
partial injection from $\\{1,\dots,n\\}$ to $\mathbb{N}$ whose image is
$\\{1,\dots,\ell\\}$ and independent of $\mathbf{T}^{(n)}$. Denote by
$\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}$ the subtree induced by
$\mathbf{\mathfrak{I}_{\ell}}^{(n)}$. Assume that Condition (C) defined
p.Condition (C) holds.

If $\tau$ is a binary tree then

$\mathbb{P}(\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}=\tau)\xrightarrow[n\to\infty]{}\frac{(\ell-1)!}{(2(\ell-1))!}2^{\ell-1}p^{\mathfrak{N}_{+}}(1-p)^{\mathfrak{N}_{-}}$

where $\mathfrak{N}_{+}$ (resp. $\mathfrak{N}_{-}$) is the number of internal
nodes of $\tau$ decorated with $\oplus$ (resp. $\ominus$) and

(23) $\displaystyle p$
$\displaystyle=\frac{1+(1+K)^{2}\mathrm{Occ}_{\oplus_{2},\mathcal{P}}(K)}{\Lambda^{\prime\prime}(\kappa)}$

where $\oplus_{2}$ (resp. $\ominus_{2}$) is the graph with $2$ vertices and
$1$ (resp. $0$) edge.

If on the contrary $\tau$ is not binary then

$\mathbb{P}(\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}=\tau)\xrightarrow[n\to\infty]{}0$

###### Proof.

Since $\mathbf{\mathfrak{I}_{\ell}}^{(n)}$ is independent of
$\mathbf{T}^{(n)}$,

$\mathbb{P}(\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}=\tau)=\frac{n![z^{n}]T_{\tau}}{n(n-1)\dots(n-\ell+1)n![z^{n}]T}=\frac{[z^{n}]T_{\tau}}{n(n-1)\dots(n-\ell+1)[z^{n}]T}$

By applying the Transfer Theorem [11, Corollary VI.1 p.392] to 5.10, we get

$[z^{n}]T_{\tau}\sim\frac{(1+K)}{\mu}B_{\tau}\frac{n^{\frac{e-1}{2}}}{\Gamma\left(\frac{e+1}{2}\right)R^{n}}$

and by 4.12 we obtain

$n\times\cdots\times(n-\ell+1)[z^{n}]T\sim
n^{\ell}\frac{(1+K)R}{\sqrt{\pi}\mu}\frac{1}{R^{n}n^{\frac{3}{2}}}.$

Thus when $n$ goes to infinity

$\mathbb{P}(\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}=\tau)\sim\frac{B_{\tau}\sqrt{\pi}}{R\Gamma\left(\frac{e+1}{2}\right)}n^{\frac{e+2}{2}-\ell}.$

Hence if $\tau$ is not a binary tree,
$\mathbb{P}(\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}=\tau)\xrightarrow[n\to\infty]{}0.$

Assume that $\tau$ is a binary tree. Since here $e=2\ell-2$, we get when $n$
goes to infinity

$\mathbb{P}(\mathbf{T}_{\mathbf{\mathfrak{I}_{\ell}}^{(n)}}^{(n)}=\tau)\to\frac{\sqrt{\pi}B_{\tau}}{R\Gamma\left(\frac{2\ell-1}{2}\right)}=\frac{(\ell-1)!}{(2(\ell-1))!}\frac{2^{2\ell-2}B_{\tau}}{R}$

Since a binary tree with $\ell$ leaves has $\ell-1$ internal nodes, we have:

$\displaystyle\frac{2^{2\ell-2}B_{\tau}}{R}$
$\displaystyle\frac{2^{2\ell-2}R^{\ell-1}}{(2R\Lambda^{\prime\prime}(\kappa))^{\ell-1}}\prod\limits_{\mathfrak{n}\in\mathfrak{N}_{\mathrm{l}}}\left(\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)(1+K)^{d_{\mathfrak{n}}}+1\right)$
$\displaystyle=\frac{2^{\ell-1}}{(\Lambda^{\prime\prime}(\kappa))^{\ell-1}}\left(1+(1+K)^{2}\mathrm{Occ}_{\oplus_{2},\mathcal{P}}(K)\right)^{\mathfrak{N}_{+}}\left(1+(1+K)^{2}\mathrm{Occ}_{\ominus_{2},\mathcal{P}}(K)\right)^{\mathfrak{N}_{-}}$
$\displaystyle=2^{\ell-1}\left(\frac{1+(1+K)^{2}\mathrm{Occ}_{\oplus_{2},\mathcal{P}}(K)}{\Lambda^{\prime\prime}(\kappa)}\right)^{\mathfrak{N}_{+}}\left(\frac{1+(1+K)^{2}\mathrm{Occ}_{\ominus_{2},\mathcal{P}}(K)}{\Lambda^{\prime\prime}(\kappa)}\right)^{\mathfrak{N}_{-}}$
$\displaystyle=2^{\ell-1}p^{\mathfrak{N}_{+}}(1-p)^{\mathfrak{N}_{-}}.$

Last equality holds because

$\displaystyle\frac{1+(1+K)^{2}\mathrm{Occ}_{\oplus_{2},\mathcal{P}}(K)}{\Lambda^{\prime\prime}(\kappa)}+\frac{1+(1+K)^{2}\mathrm{Occ}_{\ominus_{2},\mathcal{P}}(K)}{\Lambda^{\prime\prime}(\kappa)}$
$\displaystyle=\frac{2+(1+K)^{2}\sum\limits_{G\in\mathcal{P}}\frac{|G|(|G|-1)z^{|G|-2}}{|G|!}}{\Lambda^{\prime\prime}(\kappa)}$
$\displaystyle=\frac{2+(1+K)^{2}P^{\prime\prime}(K)}{\Lambda^{\prime\prime}(\kappa)}=1$

since

$\displaystyle\Lambda^{\prime\prime}(\kappa)$
$\displaystyle=\exp(\kappa)^{2}P^{\prime\prime}(\exp(\kappa)-1)+\exp(\kappa)+P^{\prime}(\exp(\kappa)-1)+\exp(\kappa)$
$\displaystyle=(1+K)^{2}P^{\prime\prime}(K)+1+\Lambda^{\prime}(\kappa)=2+(1+K)^{2}P^{\prime\prime}(K).$

Combining all the previous equality gives the announced result.

∎

1.2 is a corollary of 6.1 and 3.4.

######  Theorem 6.2.

Let $H$ be a graph. For $n\geq|H|$, let $\mathbf{G}^{(n)}$ be a uniform random
graph in $\mathcal{G}_{\mathcal{P}}$ with $n$ vertices. Let
$(d_{1},\dots,d_{k})$ be the degrees of the linear nodes of the modular
decomposition tree of $H$.

Then under Condition (C) defined p.Condition (C)

$\mathbb{E}[\mathrm{Occ}_{H}(\mathbf{G}^{(n)})]\sim K_{H}n^{|H|-\beta(H)}$

where $\beta(H)$ is defined in Eq. 1 and with

$K_{H}=\frac{\sqrt{\pi}\prod\limits_{i=1}^{k}(2d_{i}-3)!!}{2^{|H|-1-\beta(H)}\Gamma\left(\frac{2|H|-1-2\beta(H)}{2}\right)}\left(\prod\limits_{\mathfrak{n}\in\mathfrak{N}_{\mathrm{nl}}}\frac{\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)R^{|\mathrm{dec}(\mathfrak{n})|-2}}{\Lambda^{\prime\prime}(\kappa)^{\mathrm{dec}(\mathfrak{n})/2}}\right)p^{d_{\oplus}-n_{\oplus}}(1-p)^{d_{\ominus}-n_{\ominus}}$

where $d_{1},\dots,d_{k}$ are the number of children of every linear node in
the modular decomposition tree of $H$, $n_{\oplus}$ (resp. $n_{\ominus}$) is
the number of internal node decorated with $\oplus$ (resp. $\ominus$) in the
modular decomposition tree of $H$, and $d_{\oplus}$ (resp. $d_{\ominus}$) is
the sum of the number of children of internal nodes decorated with $\oplus$
(resp. $\ominus$) in the modular decomposition tree of $H$.

###### Proof.

Let $\mathcal{T}_{H}$ be the set of substitution tree $t$ such that
$\mathrm{Graph}(t)=H$. Note that

$\mathbb{E}[\mathrm{Occ}_{H}(\mathbf{G}^{(n)})]=\frac{n![z^{n}]\sum\limits_{\tau\in\mathcal{T}_{H}}T_{\tau}}{n![z^{n}]T}$

Following the proof of 6.1, for every $\tau\in\mathcal{T}_{H}$,

$\frac{[z^{n}]T_{\tau}}{[z^{n}]T}\sim\frac{B_{\tau}\sqrt{\pi}}{R\
\Gamma\left(\frac{e+1}{2}\right)}n^{\frac{e+2}{2}}.$

Using the previous asymptotic, it yields that in the expansion of
$\mathbb{E}[\mathrm{Occ}_{H}(\mathbf{G}^{(n)})]$, only the terms corresponding
to an expanded tree in $\mathcal{T}_{H}$. Thus by 2.20

$\displaystyle\mathbb{E}[\mathrm{Occ}_{H}(\mathbf{G}^{(n)})]$
$\displaystyle\sim\frac{R^{|H|}\sqrt{\pi}\prod\limits_{i=1}^{k}(2d_{i}-3)!!}{R\mu^{2|H|-2-2\beta(H)}\Gamma\left(\frac{2|H|-1-2\beta(H)}{2}\right)}\prod\limits_{\mathfrak{n}\in\mathfrak{N}_{\mathrm{nl}}}\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)$
$\displaystyle\quad\times\prod\limits_{\mathfrak{n}\in\mathfrak{N}_{\mathrm{l}}}\left(\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)(1+K)^{2}+1\right)n^{|H|-\beta(H)}$

Using the explicit expression of $\mu$, and the fact that in an expanded tree,
every linear node of size $k$ is replaced with a binary tree with $k-1$ binary
node with the same decoration, we get

$\mathbb{E}[\mathrm{Occ}_{H}(\mathbf{G}^{(n)})]\sim K_{H}n^{|H|-\beta(H)}$

with

$K_{H}=\frac{\sqrt{\pi}\prod\limits_{i=1}^{k}(2d_{i}-3)!!}{2^{|H|-1-\beta(H)}\Gamma\left(\frac{2|H|-1-2\beta(H)}{2}\right)}\left(\prod\limits_{\mathfrak{n}\in\mathfrak{N}_{\mathrm{nl}}}\frac{\mathrm{Occ}_{\mathrm{dec}(\mathfrak{n}),\mathcal{P}}(K)R^{|\mathrm{dec}(\mathfrak{n})|-2}}{\Lambda^{\prime\prime}(\kappa)^{\mathrm{dec}(\mathfrak{n})/2}}\right)p^{d_{\oplus}-n_{\oplus}}(1-p)^{d_{\ominus}-n_{\ominus}}.$

∎

Acknowledgements. I would like to thank Lucas Gerin and Frédérique Bassino for
useful discussions and for carefully reading many earlier versions of this
manuscript.

## References

  * [1] L. Addario-Berry, N. Broutin, and C. Goldschmidt.  The continuum limit of critical random graphs.  Probab. Theory Relat. Fields, 152:367–406, 2009.
  * [2] D. Aldous.  The Continuum Random Tree III.  Ann. Probab., 21(1):248 – 289, 1993.
  * [3] D. Aldous.  On the largest common subtree of random leaf-labeled binary trees.  SIAM J. Discrete Math., 36(1):299–314, 2022.
  * [4] F. Bassino, M. Bouvel, M. Drmota, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot.  Linear-sized independent sets in random cographs and increasing subsequences in separable permutations.  Comb. Theory, 2(3):#15, 2022.
  * [5] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot.  Random cographs: Brownian graphon limit and asymptotic degree distribution.  Random Struct. Algorithms, 60(2):166–200, 2022.
  * [6] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot.  Universal limits of substitution-closed permutation classes.  J. of the Eur. Math. Soc., 22(11):3565–3630, 2020.
  * [7] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi.  Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing.  Adv. Math., 219(6):1801–1851, 2008.
  * [8] A. Brandstädt, V. B. Le, and J. P. Spinrad.  Graph Classes: A Survey.  Society for Industrial and Applied Mathematics, 1999.
  * [9] A. Cournier and M. Habib.  A new linear algorithm for modular decomposition.  Trees in Algebra and Programming – CAAP’94, pages 68–84, 1994\.
  * [10] P. Diaconis and S. Janson.  Graph limits and exchangeable random graphs.  Rendiconti di Matematica, 28(1):33–61, 2008.
  * [11] P. Flajolet and R. Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [12] T. Gallai.  Transitiv orientierbare graphen.  Acta Mathematica Academiae Scientiarum Hungarica, 18:25–66, 1967\.
  * [13] M. Habib and C. Paul.  A survey of the algorithmic aspects of modular decomposition.  Computer Science Review, 4(1):41–59, 2010.
  * [14] H. Hatami, S. Janson, and B. Szegedy.  Graph properties, graph limits and entropy.  Journal of Graph Theory, 87, 12 2013.
  * [15] R. van der Hofstad.  Random Graphs and Complex Networks.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016.
  * [16] T. Lenoir.  Graph classes with few $P_{4}$’s: Universality and Brownian graphon limits, 2023.  Preprint arXiv:2301.13607.
  * [17] L. Lovász.  Large Networks and Graph Limits.  Colloquium Publications. American Mathematical Society, 2012.
  * [18] R. H. Möhring.  Algorithmic Aspects of Comparability Graphs and Interval Graphs, pages 41–101.  Springer, 1985.
  * [19] K. Panagiotou, B. Stufler, and K. Weller.  Scaling limits of random graphs from subcritical classes.  Ann. Probab., 44(5):3291–3334, 2016.
  * [20] B. Stufler.  Graphon convergence of random cographs.  Random Struct. Algorithms, 59:464 – 491, 2021.

Théo Lenoir<EMAIL_ADDRESS>
Cmap, Cnrs, École polytechnique,
Institut Polytechnique de Paris,
91120 Palaiseau, France