# Exact-size Sampling of Enriched Trees in Linear Time

Konstantinos Panagiotou<EMAIL_ADDRESS>,  Leon Ramzews
<EMAIL_ADDRESS>and  Benedikt Stufler  Institute for Discrete Mathematics
and Geometry, Technische Universität Wien<EMAIL_ADDRESS>
(Date: August 29, 2024)

###### Abstract.

Various combinatorial classes such as outerplanar graphs and maps, series-
parallel graphs, substitution-closed classes of permutations and many more
allow bijective encodings by so-called _enriched trees_ , which are rooted
trees with additional structure on the offspring of each node. Using this
universal description we develop sampling procedures that uniformly generate
objects from this classes with a given size $n$ in expected time $O(n)$. The
key ingredient is a representation of enriched trees in terms of decorated
Bienaymé–Galton–Watson trees, which allows us to develop a novel combination
of Devroye’s efficient sampler for trees [21] with Boltzmann sampling
techniques. Additionally, we construct expected linear time samplers for
critical Bienaymé–Galton–Watson trees having exactly $n$ (out of $\geq n$
total) nodes with outdegree in some fixed set, enabling uniform generation for
many combinatorial classes such as dissections of polygons.

Konstantinos Panagiotou receives funding from the European Research Council,
ERC Grant Agreement 772606-PTRCSP. Leon Ramzews receives funding by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), Project PA
2080/3-1.

##  1\. Introduction and Main Results

Suppose that we are given a combinatorial class $\mathcal{C}$, that is, a
countable set equipped with a size function
$\lvert\cdot\rvert:\mathcal{C}\to\mathbb{N}_{0}$ such that
$\mathcal{C}_{n}:=\\{C\in\mathcal{C}:\lvert C\rvert=n\\}$ is finite for all
$n\in\mathbb{N}_{0}$. A _sampler_ for $\mathcal{C}$ is a sequence of
instructions involving random decisions that construct an element
$\mathsf{C}\in\mathcal{C}$ following some given probability distribution. The
development of efficient samplers, or equivalently, the efficient random
generation of combinatorial objects, is an active and prominent research area
with widespread applications. There is a plethora of results and techniques,
many of which address specific problems and develop ad hoc methods, and others
that create universal techniques that are applicable in various situations.

Let us start right away with an important case that is very well understood
and also directly relevant to the results that will be derived here. Let $\xi$
be a random non-negative integer. We create a tree $\mathsf{T}$ by starting
with a single vertex and attaching to it a random number of vertices/children
distributed like $\xi$. Subsequently, we repeat this procedure for every newly
created vertex, using independent copies of $\xi$ to determine the number of
their children. The resulting tree is the well-known _Bienaymé–Galton–Watson_
tree with offspring distribution $\xi$, and by conditioning $\mathsf{T}$ to
have $n$ vertices we obtain a simply generated tree $\mathsf{T}_{n}$. For
example, if we choose $\xi$ to be a Poisson distribution, then the
distribution of $\mathsf{T}_{n}$ (after distributing labels to vertices
uniformly at random) is the uniform distribution on the class of all rooted
Cayley trees with $n$ vertices. Improving earlier results addressing special
cases or having a longer running time, Devroye presented in [21] a general
algorithm for sampling $\mathsf{T}_{n}$ that runs in expected linear time when
$\mathbb{E}[\xi]=1$ and $\xi$ has finite variance. So, this fundamental case
is from today’s viewpoint very well understood.

Probably the first systematic approach that applies to a broader setting is
the _recursive method_ by Nijenhuis and Wilf [34] that can be applied to
combinatorial structures defined by specific recursive decompositions. The
original method, although quite broad in applicability, was rather inefficient
and thus was developed further and improved in several works [28, 19], where
eventually samplers with almost linear average time and space complexity were
developed. However, all these results are limited to classes that do not allow
in general the powerful operation of _substitution_ , that is, constructions
in which atoms (like vertices or edges in a graph) are replaced by other
objects; this limits the applicability of the method to only moderately
complex combinatorial classes. Moreover, all variants of the recursive method
require (at least) quadratic preprocessing time.

The recursive method is best suited for _exact-size_ sampling, where we fix,
for example, the size of the object that we want to sample in advance. This
paradigm was relaxed in the seminal paper by Duchon, Flajolet, Louchard and
Schaeffer [24], allowing samplers to generate objects with varying target size
that may be distributed over the whole of $\mathbb{N}$. The so-called
_Boltzmann sampling_ paradigm developed in that paper is inspired from methods
in Physics and postulates to generate objects from the entire class
$\mathcal{C}$ with probability proportional to $x^{\lvert C\rvert}/\lvert
C\rvert!$ for $C\in\mathcal{C}$, where $x>0$ is a predefined control
parameter. Boltzmann samplers have many advantages: their complexity is (for
combinatorial specifications) linear in the size of the generated object, in
many cases we have good control of the output size by tuning $x$, and their
description is simple and intuitive. For all these reasons the paper [24]
ignited a whole new line of research, where substantial extensions and
improvements were proposed, including the celebrated approximate-size linear
time sampler for planar graphs [29], substantial Pólya-Boltzmann extensions
for unlabelled structures [26, 12], multi-parametric samplers [10, 5] enabling
the control of several parameters simultaneously, numerical procedures for
approximating the values of the generating functions [38] and many more [8, 9,
11]. The Boltzmann framework enables us to perform exact-size sampling by
rejection (discard objects until the target size is met) and truncation (stop
sampling as soon as the objects become too large). In particular, exact-size
sampling is possible in expected quadratic time whenever the counting sequence
for $(|\mathcal{C}_{n}|)_{n\in\mathbb{N}}$ satisfies certain properties, for
example if $|\mathcal{C}_{n}|=\Theta(n^{-a}\gamma^{n}n!)$ for some $a\in(1,2)$
and $\gamma>0$, see the so-called ’singular samplers’ in [24]. The Boltzmann
framework also enables sampling in this setting with a target size interval of
the form $[(1-\epsilon)n,(1+\epsilon)n]$ in expected time $O(n/\epsilon)$ for
fixed but arbitrary $\epsilon>0$. However, this so-called approximate size
sampling may introduce unpredictable error terms when performing simulations,
so there is significant added value in performing efficient exact-size
sampling.

In this article we combine the world of Devroye – linear time sampling of
conditioned Bienaymé–Galton–Watson trees – with the world of Boltzmann
sampling to assemble efficient linear time and exact-size samplers that are
applicable to a broader spectrum of combinatorial classes. Concretely, the
classes that we can treat follow a unified representation in terms of
_enriched trees_ [36, 43]. Before giving a formal definition later, let us
mention a few concrete examples that fall within our scope.

######  Example 1.1.

Our approach allows us to treat in a unified setting the following
classes:111Implementations for exact-size samplers of selected classes such as
outerplanar graphs are available on github:
https://github.com/BenediktStufler/

  1. (1)

subcritical graph classes, including connected series-parallel, outerplanar
and cactus graphs;

  2. (2)

Bienaymé–Galton–Watson trees conditioned on the number of vertices whose
degree lies in a given set and otherwise no restriction on the size;

  3. (3)

families of outerplanar maps;

  4. (4)

certain subcritical substitution-closed classes of permutations;

  5. (5)

cographs (with expected runtime being linear in the output size);

  6. (6)

level-$k$ phylogenetic networks.

Let us describe at this point exemplary for the case of series-parallel (SP)
graphs what the main obstacles in the development of efficient and exact-size
samplers are. First of all, the good news is that these objects can be put in
some specific way in bijection to a class of trees; this follows from the
general decomposition of connected graphs in parts of higher connectivity
[17]. On the other hand, these trees are not simply-generated – in fact, they
are _multi-type_ Bienaymé–Galton–Watson trees – and thus Devroye’s sampler is
not applicable. Moreover, the combinatorial specification of 2-connected SP
graphs, which play a central role in the specification of connected SP graphs,
contains the operation of _difference_ of classes (see also Section 5.1, where
we treat this specific example). This is a significant obstacle causing
problems on various levels of the analysis, as it introduces a ’$-$’-sign on
the level of the specification. A further problem that also appears (more
prominently) in other examples is that sampling from the specification is only
the first step: in order to obtain the desired object we further have to apply
a bijection. The time required to do so must be taken into account as well.

The approach taken in this work makes it possible to develop expected linear-
time exact-size samplers for the classes in Example 1.1 by addressing all of
the aforementioned problems. Very roughly speaking, the problem of the
appearance of multi-type trees is addressed by studying the class of enriched
trees, that puts us in a position to spot an adequate underlying ’simply-
generated’ tree. Moreover, the Boltzmann sampling component that we include
allows us to solve the problem of the difference of sets by rejection in a
rather straightforward way. Finally, we account explicitly in all examples for
the cost of realizing the underlying bijections.

One consequence of our main result is the development of new or the
improvement of all (with the notable exception of outerplanar maps [14])
existing samplers for the classes in Example 1.1. For instance, prior to this
work, the state-of-the-art samplers for series-parallel, outerplanar and
cactus graphs run in expected time $O(n^{2})$ and are based on Boltzmann
sampling, as the number of such graphs of size $n$ is
$\Theta(n^{-3/2}\gamma^{n}n!)$ for some $\gamma>0$. See [13] and [2].
Moreover, the sampler for 3. in the examples can be used to sample from
classes that are in bijection to these objects, for example dissections of
polygons. Finally, in [4], among other results, a superlinear uniform sampler
for substitution-closed classes of permutations with a finite number of
excluded patterns is presented. Here we will show how to sample from these
classes in (optimal) linear time as a consequence of a more general result.

As a last remark let us mention that parallel to this work and by using
completely different techniques, Sportiello developed in [41] a rather
different method for sampling from irreducible context-free combinatorial
structures. His approach solves the problem of exact-size sampling from multi-
type Bienaymé–Galton–Watson trees and thus addresses in a different and
complementary way some of the problems that are also tackled here. Moreover,
the approach presented there only makes it possible to sample from classes
related to SP graphs, for example SP networks (or two-terminal SP graphs).

###  1.1. Main result: linear-time sampling of enriched trees

When measuring the running time or the complexity of an algorithm we always
assume that we operate under the so-called _RAM model of computation_. This is
a widely used approach, followed also in Devroye’s paper [21], to establish
complexity results that are independent of the actual machine on which the
algorithm is executed. In this model we assume that we operate a hypothetical
computer called the _Random Access Machine_ under the following conditions,
see for example [40, Ch. 2]:

  1. (1)

Basic logical and arithmetic operators like $\\{if,call\\}$ and
$\\{+,-,\times,\div\\}$ take one time step.

  2. (2)

Loops and subroutines are not basic operators and count as the composition of
many single-step operators.

  3. (3)

Each memory access takes exactly one step.

  4. (4)

A number drawn uniformly at random from $[0,1]$ can be generated in one step.

In particular, in this model real numbers can be stored without loss of
precision. Let us mention at this point that it is an important question and a
significant challenge to develop and analyse algorithms that operate
efficiently under other models of computation, for example on a Word RAM with
random bits or on a Turing machine; to our knowledge, this is already an open
problem for the case considered by Devroye [21].

In the setting considered here we can already formulate a first consequence of
our main result, which, among other things, says that we develop linear-time
algorithms for sampling series-parallel and outerplanar graphs, as well as
permutations from specific substitution-closed classes and trees with a given
number of leaves.

######  Theorem 1.2.

Under the RAM model of computation, the samplers in Section 5 produce objects
of size $n$ uniformly at random in expected time $O(n)$ for all the classes in
Example 1.1.

Towards the proof of Theorem 1.2 we will switch somehow our point of view and
look at combinatorial classes as special cases of so-called ’enriched trees’.
Generally speaking, the enriched tree viewpoint emphasizes that Galton–Watson
trees take a special place among random recursive structures. Specifically, we
may sample a random recursive structure by sampling a size-constrained
Galton–Watson tree and adding local random ’decorations’ later. All classes
listed in Example 1.1 are well-known to admit encodings of this form.

Before we continue let us fix some notation. Let $\mathcal{C}$ be a
combinatorial class. We (always) consider the labelled setting, meaning that
all atoms composing an object of size $n$ bear distinct labels, typically in
the set $[n]:=\\{1,\dots,n\\}$. Any other finite set of labels $U$ with
$\lvert U\rvert=n$ is also admissible; then we write $\mathcal{C}[U]$ to
emphasize that we consider objects with labels in $U$.

With this notation at hand we may describe the main class of objects that we
shall study. Given a combinatorial class $\mathcal{R}$, the class
$\mathcal{A}_{\mathcal{R}}$ of $\mathcal{R}$-enriched trees may informally be
described as the class containing all rooted labelled unordered trees, where
in addition the offspring set of each vertex is decorated with an object from
$\mathcal{R}$. More formally, let us denote by $\mathcal{A}$ the class of
rooted Cayley trees, i.e., rooted labelled unordered acyclic connected graphs.
We (slightly) abuse notation and write $v\in T$ to denote that $v$ is a vertex
of $T\in\mathcal{A}$. Let $P_{v}$ be the label set of the offspring of $v$,
where by ’offspring’ we define the set of nodes that are connected to $v$ and
are at the same time farther away from the root than $v$. We further define
the outdegree $d_{T}^{+}(v)$ to be $\lvert P_{v}\rvert$. Then
$\mathcal{A}_{\mathcal{R}}$ contains all sequences of the form

$(T,(R_{v})_{v\in T}),\quad T\in\mathcal{A}\leavevmode\nobreak\ \text{ and
}\leavevmode\nobreak\ R_{v}\in\mathcal{R}[P_{v}]\text{ for all }v\in T,$

where the size of an $\mathcal{R}$-enriched tree $A=(T,(R_{v})_{v\in T})$ is
defined as $\lvert A\rvert=\lvert T\rvert=\sum_{v\in T}\lvert R_{v}\rvert+1$.
In light of this definition and in order to avoid trivial cases we assume that
$|\mathcal{R}_{0}|>0$ (otherwise $\mathcal{A}_{\mathcal{R}}$ is empty) and
$|\mathcal{R}_{k}|>0$ for some $k\geq 2$ (otherwise
$\mathcal{A}_{\mathcal{R}}$ is equivalent to a collection of paths), see also
Condition (A) in Definition 1.3 below.

Let us write in the sequel $r_{k}:=\lvert\mathcal{R}_{k}\rvert$ for
$k\in\mathbb{N}_{0}$ and define the generating functions

$\mathcal{R}(x):=\sum_{k\in\mathbb{N}_{0}}\frac{r_{k}}{k!}x^{k}\quad\text{and}\quad\mathcal{A}_{\mathcal{R}}(x):=\sum_{k\in\mathbb{N}}\frac{|\mathcal{A}_{\mathcal{R}}[[k]]|}{k!}x^{k}.$

The two functions are related by the important equation

(1.1)
$\mathcal{A}_{\mathcal{R}}(x)=x\mathcal{R}(\mathcal{A}_{\mathcal{R}}(x)),$

see also Section 3, where we present more related facts about
$\mathcal{R}$-enriched trees. Let $\rho_{\mathcal{R}}$ and
$\rho_{\mathcal{A}_{\mathcal{R}}}$ be the radii of convergence of
$\mathcal{R}(x)$ and $\mathcal{A}_{\mathcal{R}}(x)$, respectively. It is
rather well-known that Equation (1.1) and the aforementioned assumptions
$r_{0}>0$ and $r_{k}>0$ for at least one $k\geq 2$ entail that
$\rho_{\mathcal{A}_{\mathcal{R}}}$,
$\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})$, and
$\mathcal{R}(\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}}))$ are
finite, see Lemma 4.1 and for more background Section 3.2.

The previous considerations imply that
$\mathcal{R}(\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}}))\geq
r_{0}>0$ and thus enable us to define a random variable $\xi$ with
distribution

(1.2) $\displaystyle
p_{k}:=\mathbb{P}(\xi=k):=\frac{r_{k}\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})^{k}}{\mathcal{R}(\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}}))k!},\qquad
k\in\mathbb{N}_{0}.$

We will also need the Boltzmann random variable $\Gamma\mathcal{R}(t)$ for
$0<t<\rho_{\mathcal{R}}$ given by

$\mathbb{P}(\Gamma\mathcal{R}(t)=R)=\frac{t^{|R|}}{\mathcal{R}(t)\,|R|!},\quad
R\in\mathcal{R}.$

We now come to the most crucial part, namely the assumptions that we make for
the class of enriched trees that we consider.

######  Definition 1.3.

We call a class of enriches trees _tame_ if it has the following properties:

  1. (A)

’Non-triviality’: $r_{0}>0$ and there exists $k\geq 2$ with $r_{k}>0$.

  2. (B)

’Subcriticality’:
$\rho_{\mathcal{R}}>\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})$.

  3. (C)

’Computability’: $\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})$
and $\mathcal{R}(\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}}))$
are given, and $p_{k}$ can be computed in $\mathrm{e}^{o(k)}$ steps for
$k\in\mathbb{N}_{0}$.

  4. (D)

’Boltzmann sampler for $\mathcal{R}$’: For any $0<t<\rho_{\mathcal{R}}$ there
exists a sampling procedure for $\Gamma\mathcal{R}(t)$ running in expected
constant time.

As we will see, the most critical and essential property is Assumption (B),
which ensures together with well-known results by Janson [31] that $p_{k}$ has
exponential tails. Moreover, note that under the RAM model of computation the
determination of
$\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})^{k}/k!$ takes
$O(k)$ steps, so that (C) actually means that we need to be able to compute
$r_{k}$ (which is in $\mathbb{N}_{0}$) in $\mathrm{e}^{o(k)}$ steps. This is
usually no severe restriction, as most of the classes we consider have some
kind of combinatorial decomposition, allowing us to use the aforementioned
recursive method [34] to compute $r_{k}$ in $k^{O(1)}$ time. Further,
$\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})$ and
$\mathcal{R}(\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}}))$
being given means that we are able to compute these values beforehand.
Finally, (D) is a rather mild condition, since $t<\rho_{\mathcal{R}}$ and thus
all moments of $\Gamma\mathcal{R}(t)$ exist; such samplers can (usually) be
designed from the general principles developed in [24, 12].

A crucial ingredient in the proof of Theorem 1.2 is the following fact on
which we elaborate in Section 5.

######  Fact 1.4.

For every combinatorial class $\mathcal{C}$ given in Example 1.1 there exists
$\mathcal{R}$ such that the class $\mathcal{C}$ corresponds to the class of
enriched trees $\mathcal{A}_{\mathcal{R}}$, where $\mathcal{A}_{\mathcal{R}}$
is tame.

In Section 2 we present the backbone of our main result, namely a sampler
generating an instance of the random object $\mathsf{A}_{n}$ drawn uniformly
at random from all objects in $\mathcal{A}_{\mathcal{R}}$ of size $n$. Hence
together with the next theorem Fact 1.4 guarantees that the linear time
samplers claimed in Theorem 1.2 do indeed exist.

######  Theorem 1.5.

Assume $\mathcal{A}_{\mathcal{R}}$ is tame. Then under the RAM model of
computation the sampler in Section 2 generates the $\mathcal{R}$-enriched tree
$\mathsf{A}_{n}$ in expected time $O(n)$.

At this point we already anticipate that the algorithm generating
$\mathsf{A}_{n}$ is structured as follows. We first sample a
Bienaymé–Galton–Watson tree with offspring distribution $\xi$ of size $n$
using Devroye’s algorithm. Subsequently, for each node we repeatedly call the
sampling procedure $\Gamma\mathcal{R}(t)$ until an $\mathcal{R}$-object of the
same size as the outdegree of the node at hand is produced. The latter step
enhances the offspring of each node with an additional structure leading to an
$\mathcal{R}$-enriched tree.

###  1.2. Plan of the paper

In Section 2 we present our sampler, Algorithm 2.1, for tame
$\mathcal{R}$-enriched trees as claimed in Theorem 1.5. To prove the linear
time complexity of our algorithm we first collect some preliminaries in
Section 3. In particular, we recall basic facts about combinatorial classes
and $\mathcal{R}$-enriched trees, simply generated trees and local limit
theorems for iid random variables. Subsequently, the proof of Theorem 1.5 is
conducted in Section 4. Finally, in Section 5 we explain in detail how the
sampler for $\mathcal{R}$-enriched trees can be used to obtain linear time
samplers for the classes listed in Example 1.1. We emphasize that for most of
the examples this is not ’just’ an application of Algorithm 2.1 but a rather
involved task leading to new efficient sampling procedures for the classes at
hand.

##  2\. The Sampler

In this section we present the sampler for $\mathsf{A}_{n}$ that is needed in
the proof of Theorem 1.5. We briefly recall the construction of a
Bienaymé–Galton–Watson (BGW) tree with offspring distribution $\xi$. We start
with a distinguished root to which a number of ordered children according to
an independent copy of $\xi$ is appended. Repeat this procedure for any node
that has not received any children yet or the outcome of the copy of $\xi$ was
$0$. The result is the arbitrarily sized _unlabelled ordered_ rooted tree
$\mathsf{T}$ such that the distribution of its vertex-degrees is
$(p_{k})_{k\geq 0}$. The corresponding size-constrained tree is defined as
$\mathsf{T}_{n}:=(\mathsf{T}\mid\lvert\mathsf{T}\rvert=n)$ for
$n\in\mathbb{N}$. We use the notation that $v\in T$ is some node in the
unlabelled ordered tree $T$. With this at hand, our sampler operates as
follows.

######  Algorithm 2.1.

(Uniform $\mathcal{R}$-enriched tree of size $n$.)

  1. (1)

Generate the size-constrained Bienaymé–Galton–Watson tree $\mathsf{T}_{n}$
with offspring distribution $\xi$ as in [21].

  2. (2)

For some
$\mathcal{A}(\rho_{\mathcal{A}_{\mathcal{R}}})<t_{0}<\rho_{\mathcal{R}}$
repeatedly call for each $v\in\mathsf{T}_{n}$ the sampler
$\Gamma\mathcal{R}(t_{0})$ until it produces an object $\mathsf{R}_{v}$ of
size $d_{\mathsf{T}_{n}}^{+}(v)$.

  3. (3)

Distribute labels in $\\{1,\dots,n\\}$ uniformly at random and drop the
ordering of the vertices afterwards.

The last step requires some explanation. In Steps 1 and 2 we generate an
object $(T,(R_{v})_{v\in T})$, where $T$ is an unlabelled ordered rooted tree
of size $n$ and $R_{v}\in\mathcal{R}[[d^{+}(v)]]$ for $v\in T$. The ordering
of the offspring of $v\in T$ corresponds to a canonical labelling of the
vertices, say $(v,1),\dots,(v,d^{+}(v))$ so that we may see the object $R_{v}$
as being labelled with elements from $\\{(v,1),\dots,(v,d^{+}(v))\\}$. Naming
the root $o$, the children of the root are hence labelled
$(o,1),\dots,(o,d^{+}(o))$, the children of the first child of the root by
$((o,1),1),\dots,((o,1),d^{+}(o,1))$ and so on. In particular the labels are
all distinct and by generating a uniform permutation of $[n]$ we may
canonically relabel the entire object with labels in $[n]$.

######  Remark 2.2.

Alternatively we could use in Step (2) of the algorithm an _exact-size_
sampler for obtaining objects from $\mathcal{R}_{k}$ for
$k=d^{+}_{\mathsf{T}_{n}}(v)$ that runs in time $e^{ck}$ for some (small)
$c>0$. This will not affect the asymptotic expected running time, as we will
see later that typically the largest degree in $\mathsf{T}_{n}$ is in $O(\log
n)$. However, we will not consider this setting further here.

The next lemma guarantees that Algorithm 2.1 produces an uniform object of
size $n$ from $\mathcal{A}_{\mathcal{R}}$.

######  Lemma 2.3.

In distribution
$(\mathsf{T}_{n},(\mathsf{R}_{v})_{v\in\mathsf{T}_{n}})=\mathsf{A}_{n}$.

The proof is rather straightforward (combine the distribution of
$\mathsf{T}_{n}$ with the fact that a Boltzmann sampler generates objects of a
given size uniformly) and can be found in [44, Lem. 6.1]. So, the proof of
Theorem 1.5 boils down to validating that Algorithm 2.1 can be implemented to
run in expected linear time. This will be done in Section 4. Before we come to
that, let us first have a closer look at Devroye’s algorithm [21] for sampling
size-constrained trees, that is, Step 1 of Algorithm 2.1. Any rooted ordered
tree is uniquely determined by its outdegree sequence in breadth first search
order and, on the other hand, any sequence $(d_{1},\dots,d_{n})$ such that
$\sum_{1\leq i\leq n}d_{i}=n-1$ and $1+\sum_{1\leq i\leq t}(d_{i}-1)>0$ for
all $1\leq t\leq n$ corresponds uniquely to such a tree. Define
$S_{t}:=1+\sum_{1\leq i\leq t}(\xi_{i}-1)$ for $1\leq t\leq n$. The outdegrees
of a Bienaymé–Galton–Watson trees are per definition given by the offspring
distribution $\xi$, so that the random tree $\mathsf{T}_{n}$ can be identified
with the distribution of

(2.1) $\displaystyle(\xi_{1},\dots,\xi_{n})\leavevmode\nobreak\
\leavevmode\nobreak\ \bigg{|}\leavevmode\nobreak\ \leavevmode\nobreak\
\left\\{\sum_{1\leq i\leq n}\xi_{i}=n-1,S_{t}>0\text{ for all }1\leq t\leq
n-1\right\\}.$

This fact, that we also shall exploit, is used in [21] to generate efficiently
$\mathsf{T}_{n}$ as explained in the following algorithm. Recall that
$p_{k}=\mathbb{P}(\xi=k)$.

######  Algorithm 2.4.

(Size-constrained BGW tree $\mathsf{T}_{n}$ with offspring distribution
$\xi$.)

  1. (1)

Sample the multinomial random vector $(N_{0},N_{1},\dots)$ with parameters
$(n,p_{0},p_{1},\dots)$ repeatedly until $\sum_{1\leq i\leq n}iN_{i}=n-1$.

  2. (2)

Create a sequence of length $n$ populated with $N_{j}$ times $j$ for $0\leq
j\leq n$.

  3. (3)

Randomly permute this sequence with each permutation equiprobable.

  4. (4)

Shift the elements of the sequence cyclically until the condition in (2.1) is
fulfilled.

For generating a multinomial vector in the first step [21] proposes a sub-
routine that samples binomial random variables.

######  Algorithm 2.5.

(Multinomial random vector $(N_{0},N_{1},\dots)$ with parameters
$(n,p_{0},p_{1},\dots)$.)

  1. (1)

Let $N_{0}=\mathrm{Bin}(n,p_{0})$.

  2. (2)

For $i\geq 1$, if $\sum_{0\leq j\leq i-1}N_{j}<n$, let
$N_{i}=\mathrm{Bin}(n-\sum_{0\leq j\leq i-1}N_{j},p_{i}/(1-\sum_{0\leq j\leq
i-1}p_{j})$ and otherwise set $N_{i}=0$.

In [21] it is established that under the RAM model of computation the expected
number of steps taken by Algorithm 2.4 is $O(n)$, provided that $\xi$ has
finite variance and that it takes one step to generate an independent copy of
$\xi$. Our setting, however, is slightly different, as we do not a priori know
the entire vector $(p_{0},p_{1},\dots)$. We need to incorporate the time it
takes to compute this vector into the runtime of Step 1 of Algorithm 2.1.
Conveniently, it is sufficient to consider $(p_{0},p_{1},\dots)$ truncated at
$K:=\max_{1\leq i\leq n}\xi_{i},$ the step at which $N_{j}=0$ for all $j>K$ in
Algorithm 2.5 and hence the point in time after which the precise value of
$p_{j}$ for $j>K$ is not needed anymore. Since $\xi$ has finite exponential
moments we will essentially obtain that $K=O(\log n)$ and together with (C)
this will not spoil the overall linear runtime.

######  Lemma 2.6.

If $\mathcal{A}_{\mathcal{R}}$ is tame, Algorithm 2.4 can be implemented to
have an expected running time of $O(n)$.

##  3\. Preliminaries

###  3.1. Combinatorial classes

In this section we recall some background information about combinatorial
classes. A comprehensive survey of the theory is given in the excellent books
[27, 6]. As already said, a combinatorial class is given by a countable set
$\mathcal{C}$ equipped with a size function
$\lvert\cdot\rvert:\mathcal{C}\to\mathbb{N}_{0}$ such that
$\mathcal{C}_{n}:=\lvert\\{C\in\mathcal{C}:\lvert C\rvert=n\\}\rvert$ is
finite for all $n\in\mathbb{N}_{0}$. Elements of $\mathcal{C}$ are called
objects or structures and any object in $\mathcal{C}_{n}$ is said to be
comprised of $n$ atoms or to be of size $n$. We call $\mathcal{C}$ labelled if
each atom of an object in $\mathcal{C}$ bears a distinct label. For
convenience, let the label set of any $C\in\mathcal{C}_{n}$ be given by $[n]$.
If we want to stress out a different labelling, we simply write
$C\in\mathcal{C}[U]$ describing an object $C\in\mathcal{C}_{\lvert U\rvert}$
labelled according to the finite set $U$. For any bijection $\sigma:U\to V$
between finite sets $U,V$ and $C\in\mathcal{C}[U]$ we write $\sigma.C$ for the
object obtained by replacing the label $\ell_{v}\in U$ of each atom $v$ of $C$
by $\sigma(\ell_{v})\in V$. Clearly the resulting object is in
$\mathcal{C}[V]$. For coherence we assume that $C\in\mathcal{C}[U]$ implies
that $\sigma.C\in\mathcal{C}[U]$ for any bijection $\sigma:U\to U$. The
(exponential) generating series of $\mathcal{C}$ is the formal power series
defined by

$\mathcal{C}(x):=\sum_{n\geq 0}\lvert\mathcal{C}_{n}\rvert\frac{x^{n}}{n!}.$

######  Example 3.1.

Consider the class $\mathcal{A}$ of rooted labelled unordered acyclic
connected graphs, in short Cayley trees. We see in Figure 1 some
$T\in\mathcal{A}_{5}$ with labels in $[5]$. Applying the bijection $\sigma$
mapping $1\mapsto a$, $2\mapsto b$ and so on, we retrieve an object $\sigma.T$
in $\mathcal{A}[\\{a,b,c,d,e\\}]$.

Figure 1. Relabelling $T$ under the bijection $\sigma$.

####  3.1.1. Basic Classes

The basic combinatorial classes are the empty class $\emptyset$, the atomic
class $\mathcal{X}$, the set class SET, the cycle class CYC and the sequence
class SEQ. Let $\mathcal{S}_{n}$ be the symmetric group containing all
permutations of $[n]$ and write $(a_{1},\dots,a_{n})\simeq(b_{1},\dots,b_{n})$
if one of the two sequences is obtained by cyclically shifting the indices of
the other. Then the basic classes are defined by, letting
$n\in\mathbb{N}_{0}$,

  * •

$\lvert\emptyset_{n}\rvert=\mathbbm{1}_{n=0}$,

  * •

$\lvert\mathcal{X}_{n}\rvert=\mathbbm{1}_{n=1}$,

  * •

$\textsc{SET}_{n}=\\{\\{1,\dots,n\\}\\}$,

  * •

$\textsc{CYC}_{n}=\\{(\sigma(1),\dots,\sigma(n))_{\simeq}:\sigma\in\mathcal{S}_{n}\\}$
and

  * •

$\textsc{SEQ}_{n}=\\{(\sigma(1),\dots,\sigma(n)):\sigma\in\mathcal{S}_{n}\\}$.

The respective generating series are computed to be

$\emptyset(x)=1,\quad\mathcal{X}(x)=x,\quad\textsc{SET}(x)=\exp(x),\quad\textsc{CYC}(x)=\log\frac{1}{1-x}\quad\text{and}\quad\textsc{SEQ}(x)=\frac{1}{1-x}.$

####  3.1.2. Constructions

Given classes $\mathcal{A}$ and $\mathcal{B}$ there are several ways to
construct more complex classes.

#### Pointing

The collection of elements $(A,a)$ where $A\in\mathcal{A}$ and $a$ is a
distinguished atom (the root) in $A$ forms the pointed class
$\mathcal{A}^{\bullet}$. Since
$\lvert\mathcal{A}^{\bullet}_{n}\rvert=n\lvert\mathcal{A}_{n}\rvert$ we obtain

$\mathcal{A}^{\bullet}(x)=x\frac{\partial}{\partial x}A(x).$

#### Derivation

Let $\star$ denote a special label such that any atom bearing this label does
not contribute to the total size of the object at hand. The derived class
$\mathcal{A}^{\prime}$ is given by the collection of objects in $\mathcal{A}$
where the largest label is replaced by $\star$, i.e.
$\mathcal{A}^{\prime}_{n-1}:=\mathcal{A}[\\{1,\dots,n-1,\star\\}]$ for all
$n\in\mathbb{N}$. Hence the generating series is computed to be

$\mathcal{A}^{\prime}(x)=\frac{\partial}{\partial x}\mathcal{A}(x).$

#### Disjoint union

If $\mathcal{A}$ and $\mathcal{B}$ are disjoint then the disjoint union
$\mathcal{A}+\mathcal{B}$ is the union $\mathcal{A}\cup\mathcal{B}$ in the
standard set-theoretic sense. Formally and to avoid the assumption that the
two classes at hand are disjoint we introduce two disjoint sets, say $\\{0\\}$
and $\\{1\\}$, and set

$\mathcal{A}+\mathcal{B}:=(\\{0\\}\times\mathcal{A})\cup(\\{1\\}\times\mathcal{B}).$

The size of an object in $\mathcal{A}+\mathcal{B}$ is the size of the
respective object in $\mathcal{A}$ or $\mathcal{B}$. It is straightforward
that

$(\mathcal{A}+\mathcal{B})(x)=\mathcal{A}(x)+\mathcal{B}(x).$

#### Product

The product class $\mathcal{A}\cdot\mathcal{B}$ contains all tuples $(A,B)$
with $A\in\mathcal{A}$ and $B\in\mathcal{B}$ relabelled with labels in
$\\{1,\dots,\lvert A\rvert+\lvert B\rvert\\}$. The size function is defined by
$\lvert(A,B)\rvert=\lvert A\rvert+\lvert B\rvert$. The generating series is

$(\mathcal{A}\cdot\mathcal{B})(x)=\mathcal{A}(x)\mathcal{B}(x).$

#### Substitution

For this construction we assume $\mathcal{B}_{0}=\emptyset$. An object in the
substitution class $\mathcal{A}\circ\mathcal{B}$, sometimes also
$\mathcal{A}(\mathcal{B})$, is comprised of an $\mathcal{A}$-object whose
atoms are replaced by $\mathcal{B}$-objects. In other words,
$\mathcal{A}\circ\mathcal{B}$ contains all equivalence classes of sequences of
the form

$(A,B_{1},\dots,B_{k})_{\simeq},\quad
A\in\mathcal{A}[\\{P_{1},\dots,P_{k}\\}],B_{i}\in\mathcal{B}[P_{i}],1\leq
i\leq k,$

where $k\geq 0$ and $P_{1},\dots,P_{k}$ is a partition of
$\\{1,\dots,\sum_{1\leq i\leq k}\lvert B_{i}\rvert\\}$ with $\lvert
P_{i}\rvert=\lvert B_{i}\rvert$ for $1\leq i\leq k$. The equivalence relation
“$\simeq$” terms two sequences $(A,B_{1},\dots,B_{k})$ and
$(A^{\prime},B_{1}^{\prime},\dots,B_{k}^{\prime})$ isomorphic if
$A=A^{\prime}$ and for any permutation
$\sigma:\\{1,\dots,k\\}\to\\{1,\dots,k\\}$ such that $\sigma.A=A$ it holds
that $B_{\sigma(i)}=B_{i}^{\prime}$ for $1\leq i\leq k$. Hence any
$M\in\mathcal{A}\circ\mathcal{B}$ possesses a core structure $A$ and
_components_ $B_{1},\dots,B_{k}$. The size is then given by $\lvert
M\rvert:=\sum_{1\leq i\leq k}\lvert B_{i}\rvert$. The respective generating
series fulfils

$(\mathcal{A}\circ\mathcal{B})(x)=\mathcal{A}(\mathcal{B}(x)).$

####  3.1.3. $\mathcal{R}$-enriched trees

The theory of this subsection is extensively treated in [6, Ch. 3]. Let
$\mathcal{R}$ be a combinatorial class and $\mathcal{A}$ the class of rooted
Cayley trees. As we already defined in Section 1.1, the class of
$\mathcal{R}$-enriched trees $\mathcal{A}_{\mathcal{R}}$ contains all
sequences

$(T,(R_{v})_{v\in T}),\qquad T\in\mathcal{A},R_{v}\in\mathcal{R}[P_{v}],v\in
T,$

where $P_{v}$ is the label set of the offspring of vertex $v\in T$ and the
sequence $(R_{v})_{v\in T}$ is canonically ordered, for example in breath
first search appearance of $v\in T$. Further, recall that the size of any
$A=(T,(R_{v})_{v\in T})\in\mathcal{A}_{\mathcal{R}}$ is defined as $\lvert
A\rvert=\lvert T\rvert$. As any $\mathcal{R}$-enriched tree is comprised of a
root to which an $\mathcal{R}$-structure is attached whose atoms are replaced
by $\mathcal{R}$-enriched trees, we obtain the functional equation

$\mathcal{A}_{\mathcal{R}}=\mathcal{X}\cdot\mathcal{R}(\mathcal{A}_{\mathcal{R}}),$

see Theorem 2 in [6, Ch. 3]. This is a combination of the product and
substitution construction and so the generating series satisfies the equation

(3.1)
$\displaystyle\mathcal{A}_{\mathcal{R}}(x)=x\mathcal{R}(\mathcal{A}_{\mathcal{R}}(x)).$

######  Example 3.2.

Letting $\mathcal{R}$ be one of the basic combinatorial classes, we retrieve
basic models of trees, see also Figure 2. To wit:

  * •

By choosing $\mathcal{R}=\textsc{SET}$ no additional structure is imposed on
the offspring set of each vertex, so that we obtain that
$\mathcal{A}_{\textsc{SET}}=\mathcal{A}$, the class of rooted Cayley trees.

  * •

When $\mathcal{R}=\textsc{SEQ}$ the offspring of each vertex is given an
ordering and we obtain that $\mathcal{A}_{\textsc{SEQ}}=\mathcal{T}$, the
class of rooted labelled ordered trees.

  * •

By cyclically ordering the offspring of each vertex (that is,
$\mathcal{R}=\textsc{CYC}$) we obtain the class
$\mathcal{A}_{\textsc{CYC}}=\mathcal{P}$ of rooted labelled plane trees.

Figure 2. An $\mathcal{R}$-enriched tree observed locally at some node $v$ and
its offspring labelled by $\\{a,b,c\\}$ paired with the $\mathcal{R}$-object
$R_{v}$, where $R_{v}=(b,a,c)_{\simeq}\in\textsc{CYC}[\\{a,b,c\\}]$ or
$(c,b,a)\in\textsc{SEQ}[\\{a,b,c\\}]$.

###  3.2. Simply generated trees

In the following we recall results concerning simply generated trees discussed
thoroughly in [31, Ch. 7 and 8]. We will use these results to study the
offspring distribution defined in (1.2). Denote the class of _rooted
unlabelled ordered trees_ by $\widetilde{\mathcal{T}}$ that is obtained by
taking equivalence classes under relabelling in $\mathcal{T}$, the labelled
version shown in Example 3.2. Let $\mathrm{\omega}=(\omega_{k})_{k\geq 0}$ be
a real-valued non-negative sequence and set $\Phi(x):=\sum_{k\geq
0}\omega_{k}x^{k}$. For any given finite ordered tree $T$ in
$\widetilde{\mathcal{T}}$ define its weight by

$\omega(T):=\prod_{v\in T}\omega_{d^{+}(v)}.$

Define by $\mathsf{T}_{n}(\omega)$ the $n$-sized random tree with distribution

(3.2)
$\displaystyle\mathbb{P}(\mathsf{T}_{n}(\omega)=T)=\frac{\omega(T)}{Z_{n}},\quad\text{
where }T\in\widetilde{\mathcal{T}}_{n},\leavevmode\nobreak\
Z_{n}=\sum_{T^{\prime}\in\widetilde{\mathcal{T}}_{n}}\omega(T^{\prime}).$

We only consider values for $n$ such that $Z_{n}$, the so-called partition
function, is strictly greater than zero. In the next lemma we gather important
properties of the generating function of the sequence of partition functions
$Z(x):=\sum_{n\geq 1}Z_{n}x^{n}$.

######  Lemma 3.3 ([31, Rem. 3.2, Thm. 7.1, Rem. 7.5]).

The generating function of the partition functions satisfies the relation

$Z(x)=x\Phi(Z(x)).$

If in addition $\omega$ is such that $\omega_{0}>0$ and $\omega_{k}>0$ for
some $k\geq 2$, then $Z(x)$ has radius of convergence

$\displaystyle\rho_{Z}=\frac{\tau}{\Phi(\tau)},\quad\text{where}\quad\tau=Z(\rho_{Z})\in(0,\infty),\Phi(\tau)\in(0,\infty).$

If $\omega$ is a probability weight sequence we readily notice that
$\mathsf{T}_{n}(\omega)$ defined in (3.2) is just the size-constrained
Bienaymé–Galton–Watson tree with offspring distribution $\omega$. Thus, simply
generated trees are a generalization of Bienaymé–Galton–Watson trees. However,
as we will see in a moment, using a technique called _tilting_ , it is often
possible to view $\mathsf{T}_{n}(\omega)$ as a Bienaymé–Galton–Watson tree
even if $\omega$ is not a probability sequence. We actually claim even more:
there are cases – in particular the ones that we consider here – where it is
possible to transform $\omega$ to a probability sequence such that
simultaneously the distribution of the underlying simply generated tree is not
altered and in addition the offspring distribution is critical, meaning that
the mean is $1$ and of finite variance. More specifically, letting $\tau$ be
as in Lemma 3.3, the candidate for the offspring distribution is the _tilted_
sequence

(3.3) $\displaystyle\pi_{k}:=\frac{\omega_{k}\tau^{k}}{\Phi(\tau)},\quad
k\in\mathbb{N}_{0}.$

Note that in general this is not necessarily a probability sequence (for
example, if $\tau=\infty$). In order to establish conditions under which
$(\pi_{k})_{k\geq 1}$ is a probability sequence we need some more notation.
Denote the radius of convergence of $\Phi(x)$ by $\rho$. Set

$\Psi(x):=\frac{x\Phi^{\prime}(x)}{\Phi(x)}\qquad\text{and}\qquad\nu:=\lim_{x\to\rho}\Psi(x)\in(0,\infty].$

######  Lemma 3.4 ([31, Thm. 7.1, Rem. 7.5 and Ch. 8 Ia]).

Let $\omega$ be a weight sequence such that $\omega_{0}>0$ and $\omega_{k}>0$
for some $k\geq 2$. If in addition $0<\tau<\rho$ (case $(Ia)$ in [31]) then
$(\pi_{k})_{k\geq 0}$ is a probability sequence with mean $1$ and finite
exponential moments. In particular we have that $\rho_{Z}$, $Z(\rho_{Z})$ and
$\Phi(Z(\rho_{Z}))$ are finite.

The other ranges for $\tau$ can be treated as well, see [31, Ch. 8], but that
is not needed here.

###  3.3. Local limit theorems

Let in this subsection $\xi$ be a non-negative integer-valued random variable.
Further let $\xi_{1},\xi_{2},\dots$ be iid copies of $\xi$ and set
$\Xi_{n}:=\xi_{1}+\cdots+\xi_{n}$ for $n\in\mathbb{N}$. Define the span $d$ by

$d:=\max\\{d\geq 1:d\mid i\text{ whenever }\mathbb{P}\left(\xi=i\right)>0\\}.$

The following local central limit theorem holds for any distribution with
finite variance, so in particular in our intended application.

######  Lemma 3.5 ([31, Lem. 4.1 and Rem. 14.2]).

If $\mathbb{E}[\xi]=1$ and $\mathbb{V}[\xi]<\infty$

$\mathbb{P}\left(\Xi_{n}=n-1\right)\sim\frac{d}{\sqrt{2\pi\sigma^{2}n}}\quad\text{
as }n\to\infty\quad\text{and }n\text{ divisible by }d.$

Furthermore,

$\mathbb{P}\left(\Xi_{n}=m\right)\leq\frac{d+o(1)}{\sqrt{2\pi\sigma^{2}n}},\quad
m\in\mathbb{N}.$

##  4\. Proofs

In this section we prove Theorem 1.5. We first show that Algorithm 2.4 runs in
linear time in our setting as claimed in Lemma 2.6. The following statement
about the distribution $\xi$ defined in (1.2) will be a helpful tool for that
matter and is a straightforward consequence of results about simply generated
trees in presented in the previous section.

######  Lemma 4.1.

We have $\mathbb{E}[\xi]=1$ and there exists $\varepsilon>0$ such that
$\mathbb{E}[(1+\varepsilon)^{\xi}]<\infty$. In particular, the quantities
$\rho_{\mathcal{A}_{\mathcal{R}}}$,
$\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})$ and
$\mathcal{R}(\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}}))$ are
finite.

###### Proof.

Let $\mathsf{T}_{n}(\omega)$ be the simply generated tree of size $n$ with
weight sequence $\omega=(r_{k}/k!)_{k\geq 0}$ as defined in (3.2), i.e.,

(4.1)
$\displaystyle\mathbb{P}(\mathsf{T}_{n}(\omega)=T)=\frac{\omega(T)}{Z_{n}},\qquad\text{where
}\omega(T)=\prod_{v\in T}\frac{r_{d^{+}(v)}}{d^{+}(v)!},\leavevmode\nobreak\
Z_{n}=\sum_{T^{\prime}\in\widetilde{\mathcal{T}}_{n}}\omega(T^{\prime}),\leavevmode\nobreak\
T\in\widetilde{\mathcal{T}}_{n}.$

Then the generating function $Z(x)$ of the partition functions $(Z_{n})_{n\geq
0}$ is recursively given by $Z(x)=x\mathcal{R}(Z(x))$. Let
$(\mathcal{A}_{\mathcal{R}})_{n}$ be the collection of objects in
$\mathcal{A}_{\mathcal{R}}$ of size $n$. Since
$\mathcal{A}_{\mathcal{R}}=\mathcal{X}\cdot\mathcal{R}(\mathcal{A}_{\mathcal{R}})$
we know by (3.1) that
$\mathcal{A}_{\mathcal{R}}(x)=x\mathcal{R}(\mathcal{A}_{\mathcal{R}}(x))$ by
which we deduce

(4.2)
$\displaystyle\mathcal{A}_{\mathcal{R}}(x)=Z(x)\qquad\text{and}\qquad\frac{\lvert(\mathcal{A}_{\mathcal{R}})_{n}\rvert}{n!}=Z_{n},\quad
n\in\mathbb{N}_{0}.$

We conclude that due to Lemma 3.3 the radius of convergence
$\rho_{\mathcal{A}_{\mathcal{R}}}$ of $\mathcal{A}_{\mathcal{R}}(x)$ (or
equivalently $Z(x)$) is given by

$\rho_{\mathcal{A}_{\mathcal{R}}}=\frac{\tau}{\mathcal{R}(\tau)},\qquad\text{where
}\tau=\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}}).$

Assumption (B) immediately implies that $0<\tau<\rho_{\mathcal{R}}$ and we
deduce due to Lemma 3.4 that $(\pi_{k})_{k\geq 0}$ as defined in (3.3) is the
probability distribution with mean $1$ and finite exponential moments such
that the distribution of $\mathsf{T}_{n}(\omega)$ is not altered by switching
to $(\pi_{k})_{k\in\mathbb{N}_{0}}$. Further we observe that this is also the
distribution of $\xi$ given in (1.2), i.e.

$\pi_{k}=\frac{r_{k}\tau^{k}}{\mathcal{R}(\tau)k!}=\frac{r_{k}\mathcal{A}(\rho_{\mathcal{A}})^{k}}{\mathcal{R}(\mathcal{A}(\rho_{\mathcal{A}}))k!}=p_{k},\quad
k\in\mathbb{N}_{0}$

and hence the claim is verified. ∎

With these considerations at hand we first prove Lemma 2.6 and then Theorem
1.5. In the following let $\xi_{1},\xi_{2},\dots$ be independent copies of
$\xi$.

###### Proof of Lemma 2.6.

Define

$K:=\max_{1\leq i\leq
n}\xi_{i},\quad\tau_{n}:=\mathbb{E}[K]\quad\text{and}\quad\varphi_{n}:=\mathbb{P}\bigg{(}\sum_{1\leq
i\leq n}\xi_{i}=n-1\bigg{)}.$

According to [21] the expected time needed in Step 1 of Algorithm 2.4 (i.e.
the expected running time of Algorithm 2.5) is
$O\big{(}(1+\tau_{n})/\varphi_{n})\big{)}+O(n)$ if the probabilities
$(p_{0},p_{1},\dots)$ are given. Here the term $1+\tau_{n}$ corresponds to the
expected time until a multinomial vector $(N_{0},N_{1},\dots,N_{K},0,\dots)$
is generated, and it takes on average $\varphi_{n}^{-1}$ rejections until a
vector is found such that $\sum_{1\leq i\leq n}iN_{i}=n-1$. Note that after
the (random) multinomial vector has been generated in Algorithm 2.4, Step $2$
is deterministic and takes $O(n)$ steps, Step $3$ is a standard shuffling
procedure (e.g. [32, Alg. P (Shuffling)]) of $n$ elements and takes $O(n)$
steps and Step $4$ is again performed in $O(n)$ steps. In our setting we
additionally have to take care of the computation time of
$(p_{0},p_{1},\dots,p_{K})$ in Step 1. Denoting the expected time to do so by
$X$ we obtain that the total expected running time of Algorithm 2.4 in our
setting is

$O\left(\frac{1+\tau_{n}+X}{\varphi_{n}}\right)+O(n).$

Lemma 4.1 guarantees that $\mathbb{E}[\xi^{2}]<\infty$, so we immediately
obtain from [21] that $\tau_{n}=O(n^{1/2})$ and $\varphi_{n}^{-1}=O(n^{1/2})$.
This means that it suffices to show that $X=O(n^{1/2})$. Assumption (C) yields
that there exists a non-negative sequence $(f_{i})_{i\in\mathbb{N}_{0}}$ with
$f_{n}\to 0$ as $n\to\infty$ such that the expected time to compute
$(p_{0},p_{1},\dots,p_{K})$ is

(4.3) $\displaystyle X=\mathbb{E}\bigg{[}\sum_{0\leq i\leq
K}\mathrm{e}^{f_{i}\cdot i}\bigg{]}=\sum_{m\geq
1}\mathbb{P}\left(K=m\right)\sum_{0\leq i\leq m}\mathrm{e}^{f_{i}\cdot i}.$

Since $f_{n}\to 0$ we obtain that for every $\varepsilon>0$ there is $C>0$
such that for all $m\in\mathbb{N}$

$\sum_{0\leq i\leq m}\mathrm{e}^{f_{i}\cdot i}\leq
C\cdot\mathrm{e}^{\varepsilon m}.$

Thus, continuing with (4.3)

$X\leq C\sum_{m\geq 1}\mathbb{P}\left(K=m\right)\mathrm{e}^{\varepsilon
m}=C\mathbb{E}[\mathrm{e}^{\varepsilon K}].$

By applying Lemma 4.1 we may choose a $t>0$ such that
$\mathbb{E}[\mathrm{e}^{t\xi}]<\infty$. We use the Log-Sum-Exp estimate
$\max_{1\leq i\leq n}x_{i}\leq\log(\mathrm{e}^{\alpha
x_{1}}+\cdots+\mathrm{e}^{\alpha x_{n}})/\alpha$ for any
$(x_{1},\dots,x_{n})\in\mathbb{N}_{0}^{n}$ and $\alpha>0$ to obtain

$\mathbb{E}[\mathrm{e}^{\varepsilon
K}]\leq\mathbb{E}[\mathrm{e}^{\varepsilon/t\cdot\log(\mathrm{exp}(t\xi_{1})+\cdots+\mathrm{exp}(t\xi_{n}))}]=\mathbb{E}[(\mathrm{exp}(t\xi_{1})+\cdots+\mathrm{exp}(t\xi_{n}))^{\varepsilon/t}].$

Pick $\varepsilon>0$ such that $0<\varepsilon/t<1/2$. Then the Jensen
inequality entails ($x\mapsto x^{\varepsilon/t}$ is concave)

$\displaystyle\mathbb{E}[(\mathrm{exp}(t\xi_{1})+\cdots+\mathrm{exp}(t\xi_{n}))^{\varepsilon/t}]\leq\mathbb{E}[\mathrm{exp}(t\xi_{1})+\cdots+\mathrm{exp}(t\xi_{n})]^{\varepsilon/t}=(n\mathbb{E}[\mathrm{e}^{t\xi}])^{\varepsilon/t}=o(n^{1/2}).$

∎

###### Proof of Theorem 1.5.

Subsequently we go through each step in Algorithm 2.1 and explain how the
expected runtime of $O(n)$ is achieved. For Step 1 see Lemma 2.6. Let us next
investigate Step 2. Recall that
$\mathcal{A}(\rho_{\mathcal{A}})<t_{0}<\rho_{\mathcal{R}}$. The probability
that $\Gamma\mathcal{R}(t_{0})$ produces a $k$-sized object is

$\mathbb{P}(\lvert\Gamma\mathcal{R}(t_{0})\rvert=k)=\frac{r_{k}t_{0}^{k}}{k!\mathcal{R}(t_{0})},\qquad
k\in\mathbb{N}_{0}.$

Hence the time until an object of size $k\in\mathbb{N}_{0}$ is distributed
like a random variable $G(k)$ with geometric distribution and with mean

$g(k)=\frac{r_{k}t_{0}^{k}}{k!\mathcal{R}(t_{0})}\sum_{\ell\geq
1}\ell\left(1-\frac{r_{k}t_{0}^{k}}{k!\mathcal{R}(t_{0})}\right)^{\ell-1}=\frac{k!\mathcal{R}(t_{0})}{r_{k}t_{0}^{k}}.$

Let $W_{n}$ denote the total waiting time until Step 2 is completed and set
$\Xi_{n}=\sum_{1\leq i\leq n}\xi_{i}$. Recall that $\mathsf{T}_{n}$ can be
equivalently represented by its outdegree sequence as outlined in (2.1) so
that we deduce

(4.4)
$\displaystyle\mathbb{E}[W_{n}]=\mathbb{E}\left[\sum_{v\in\mathsf{T}_{n}}G({d_{\mathsf{T}_{n}}^{+}(v)})\right]=\sum_{1\leq
i\leq n}\mathbb{E}\left[G(\xi_{i})\Bigm{|}\Xi_{n}=n-1,S_{t}>0\text{ for }1\leq
t\leq n-1\right].$

Next we use the fact, sometimes referred to as the _cycle lemma_ , see for
example [20], that for any sequence $(d_{1},\dots,d_{n})$ of non-negative
integers such that $\sum_{1\leq i\leq n}d_{i}=n-1$ there exists a unique
$1\leq\ell\leq n$ such that the shifted sequence
$(\tilde{d}_{1},\dots,\tilde{d}_{n})=(d_{\ell},\dots,d_{n},d_{1},\dots,d_{\ell-1})$
fulfils that $1+\sum_{1\leq i\leq t}(\tilde{d}_{i}-1)>0$ for $1\leq t\leq
n-1$. Since this shift is only one of $n$ possible shifts and we are dealing
with iid random variables we obtain

$\mathbb{P}\left(\Xi_{n}=n-1,S_{t}>0\text{ for }1\leq t\leq
n-1\right)=\frac{1}{n}\mathbb{P}\left(\Xi_{n}=n-1\right),$

a well-known relation. Further, as $\xi_{1},\xi_{2},\dots$ are iid the random
variable $G(\xi_{i})$ is not altered by rotating $(\xi_{1},\dots,\xi_{n})$ so
that we also get for any $k\in\mathbb{N}$

$\mathbb{P}\left(G(\xi_{i})=k,\Xi_{n}=n-1,S_{t}>0\text{ for }1\leq t\leq
n-1\right)=\frac{1}{n}\mathbb{P}\left(G(\xi_{1})=k,\Xi_{n}=n-1\right),\leavevmode\nobreak\
\leavevmode\nobreak\ 1\leq i\leq n.$

Combining the latter two equations into (4.4) yields

(4.5)
$\displaystyle\mathbb{E}[W_{n}]=n\mathbb{E}\left[G(\xi_{1})\Bigm{|}\Xi_{n}=n-1\right].$

Next we compute

$\displaystyle\mathbb{E}\left[G(\xi_{1})\Bigm{|}\Xi_{n}=n-1\right]$
$\displaystyle=\sum_{k,\ell\geq
0}\ell\mathbb{P}\left(G(k)=\ell\right)\mathbb{P}\left(\xi_{1}=k\Bigm{|}\Xi_{n}=n-1\right)$
$\displaystyle=\sum_{k\geq
0}g(k)\mathbb{P}\left(\xi_{1}=k\Bigm{|}\Xi_{n}=n-1\right).$

With this at hand we obtain with Lemma 3.5 (which we are allowed to apply due
to Lemma 4.1) that

(4.6) $\displaystyle\mathbb{E}\left[G(\xi_{1})\Bigm{|}\Xi_{n}=n-1\right]$
$\displaystyle=\sum_{k\geq
0}g(k)\mathbb{P}(\xi=k)\frac{\mathbb{P}(\Xi_{n-1}=n-k-1)}{\mathbb{P}(\Xi_{n}=n-1)}$
$\displaystyle=O\left(\mathbb{E}[g(\xi)]\right).$

Since $t_{0}>\mathcal{A}(\rho_{\mathcal{A}})$,

(4.7) $\displaystyle\mathbb{E}[g(\xi)]=\sum_{k\geq
0}\frac{\mathcal{R}(t_{0})}{\mathcal{A}(\rho_{\mathcal{A}})}\left(\frac{\mathcal{A}(\rho_{\mathcal{A}})}{t_{0}}\right)^{k}<\infty.$

Looking back at (4.5) this immediately gives us $\mathbb{E}[W_{n}]=O(n)$, as
desired. Finally, generating a uniform permutation of $[n]$ in Step 3 takes
time $O(n)$, see for example [32, Alg. P (Shuffling)]. ∎

##  5\. Main Applications

We study several models of random trees, graphs and permutations. For each we
explain in detail how they fit into the general framework of
$\mathcal{R}$-enriched trees and devise linear time exact size sampling
algorithms by verifying the conditions of our main theorem.

###  5.1. Subcritical classes of connected graphs

Let us first recall a few basic notions from graph theory. A subgraph of a
graph $G$ is called a _block_ of $G$ if is is maximal such that it is either
(isomorphic) to an edge or if it is 2-connected otherwise. We call a class
$\mathcal{G}$ _block-stable_ if it contains the graph that is isomorphic to a
single edge and that has the property that a graph belongs to $\mathcal{G}$ if
and only if all of its blocks belong to $\mathcal{G}$. Block stable classes
are ubiquitous, and include, for example, classes that are specified by
excluding a finite list of minors.

It is well-known, see for example [17], that any block stable class
$\mathcal{C}$ of connected graphs satisfies the decomposition

(5.1)
$\displaystyle\mathcal{C}^{\bullet}\simeq\mathcal{X}\cdot(\textsc{SET}\circ\mathcal{B}^{\prime}\circ\mathcal{C}^{\bullet}),$

where $\mathcal{B}$ denotes the class of 2-connected graphs in $\mathcal{C}$
(together, possibly, with the graph that is isomorphic to an edge) and
$\mathcal{X}$ contains a single vertex. The combinatorial constructions used
in that formula are defined in the preliminaries, see Section 3.1. This
decomposition of connected graphs is a consequence from the decomposition into
blocks that enables us to describe a graph in terms of a tree and associated
subgraphs of higher connectivity. Roughly speaking, Equation (5.1) follows
from the fact that the root vertex of a connected rooted graph is incident to
an unordered collection of blocks, that is, maximal $2$-connected subgraphs.
The entire graph may be described by this collection, with arbitrary rooted
connected graphs glued to each of its non-root vertices.

What is important here is that block stable classes are isomorphic to enriched
trees $\mathcal{A}_{\mathcal{R}}$ with
$\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$; this observation is not
new and was also exploited elsewhere [37, 43, 44]. The correspondence is
illustrated in Figure 3. Roughly speaking, we “unroll” the decomposition in
(5.1). That is, given a rooted connected graph, we form the collection of
blocks incident to the root vertex. This collection will become the decoration
of the root of the associated tree. The non-root vertices of this collection
correspond to the children of the root of the associated tree. As the entire
graph consists of this collection with arbitrary rooted graphs glued to each
of its non-root vertices, this transformation is then recursively applied to
each of these graphs, grafting the resulting enriched trees to the children of
the root in the enriched tree.

Figure 3. A rooted connected graph, its block decomposition, and the
corresponding $\mathcal{R}$-enriched tree.

From the description of block stable classes, see also (1.1), we immediately
obtain the relation

$\mathcal{C}^{\prime}(x)=\exp(\mathcal{B}^{\prime}(x\mathcal{C}^{\prime}(x)))$

for the corresponding exponential generating functions. We will study here the
particular case in which the composition of the generating functions is
_subcritical_ , meaning that the largest value that $x\mathcal{C}^{\prime}(x)$
can attain, where $x$ is at most the radius of convergence of
$\mathcal{C}(x)$, lies strictly within the disc of convergence of
$\mathcal{B}^{\prime}(x)$.

######  Definition 5.1.

Let $\mathcal{C}$ be a block stable class of connected graphs and
$\mathcal{B}$ the corresponding class of 2-connected graphs together with the
graph that is isomorphic to an edge. Let $\rho_{\mathcal{C}}$ and
$\rho_{\mathcal{B}}$ denote the radii of convergence of $\mathcal{C}(x)$ and
$\mathcal{B}(x)$. We say that $\mathcal{C}$ is _subcritical_ if
$\rho_{\mathcal{B}}>\rho_{\mathcal{C}}\mathcal{C}^{\prime}(\rho_{\mathcal{C}})$.

Subcritical graph classes have been studied from various viewpoints and
include many important classes like trees, outerplanar and series-parallel
graphs, but exclude also others, like planar graphs. From an _analytical_
viewpoint, in the subcritical case the behavior of $\mathcal{C}(x)$ near its
singular points is not dictated by the behavior of $\mathcal{B}(x)$, but it is
rather a consequence of the composition
$\mathcal{B}^{\prime}(x\mathcal{C}^{\prime}(x))$; this is in stark contrast to
critical compositions (where necessarily
$\rho_{\mathcal{B}}=\rho_{\mathcal{C}}\mathcal{C}^{\prime}(\rho_{\mathcal{C}})$),
where there is an explicit interplay. From a _combinatorial_ viewpoint
subcritical classes are very much tree-like, in the sense that the blocks are
typically small, the largest one having at most logarithmic size in the size
of the graph. This makes it possible to study subcritical classes rather
abstractly without explicitly fixing $\mathcal{B}$, and by now there are many
results that address the local as well the global structure of ’typical’
members of such classes [23, 7, 22, 35]. Here we extend this list of results
by providing linear-time exact-size samplers for many important classes
including cactus, outerplanar and series-parallel graphs; many other classes
for which there is a decomposition of the 2-connected graphs can be treated
analogously.

In order to apply our main result we begin with the following fact, which is a
simple consequence of the definition of subcritical classes.

######  Fact 5.2.

Let $\mathcal{C}$ be subcritical. Then $\mathcal{C}$ has the properties (A)
and (B) in the definition of a tame class of $\mathcal{R}$-enriched trees for
$\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$.

So, what remains to be done in order to obtain an expected linear-time exact-
size sampler for $\mathcal{R}$-enriched trees by applying Theorem 1.5 is to
verify the properties (C) and (D) in the definition of tame enriched trees for
the classes at hand. In particular, we have to show that
$|\mathcal{R}_{k}|=|\textsc{SET}\circ\mathcal{B}^{\prime}_{k}|$ can be
computed in time $e^{o(k)}$ and that we have a Boltzmann sampler for
$\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$. _Assuming_ for the moment
that this can be done (we will verify this condition for cacti graphs,
outerplanar graphs, and series-parallel graphs in the following subsections),
we may apply Theorem 1.5 that utilizes Algorithm 2.1 with the a random
variable $\xi$ that has distribution, see also (1.2),

(5.2)
$\displaystyle\mathbb{P}(\xi=k)=\frac{|\mathcal{R}_{k}|\rho_{\mathcal{C}}\mathcal{C}^{\bullet}(\rho_{\mathcal{C}})^{k}}{\mathcal{C}(\rho_{\mathcal{C}})k!},\quad\text{with
pgf}\quad\mathbb{E}[z^{\xi}]=\frac{\rho_{\mathcal{C}}\mathcal{R}(\mathcal{C}^{\bullet}(\rho_{\mathcal{C}})z)}{\mathcal{C}^{\bullet}(\rho_{\mathcal{C}})},$

to obtain a linear-time exact-size sampler for $\mathcal{R}$-enriched trees.
In order to obtain a linear-time exact-size sampler for $\mathcal{C}$ we need
to transform this enriched into a rooted graph and drop the root-vertex:

######  Algorithm 5.3.

(Uniform $n$ vertex graphs from a subcritical graph class $\mathcal{C}$) Let
$\mathcal{C}$ be subcritical and assume that properties (C) and (D) in the
definition of tame enriched trees are met. Then the following generates a
uniform $n$-vertex graph from $\mathcal{C}$ in expected time $O(n)$.

  1. (1)

Generate a uniform $n$-vertex
$\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$ enriched tree using
Algorithm 2.1.

  2. (2)

Transform the enriched tree into a rooted graph from $\mathcal{C}^{\bullet}$.

  3. (3)

Create an unrooted graph by forgetting which was the root vertex.

First, the algorithm is correct, since a uniform enriched tree corresponds to
a uniform rooted connected graph. Any $n$-vertex labelled graph corresponds to
$n$ rooted versions, hence forgetting the root vertex yields the uniform
distribution on $n$-vertex labelled unrooted graphs.

Second, Theorem 1.5 guarantees that generating a uniform $n$-vertex enriched
tree takes expected time $O(n)$. Transforming it into a graph takes expected
time $O(n)$ by the following lemma, hence Algorithm 5.3 runs in expected
linear time.

######  Lemma 5.4.

A uniformly selected $n$-vertex
$\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$ enriched tree may be
transformed into a rooted connected graph from $\mathcal{C}^{\bullet}$ in an
expected linear number of steps.

###### Proof.

Let $(T,(R_{v})_{v\in T})$ denote an $n$-vertex $\mathcal{R}$-enriched tree
for $\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$. We may construct the
associated rooted graph by traversing the tree $T$ in some order (for example
breadth-first-search) and gluing the respective blocks together as depicted in
Figure 3.

At any point in this traversal, when we arrive at a vertex $v\in T$ we glue
the blocks from $R_{v}$ to the graph constructed so far. If the graphs are
represented by adjacency lists, then the time required for this step is
bounded by a constant multiple of the number of edges in the blocks from
$R_{v}$. As the number of non-$*$-vertices of $R_{v}$ agrees with the number
$d_{T}^{+}(v)$ of children of $v$ in $T$, the number of edges in $R_{v}$ is at
most $O(d_{T}^{+}(v)^{2})$.

Hence the time required for transforming $(T,(R_{v})_{v\in T})$ into a graph
is bounded by a constant multiple of $\sum_{v\in T}d_{T}^{+}(v)^{2}$. Hence it
follows from Lemma 2.3 that for a uniformly selected $n$-vertex
$\mathsf{A}_{n}(\mathsf{T}_{n},(\mathsf{R}_{v})_{v\in\mathsf{T}_{n}})$ the
expected required time is bounded by a constant multiple of

$\mathbb{E}\left[\sum_{v\in\mathsf{T}_{n}}d^{+}_{\mathsf{T}_{n}}(v)^{2}\right].$

By identical arguments as for Equations (4.4), (4.5), and (4.6), it follows
that this bound belongs to $O(n)$ and the proof is complete. ∎

The following subsections are devoted to verifying (C) and (D) for the classes
of cactus, outerplanar and series-parallel graphs, which are all subcritical,
see for example [37]. Further minor-closed classes (such as the class of
graphs that contain no cycle of length at least five) that fall into the
present setting were described in [30], but we omit the details.

#### Cactus Graphs

A cactus graph is a graph in which each edge is contained in at most one
cycle, that is, the class of such graphs is the block-stable class in which
each every block is either an edge or a cycle. So, for this class we have

$\mathcal{B}=e+\textsc{CYC}(\mathcal{X}),\quad\text{and}\quad\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime},$

where $e$ is class of graphs that consists only of a single edge of size two.
We immediately obtain that, see the relations for generating functions in
Section 3.1 or directly in [37, Sec. 8.4],

$\mathcal{B}^{\prime}(x)=x+\frac{x^{2}}{2(1-x)},\quad\mathcal{R}(x)=(\textsc{SET}\circ\mathcal{B}^{\prime})(x)=e^{\mathcal{B}^{\prime}(x)}.$

In order to verify Condition (C) we have to show how to compute
$|\mathcal{R}_{k}|$ in time $e^{o(k)}$. In this case, the counting sequence
for $\mathcal{B}^{\prime}$ is explicit: we have $|\mathcal{B}^{\prime}_{1}|=1$
and $|\mathcal{B}^{\prime}_{k}|=k!/2$ for $k\geq 2$. Then, computing the
$k$-th coefficient of $e^{\mathcal{B}^{\prime}(x)}$ can readily be done in
polynomial (actual, at most cubic) time by using for example the recursive
method [34].

It remains to verify Condition (D). From the general principles for the
construction of Boltzmann samplers [24] we infer that a Boltzmann distributed
object from $\mathcal{R}$ contains a Poisson number of independent
$\mathcal{B}^{\prime}$ components, each of which is also Boltzmann
distributed. Moreover, a Boltzmann distributed object from
$\mathcal{B}^{\prime}$ is with some constant probability an edge, and with the
remaining probability a Boltzmann distributed cycle. To be completely explicit
in this example, the Boltzmann sampler for $\mathcal{R}$ is given by the
following algorithm.

######  Algorithm 5.5.

Boltzmann sampler $\Gamma\mathcal{R}(t)$ for the class of cactus graphs, where
$0\leq t<\rho_{\mathcal{R}}$.

  1. (1)

Let $\ell$ be Poisson distributed with parameter $\mathcal{B}^{\prime}(t)$.

  2. (2)

For each $1\leq k\leq\ell$ let independently $b^{\prime}_{i}$ be a random
graph from the Boltzmann distribution from $\mathcal{B}^{\prime}$ with
parameter $t$.

  3. (3)

Distribute uniformly at random labels from $[\sum_{1\leq
k\leq\ell}|b_{k}^{\prime}|]$ to $b^{\prime}_{1},\dots,b^{\prime}_{\ell}$ and
return the collection of relabeled $b^{\prime}_{1},\dots,b^{\prime}_{\ell}$.

Note that this algorithm is actually a _generic_ algorithm for sampling from
the Boltzmann distribution for a class
$\textsc{SET}\circ\mathcal{B}^{\prime}$, provided that we have a corresponding
sampler for $\mathcal{B}^{\prime}$. We will (re-)use this algorithm in the
following examples – outerplanar and series-parallel graphs – as well. It
remains to specify the Boltzmann sampler for $\mathcal{B}^{\prime}$.

######  Algorithm 5.6.

A Boltzmann sampler $\Gamma\mathcal{B}^{\prime}(t)$ for the class of connected
cactus graphs without a cut vertex, where $0\leq
t<\rho_{\mathcal{B}}=\rho_{\mathcal{R}}=1$.

  1. (1)

Let $h$ be equal to one with probability $t/\mathcal{B}^{\prime}(t)$ and zero
otherwise.

  2. (2)

If $h=1$ create an edge and otherwise a cycle with $2+d$ vertices, where $d$
is geometrically distributed with parameter $t$.

  3. (3)

Replace in the created graph the largest label with $\star$ and return.

#### Outerplanar Graphs

An outerplanar graph is a planar graph that can be embedded in such a way that
every vertex lies on the boundary of the outer face. In this case, the blocks
essentially correspond to edges and dissections of polygons, see for example
[37, Sec. 8.5] for the (well-known) following statement.

######  Lemma 5.7.

Let $\mathcal{B}$ be the class of all connected outerplanar graphs not
containing a cut-vertex. Then there is a bijection

$\mathcal{B}^{\prime}+\mathcal{B}^{\prime}\simeq\mathcal{X}+\mathcal{D},$

where the class $\mathcal{D}$ of dissections satisfies
$\mathcal{D}=\mathcal{X}+\textsc{SEQ}_{\geq 2}\circ\mathcal{D}$.

See Figure 4 for the specification of the class of dissections and the
corresponding bijection. Lemma 5.7 enables us to compute via the recursive
method [34] $[x^{k}]\mathcal{B}^{\prime}(x)$ and
$[x^{k}]e^{\mathcal{B}^{\prime}(x)}$ in time $e^{o(k)}$ with plenty of room to
spare; this verifies Condition (C). In order to verify (D) we use, as already
announced, Algorithm 5.5 as the Boltzmann sampler for
$\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$, where we additionally
need to specify the sampler for $\mathcal{B}^{\prime}$. This, in turn,
following the general Boltzmann sampling principles [24], can be realized by
making a two-way choice between $\mathcal{X}$ (with probability
$t/2\mathcal{B}^{\prime}(t)$) and $\mathcal{D}$ (with the remaining
probability), in complete analogy to what we did in Algorithm 5.6. Finally,
the sampler for $\mathcal{D}$ can be immediately obtained from the
specification: we make (again) a two-way choice between $\mathcal{X}$ (this
time with probability $t/\mathcal{D}(t)$) and $\textsc{SEQ}_{\geq
2}\circ\mathcal{D}$, where in the latter the number of $\mathcal{D}$
components follows a geometric distribution, that is conditioned to be $\geq
2$, with parameter $\mathcal{D}(t)$.

Figure 4. Recursive specification of the class $\mathcal{D}$.

#### Series-Parallel Graphs

In the case of series-parallel graphs we will use the following property of
the associated class $\mathcal{B}^{\prime}$ (connected series-parallel graphs
with no cut-vertex).

######  Lemma 5.8.

Let $\mathcal{X}$ be the class of graphs consisting of a single graph that is
an isolated vertex, $\mathcal{X}_{2}$ the class consisting of a single graph
that contains exactly two isolated vertices, and $e$ the class consisting of a
single graph that is an isolated edge, where the size of it is defined to be
zero. Then the class $\mathcal{B}^{\prime}$ has the decomposition

$\mathcal{B}^{\prime}+\mathcal{B}^{\prime}_{(rm)}\simeq
e\cdot\mathcal{X}+\mathcal{B}^{\prime}_{(r)}+\mathcal{B}^{\prime}_{(m)},$

where $\mathcal{B}^{\prime}_{(rm)}\subseteq\mathcal{B}^{\prime}$ and

$\mathcal{B}^{\prime}_{(r)}\simeq\mathcal{X}_{2}\cdot(e+\mathcal{P})^{2}\cdot\mathcal{D},\enspace\mathcal{B}^{\prime}_{(m)}\simeq\mathcal{X}\cdot\big{(}e\cdot\textsc{SET}_{\geq
2}(\mathcal{S})+\textsc{SET}_{\geq
3}(\mathcal{S})\big{)},\enspace\mathcal{B}^{\prime}_{(rm)}\simeq\mathcal{X}\cdot\mathcal{P}\cdot\mathcal{S},$

and

$\mathcal{D}\simeq
e+\mathcal{S}+\mathcal{P},\mathcal{S}=(e+\mathcal{P})\cdot\mathcal{X}\cdot\mathcal{D},\mathcal{P}=e\cdot\textsc{SET}_{\geq_{1}}(\mathcal{S})+\textsc{SET}_{\geq_{2}}(\mathcal{S}).$

This lemma is taken from [7, Sec. 6.1], where also the simple bijections –
that can be implemented in linear time – behind the given isomorphisms are
depicted. We will not repeat this here, since it would be a mere
reconstruction of what is done in [7]. Let us just mention that in Lemma 5.8
the classes $\mathcal{D},\mathcal{S}$ and $\mathcal{P}$ correspond to the
well-known classes of general, series and parallel networks, which are,
roughly speaking, 2-connected series-parallel graphs with a removed edge whose
endpoints are distinguished and do not contribute to the size. Their
decomposition has been known since the 1980’s. Moreover, the decomposition of
$\mathcal{B}^{\prime}$ follows from the general decomposition scheme of
connected graphs in their 3-connected components; for details we refer to our
primary source [7] and the paper [17].

With Lemma 5.8 at hand we proceed as usual in this section. We are again in a
position to compute via the recursive method [34]
$[x^{k}]\mathcal{B}^{\prime}(x)$ and $[x^{k}]e^{\mathcal{B}^{\prime}(x)}$ in
time $e^{o(k)}$ with room to spare; this verifies Condition (C). In order to
verify (D) we again use Algorithm 5.5 as the Boltzmann sampler for
$\mathcal{R}=\textsc{SET}\circ\mathcal{B}^{\prime}$, where the last remaining
step is to specify the sampler for $\mathcal{B}^{\prime}$. Using the
decomposition in Lemma 5.8 we readily obtain a Boltzmann sampler for
$\mathcal{B}^{\prime}+\mathcal{B}^{\prime}_{(rm)}$ from the general principles
for the construction of Boltzmann samplers from [24]. In addition to that,
since $\mathcal{B}^{\prime}_{(rm)}\subseteq\mathcal{B}^{\prime}$, we obtain a
sampler for $\mathcal{B}^{\prime}$ by rejection: if the sampled graph is in
$\mathcal{B}^{\prime}_{(rm)}$, we reject it with probability $1/2$ and repeat
the experiment.

###  5.2. Bienaymé–Galton–Watson trees conditioned on the number of vertices
with given degrees.

Throughout this section we fix a proper subset
$\Omega\subsetneqq\mathbb{N}_{0}$ satisfying $0\in\Omega$. See Remark 5.11
below for comments on this assumption. We let
$\Omega^{c}:=\mathbb{N}_{0}\setminus\Omega$ denote its complement. Let $\zeta$
be a random non-negative integer satisfying

(5.3) $\displaystyle\mathbb{P}(\zeta=0)>0,\quad\mathbb{P}(\zeta\geq
2)>0,\quad\text{and}\quad\mathbb{P}(\zeta\in\Omega)>0.$

Our aim in this section is to develop an expected linear-time sampler for a
tree $\mathsf{A}_{n}^{\Omega}$ that is distributed like a
$\zeta$-Galton–Watson $\mathsf{A}$ tree conditioned on having $n$ vertices
with outdegree in $\Omega$. Formally, letting $L_{\Omega}(\cdot)$ denote the
number of vertices with outdegree in $\Omega$, we set
$\mathsf{A}_{n}^{\Omega}=(\mathsf{A}\mid L_{\Omega}(\mathsf{A})=n)$. Of
course, we only consider integers $n$ for which this is well defined, that is,
where $\mathbb{P}(L_{\Omega}(\mathsf{A})=n)>0$. Furthermore, in order to
obtain a procedure that samples in linear time, we assume that

(5.4)
$\displaystyle\mathbb{E}[\zeta]=1\qquad\text{and}\qquad\mathbb{E}[(1+\epsilon)^{\zeta}]<\infty\quad\text{for
some $\epsilon>0$}.$

We also assume that the weight $\mathbb{P}(\zeta=k)$ may be computed in time
$\exp(o(k))$ for each $k\geq 0$, and that the probability
$\mathbb{P}(\zeta\in\Omega)$ is also given.

A result by Kortchemski [33, Thm. 8.1] asserts that for some constant
$c=c(\Omega)>0$

(5.5) $\displaystyle\mathbb{P}(L_{\Omega}(\mathsf{A})=n)\sim cn^{-3/2}.$

Hence, we may use Boltzmann sampling as described in the introduction
(rejection and truncation) to obtain a polynomial time exact-size sampler for
$\mathsf{A}_{n}^{\Omega}$. This performance is not optimal, hence our
motivation for describing a generator that accomplishes this in linear time.

The procedure we are going to describe is based on the fact that rooted trees
satisfying $L_{\Omega}(\cdot)=n$ correspond bijectively to $n$-vertex
$\mathcal{R}$-enriched trees for a specific class $\mathcal{R}$, see [25, 39].
Since we may generate $\mathcal{R}$-enriched trees in expected linear time via
Algorithm 2.1, and since the transformation to a plane tree with
$L_{\Omega}(\cdot)=n$ also takes expected linear time, we will arrive at
generator for $\mathsf{A}_{n}^{\Omega}$ that runs in expected time $O(n)$. To
be fully precise, we will use a straight-forward extension of Algorithm 2.1 to
weighted species, because $\mathsf{A}_{n}^{\Omega}$ is not (necessarily)
uniform among all plane trees $A$ with $L_{\Omega}(A)=n$. To wit, for a tree
$A$

(5.6)
$\displaystyle\mathbb{P}(\mathsf{A}_{n}^{\Omega}=A)=\frac{\mathbb{P}(\mathsf{A}=A)}{\mathbb{P}(L_{\Omega}(\mathsf{A})=n)}=\frac{1}{\mathbb{P}(L_{\Omega}(\mathsf{A})=n)}\prod_{v\in
A}\mathbb{P}(\zeta=d^{+}_{A}(v)).$

Consequently, the random $n$-vertex $\mathcal{R}$-enriched tree corresponding
to $\mathsf{A}_{n}^{\Omega}$ is not (necessarily) uniform. Furthermore, again
to be fully precise, Algorithm 2.1 is formulated for labelled structures. The
plane trees we generate here are asymmetric unlabelled structures. That is, it
is irrelevant whether we consider them as labelled or unlabelled, since they
have no non-trivial symmetries. Thus, we may safely ignore labels in this
section.

Let us start with the description of the weighted species $\mathcal{R}$ in
question. For each integer $k\geq 0$ we let $\mathcal{R}_{k}$ denote the
collection of all tuples $R=(y,x_{1},\ldots,x_{\ell})$ satisfying $\ell\geq
0$, $y\in\Omega$, $x_{1},\ldots,x_{\ell}\in\Omega^{c}-1$, and
$y+\sum_{i=1}^{\ell}x_{i}=k$. To each such tuple $R$ we assign a weight
$\gamma(R)$ by

(5.7)
$\displaystyle\gamma(R)=\mathbb{P}(\zeta=y)\prod_{i=1}^{\ell}\mathbb{P}(\zeta=x_{i}+1).$

It was shown in [25, 39] in a more general context that an ordered rooted tree
$A$ corresponds bijectively to a pair $(T,\beta)$ of an ordered rooted tree
$T$ with $n$ vertices, and a map $\beta$ that assigns to each inner vertex
$v\in T$ a structure $\beta(v)\in\mathcal{R}_{d^{+}_{T}(v)}$. Here $A$ is
constructed from $T$ by a blow-up procedure that replaces a vertex $v\in T$
and the edges to its children by a tree constructed from $\beta(v)$ as
illustrated in Figure 5.

Figure 5. Blow-up procedure of a vertex $v$ (red) having $5$ children and
decoration $\beta(v)=(2,2,0,3)$.

This correspondence is weight-preserving in the sense that the weight
$\mathbb{P}(\mathsf{A}=A)$ of the tree $A$ equals the weight $\prod_{v\in
T}\gamma(\beta(v))$ of the decorated tree $(T,\beta)$. Furthermore, the random
decorated tree $(\mathsf{T}_{n},\beta_{n})$ corresponding to the random tree
$\mathsf{A}_{n}^{\Omega}$ has the property that $\mathsf{T}_{n}$ is
distributed like a $\xi$-Galton–Watson tree conditioned on having $n$
vertices, where the random integer $\xi\geq 0$ has probability generating
function

(5.8)
$\displaystyle\mathbb{E}[z^{\xi}]=\left(\sum_{k\in\Omega}\mathbb{P}(\zeta=k)z^{k}\right)\left(1-\sum_{k\in\Omega^{c}}\mathbb{P}(\zeta=k)z^{k-1}\right)^{-1}.$

Conditional on $\mathsf{T}_{n}$, each decoration $\beta_{n}(v)$ gets drawn
from $\mathcal{R}_{d^{+}_{\mathsf{T}_{n}}(v)}$ with probability proportional
to its $\gamma$-weight, independently from the rest. Setting
$|\mathcal{R}_{k}|_{\gamma}=\sum_{R\in\mathcal{R}_{k}}\gamma(R)$ for each
$k\geq 0$, the ordinary generating series of the species $\mathcal{R}$ is
given by

(5.9) $\displaystyle\mathcal{R}(z):=\sum_{k\geq
0}|\mathcal{R}_{k}|_{\gamma}z^{k}=\mathbb{E}[z^{\xi}].$

See [25, 39, 44] for detailed justifications.

Our strategy for generating $\mathsf{A}_{n}^{\Omega}$ in expected time $O(n)$
is to generate the $\mathcal{R}$-enriched plane tree
$(\mathsf{T}_{n},\beta_{n})$ with Algorithm 2.1 and apply the blow-up
procedure. In order to verify that this works we have to do two things. First,
we have to check that the conditions of Algorithm 2.1 are met. Second, we have
to check that the expected time for applying the blow-up procedure to
$(\mathsf{T}_{n},\beta_{n})$ is $O(n)$. Note that there is a subtle difficulty
in the second step, because the number of vertices of
$\mathsf{A}_{n}^{\Omega}$ may be much larger than $n$ and the blow-up
procedure may take very long.

Let us start by verifying the conditions of Algorithm 2.1. Condition (5.4) and
the definition of the probability generating function of $\xi$ in (5.8) entail
that $\mathcal{R}(z)=\mathbb{E}[z^{\xi}]$ has radius of convergence
$\rho_{\mathcal{R}}>1$. (Specifically, $\rho_{\mathcal{R}}$ is the supremum of
the collection of all $x>0$ for which
$\mathbb{E}[x^{\zeta}{\mathbbm{1}}_{\zeta\in\Omega}]<\infty$ and
$\mathbb{E}[x^{\zeta-1}{\mathbbm{1}}_{\zeta\in\Omega^{c}}]<1$.) For any
parameter $t>0$ with $\mathcal{R}(t)<\infty$ we define a Boltzmann sampler
$\Gamma\mathcal{R}(t)$ with distribution

(5.10)
$\displaystyle\mathbb{P}(\Gamma\mathcal{R}(t)=R)=\frac{\gamma(R)t^{k(R)}}{\mathcal{R}(t)},\qquad
R\in\bigsqcup_{k\geq 0}\mathcal{R}_{k}$

for $k(R)\geq 0$ the unique integer with $R\in\mathcal{R}_{k(R)}$.

######  Algorithm 5.9.

A Boltzmann sampler $\Gamma\mathcal{R}(t)$:

  1. (1)

Generate a random integer $y$ with probability generating function

$\mathbb{E}[(zt)^{\zeta}{\mathbbm{1}}_{\zeta\in\Omega}]/\mathbb{E}[t^{\zeta}{\mathbbm{1}}_{\zeta\in\Omega}].$

  2. (2)

Generate a random integer $\ell$ with geometric distribution with parameter
$\mathbb{E}[t^{\zeta-1}{\mathbbm{1}}_{\zeta\in\Omega^{c}}]$.

  3. (3)

For each $1\leq i\leq\ell$ generate a random integer $x_{i}$ with probability
generating function given by
$\mathbb{E}[t^{\zeta-1}{\mathbbm{1}}_{\zeta\in\Omega^{c}}]^{-1}\sum_{k\in\Omega^{c}}\mathbb{P}(\zeta=k)(zt)^{k-1}$.

  4. (4)

Return $(y,x_{1},\ldots,x_{\ell})$.

For any integer $k\geq 0$ (satisfying $|\mathcal{R}_{k}|_{\gamma}>0$) we may
condition $\Gamma\mathcal{R}(t)$ on returning an element from
$\mathcal{R}_{k}$. The element generated in this way is drawn with probability
proportional to its $\gamma$-weight from $\mathcal{R}_{k}$. Since all
coordinates of a tuple from $\mathcal{R}_{k}$ are at most $k$, we may fix some
$K\geq k$ and work with a truncated version $\Gamma_{\leq K}\mathcal{R}(t)$
instead. That is, $\Gamma_{\leq K}\mathcal{R}(t)$ uses truncated versions
$(y\mid y\leq K)$ and $(x_{i}\mid x_{i}\leq K)$ instead, and conditioning
$\Gamma_{\leq K}\mathcal{R}(t)$ on producing an element from $\mathcal{R}_{k}$
also yields a random element that gets drawn with probability proportional to
its $\gamma$-weight. Furthermore, constructing $\Gamma_{\leq K}\mathcal{R}(t)$
only requires knowledge of $\mathbb{P}(\zeta\in\Omega)$ and the probabilities
$\mathbb{P}(\zeta=i)$ for $0\leq i\leq K$. We assumed that
$\mathbb{P}(\zeta\in\Omega)$ is given and that $\mathbb{P}(\zeta=i)$ may be
computed in $e^{o(i)}$ steps. Hence constructing $\Gamma_{\leq
K}\mathcal{R}(t)$ requires $e^{o(K)}$ preprocessing time. Running a single
instance of $\Gamma_{\leq K}\mathcal{R}(t)$ only requires constant time in
expectation. Moreover, $\mathbb{P}(\Gamma_{\leq
K}\mathcal{R}(t)\in\mathcal{R}_{k})\geq\mathbb{P}(\Gamma\mathcal{R}(t)\in\mathcal{R}_{k})$,
hence generating a random element from $\mathcal{R}_{k}$ using $\Gamma_{\leq
K}\mathcal{R}(t)$ is at least as fast as using $\Gamma\mathcal{R}(t)$.

We may now state our final algorithm for sampling $\mathsf{A}_{n}^{\Omega}$.

######  Algorithm 5.10.

A generator for $\mathsf{A}_{n}^{\Omega}$ that runs in expected time $O(n)$.

  1. (1)

Use Algorithm 2.4 to sample a Bienaymé–Galton–Watson tree $\mathsf{T}_{n}$
with offspring distribution $\xi$ conditioned on having $n$ vertices.

  2. (2)

Let $K$ denote the maximal outdegree of $\mathsf{T}_{n}$. For a fixed
$1<t_{0}<\rho_{\mathcal{R}}$ repeatedly call for each $v\in\mathsf{T}_{n}$ the
sampler $\Gamma_{\leq K}\mathcal{R}(t_{0})$ until it produces an object
$\beta_{n}(v)$ from $\mathcal{R}_{d^{+}_{\mathsf{T}_{n}}(v)}$.

  3. (3)

Perform the blow-up procedure illustrated in Figure 5 on
$(\mathsf{T}_{n},\beta_{n})$ to create $\mathsf{A}_{n}^{\Omega}$.

Here’s a justification why Algorithm 5.10 runs in expected time $O(n)$.

###### Proof.

We first show that Step (1) can be implemented in expected time $O(n)$. The
expression of $\mathbb{E}[z^{\xi}]$ in (5.8) allows us to compute
$\mathbb{P}(\xi=k)$ in $e^{o(k)}$ steps for any $k\geq 0$, since we assumed
$\mathbb{P}(\zeta=k)$ to be computable in $e^{o(k)}$ steps. Furthermore, using
$\mathbb{E}[\zeta]=1$ it follows from (5.8) that $\mathbb{E}[\xi]=1$, see [39,
Thm. 6] for details on the calculation. Moreover, $\xi$ has finite exponential
moments. Thus, Algorithm 2.4 samples from the distribution of $\mathsf{T}_{n}$
in expected time $O(n)$.

We proceed with the analysis of Step (2) in Algorithm 5.10. Determining the
maximum degree $K$ takes $O(n)$ steps. As argued before, constructing the
sampler $\Gamma_{\leq K}\mathcal{R}(t)$ takes $e^{o(K)}$ steps. Hence, the
expected time for doing so is bounded by

$\mathbb{E}[e^{o(K)}]\leq\mathbb{E}\left[\sum_{v\in\mathsf{T}_{n}}e^{o(d^{+}_{\mathsf{T}_{n}}(v)}\right].$

By identical arguments as for Equations (4.4), (4.5), and (4.6), and since
$\xi$ has an exponential tail, it follows that this bound belongs to $O(n)$.

The unique generating series $\mathcal{A}_{\mathcal{R}}(z)$ with
$\mathcal{A}_{\mathcal{R}}(z)=z\mathcal{R}(\mathcal{A}_{\mathcal{R}}(z))$
satisfies
$[z^{n}]\mathcal{A}_{\mathcal{R}}(z)=\mathbb{P}(L_{\Omega}(\mathsf{A})=n)$. By
(5.5) it follows that it has radius of convergence
$\rho_{\mathcal{A}_{\mathcal{R}}}=1$ and hence
$\mathcal{A}_{\mathcal{R}}(\rho_{\mathcal{A}_{\mathcal{R}}})=\mathcal{R}(1)=1$
(since $\mathcal{R}(z)=\mathbb{E}[z^{\xi}]$). We observed above that
$\rho_{\mathcal{R}}>1$. Thus, as justified in the proof of Thm. 1.5, we may
generate the decoration $\beta_{n}$ in expected time $O(n)$ by repeatedly
running $\Gamma_{\leq K}\mathcal{R}(t)$ for each vertex $v\in\mathsf{T}_{n}$
until we generate an element from $\mathcal{R}_{d_{\mathsf{T}_{n}}^{+}(v)}$.

We conclude with the analysis of the blow-up procedure in Step (3). The time
required for performing the blow-up of a vertex $v\in\mathsf{T}_{n}$ with
decoration $\beta_{n}(v)=(y(v),x_{1}(v),\ldots,x_{\ell(v)}(v))$ is bounded by
$O(d_{\mathsf{T}_{n}}^{+}(v)+\ell(v))$. Recall that the outdegrees of a tree
with $n$ vertices sum up to $n-1$. Summing over the $n$ vertices of
$\mathsf{T}_{n}$, the total time for performing all blow-up operations is
hence bounded by

$n-1+\sum_{v\in\mathsf{T}_{n}}\ell(v).$

Arguing analogously as for Equations (4.4), (4.5), and (4.6), only with
conditional moments, and using $t>1$ and $\mathbb{E}[\ell]<\infty$, it follows
that

$\displaystyle\mathbb{E}[\sum_{v\in\mathsf{T}_{n}}\ell(v)]$
$\displaystyle=O(n)\sum_{k\geq 0}\mathbb{E}[\ell\mid
y+x_{1}+\ldots+x_{\ell}=k]\mathbb{P}(\xi=k)$
$\displaystyle=O(n)\mathbb{E}[\ell]\sum_{k\geq
0}\frac{\mathbb{P}(\xi=k)}{\mathbb{P}(y+x_{1}+\ldots+x_{\ell}=k)}$
$\displaystyle=O(n)\sum_{k\geq
0}\frac{[z^{k}]\mathcal{R}(z)}{[z^{k}]\mathcal{R}(tz)}$ $\displaystyle=O(n).$

It follows that the expected time for performing the blow-up is $O(n)$. Hence
the total expected time for generating $\mathsf{A}_{n}^{\Omega}$ using
Algorithm 5.10 is $O(n)$. ∎

######  Remark 5.11.

Throughout, we assumed that $0\in\Omega$. Rizzolo’s [39] methods may be used
to generalize the procedure so that this assumption is no longer necessary.
However, the decorations and the blow-up procedure are far more technical in
the case $0\notin\Omega$. We leave the details to the reader, because all
applications of the present section to models of combinatorial structures
considered below are already covered by the special case $\Omega=\\{0\\}$.

####  5.2.1. Dissections of convex polygons

Let $\mathcal{D}=\mathcal{X}+\textsc{SEQ}_{\geq 2}\circ\mathcal{D}$ denote the
class of dissections of polygons, compare to Figure 4. In this section we
present a sampler generating uniform dissections $\mathsf{D}_{n}$ of size $n$
in expected time $O(n)$ as an application of Algorithm 5.10 for
$\mathsf{A}_{n}^{\Omega}$ with $\Omega=\\{0\\}$. First we need some notation
and an alternative viewpoint for the class $\mathcal{D}$. For $n\geq 3$ let
$P_{n}$ denote the polygon in the complex plane with $n$ sides whose vertices
are the $n$-th roots of unity. A dissection $D$ of $P_{n}$ is the union of all
sides of $P_{n}$ together with a collection of diagonals (connecting vertices
of $P_{n}$) that may only intersect in their endpoints. Then $\mathcal{D}_{n}$
contains all dissections of $P_{n+1}$. See the first two images in Figure 6
for an example.

Figure 6. From left to right: the polygon $P_{8}$, a dissection in
$\mathcal{D}_{7}$, the bijection $\Phi$ applied to this dissection and the
corresponding tree.

In order to specify a sampler for $\mathsf{D}_{n}$ (the uniform distribution
on $\mathcal{D}_{n}$) we exploit the following fact that can be found for
instance in [18, Prop. 2.2]. There is a bijection $\Phi$ between
$\mathcal{D}_{n}$ and rooted plane trees with $n$ leaves where no node has
outdegree $1$. We abbreviate this set of trees by $\mathcal{H}_{n}$. Given a
dissection $D\in\mathcal{D}_{n}$ the tree $\Phi(D)\in\mathcal{H}_{n}$ is
constructed as follows, see also the transition from the third to the fourth
image in Figure 6. First place a vertex in each of the faces of $D$ and
outside each side of $P_{n+1}$. Then join any two vertices whose corresponding
faces share a common edge. Let the root be the vertex connected to the vertex
outside of the side connecting vertex $1$ with
$\mathrm{e}^{2\pi\mathrm{i}/(n+1)}$ and delete this vertex and its adjacent
edge. Vice versa given a tree $T\in\mathcal{H}_{n}$ it is straightforward to
obtain the corresponding dissection $\Phi^{-1}(T)\in\mathcal{D}_{n}$ as
depicted in the example (third and fourth image) in Figure 6.

It was shown in [18] that there is a model of Galton-Watson-trees in
$\mathcal{H}_{n}$ corresponding to uniform dissections. More concretely, for
$c\in(0,1/2)$ consider the distribution of a random variable $\zeta$ given by

$\mathbb{P}\left(\zeta=0\right)=\frac{1-2c}{1-c},\quad\mathbb{P}\left(\zeta=1\right)=0\quad\text{and}\quad\mathbb{P}\left(\zeta=k\right)=c^{k-1}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\ \leavevmode\nobreak\ k\geq
2.$

Denote by $\mathsf{A}_{n}$ the Galton-Watson tree with offspring distribution
$\zeta$ and being conditioned on having $n$ leaves. Note that this corresponds
to $\mathsf{A}_{n}^{\Omega}$ in the previous section in the special case
$\Omega=\\{0\\}$. Then $\mathsf{A}_{n}$ has the same distribution as
$\Phi(\mathsf{D}_{n})$ for any $c\in(0,1/2)$ according to [18, Prop. 2.3].
With this at hand, the sampler for $\mathsf{D}_{n}$ involves two steps.

######  Algorithm 5.12.

Uniform dissection $\mathsf{D}_{n}$ from $\mathcal{D}_{n}$.

  1. (1)

Use Algorithm 5.10 to generate $\mathsf{A}_{n}$.

  2. (2)

Translate $\mathsf{A}_{n}$ to $\Phi^{-1}(\mathsf{A}_{n})$.

In Step $(1)$ of Algorithm 5.12 we generate a degree sequence
$(d_{1},\dots,d_{K})$ for some $K\in\mathbb{N}$ representing the rooted plane
tree $\mathsf{A}_{n}$ with $n$ leaves (and $K+1$ vertices), compare to (2.1).
To state a complete sampler for $\mathsf{D}_{n}$ we still need to clarify a
subroutine for Step $(2)$ translating this sequence into the corresponding
dissection.

######  Algorithm 5.13.

Translating a degree sequence $(d_{1},\dots,d_{K})$ to the corresponding
dissection.

  1. (1)

Create a directed cycle with $d_{1}+1$ vertices labelled counterclockwise by
$\\{1,\dots,d_{1}+1\\}$. Let $E_{1}=((1,2),(2,3),\dots,(d_{1}+1,1))$ be the
sequence of edges.

  2. (2)

For $2\leq i\leq K$ set $E_{i}=E_{i-1}$ if $d_{i}=0$. If $d_{i}>0$ (implying
that $d_{i}\geq 2$) do the following. Let $(v_{1},v_{2})$ be the $i$-th edge
in the sequence $E_{i-1}$. Create a directed cycle of size $d_{i}+1$ such that
one edge is $(v_{1},v_{2})$. Label the remaining vertices counterclockwise
(starting at $v_{2}$) with successive labels in $\mathbb{N}$ which have not
been used so far. Append the newly created edges counterclockwise to $E_{i-1}$
to obtain $E_{i}$.

  3. (3)

Let $V$ contain all the labels in $E_{K}$ and let $E$ be the set of edges in
$E_{K}$. Return the graph $(V,E)$. (To draw the dissection in the way defined
above embed the graph $(V,E)$ into the complex plane such that its vertices
are the $n$-th roots of unity, the vertex with label $1$ sits at $1$ and all
the edges are non-crossing. Drop the labels afterwards.)

######  Theorem 5.14.

Choosing $c=1-2^{-1/2}$ Algorithm 5.12 has expected runtime $O(n)$.

###### Proof.

Per definition of $\zeta$ we have that $\mathbb{P}\left(\zeta=0\right)>0$ and
$\mathbb{P}\left(\zeta\geq 2\right)>0$ verifying (5.3). The choice
$c=1-2^{-1/2}$ further guarantees that $\mathbb{E}\left[\zeta\right]=1$ and
for $\varepsilon>0$ such that $(1+\varepsilon)c<1$ we have that

$\mathbb{E}\left[(1+\varepsilon)^{\zeta}\right]=(1+\varepsilon)\frac{1-2c}{1-c}+c^{-1}\sum_{k\geq
2}(1+\varepsilon)^{k}c^{k}<\infty.$

Hence Equation (5.4) is valid. Finally, the probability
$\mathbb{P}\left(\zeta=k\right)$ can be computed in $\mathrm{e}^{o(k)}$ steps
as $c$ is explicitly given. We deduce that all conditions at the beginning of
Section 5.2 are fulfilled so that Algorithm 5.10, Step $(1)$ of Algorithm 5.12
respectively, runs in expected time $O(n)$.

Let us next explain why Step $(2)$ or equivalently Algorithm 5.13 runs in
expected time $O(n)$ for any degree sequence $(d_{1},\dots,d_{K})$
corresponding to a tree $T\in\mathcal{H}_{n}$. First of all note that there is
no vertex with outdegree $1$ in $T$ implying that $K\leq 2n$ so that we have
$O(n)$ iterations in steps $(1)$ and $(2)$ of Algorithm 5.13. The number of
created edges is $n+1$ (for the edges of the polygon of length $n+1$) plus the
additional edges accounting for the diagonals of the dissection. But in each
iteration of Step $(2)$ at most one diagonal edge (if $d_{i}>0$) is created so
that the total number of edges is $O(n+1+K)=O(n)$. As each edge is only
created once the total time needed to finish Step $(2)$ is $O(n)$. ∎

###  5.3. Subcritical substitution-closed classes of permutations

An $n$-sized permutation $\sigma:[n]\to[n]$ may be denoted in multiple ways,
for example by the sequence of numbers $\sigma(1)\sigma(2)\ldots\sigma(n)$, or
graphically by a diagram corresponding to the collection of points
$\\{(i,\sigma(i))\mid i\in[n]\\}$. Given permutations $\nu_{1},\ldots,\nu_{n}$
of arbitrary sizes $k_{1},\ldots,k_{n}\geq 1$, we may form the
$(k_{1}+\ldots+k_{n})$-sized permutation $\sigma[\nu_{1},\ldots,\nu_{n}]$ by
performing a _substitution_ -operation, where for each $1\leq i\leq n$ the
point $(i,\sigma(i))$ gets replaced by the diagram of the permutation
$\nu_{i}$, and the rows and columns are rescaled accordingly. This is best
explained by Figure 7 which depicts an example.

Figure 7. The substitution $\sigma[\nu_{1},\ldots,\nu_{4}]$ for $\sigma=1324$,
$\nu_{1}=1$, $\nu_{2}=12$, $\nu_{3}=132$, and $\nu_{4}=21$.

A class $\mathcal{C}$ of permutations is called _substitution-closed_ if
$\sigma,\nu_{1},\ldots,\nu_{n}\in\mathcal{C}$ implies
$\sigma[\nu_{1},\ldots,\nu_{n}]\in\mathcal{C}$. Letting
$\mathcal{C}_{n}\subset\mathcal{C}$ denote the subset of $n$-sized
permutations in $\mathcal{C}$, the ordinary generating function of
$\mathcal{C}$ is given by $\mathcal{C}(x)=\sum_{n\geq
1}|\mathcal{C}_{n}|x^{n}$. A permutation $\sigma$ of size at least $3$ is
called _simple_ , if it cannot be represented as a substitution of
permutations, except of course in a trivial manner by
$\sigma=\sigma[1,\ldots,1]$ and $\sigma=1[\sigma]$. We let
$\mathcal{S}\subset\mathcal{C}$ denote the subclass of permutations that are
simple and lie in $\mathcal{C}$.

######  Definition 5.15.

We call the substitution-closed class $\mathcal{C}$ of permutations
_subcritical_ , if the radius of convergence $\rho_{\mathcal{S}}$ of the
ordinary generating series $\mathcal{S}(z)$ satisfies

(5.11)
$\displaystyle\mathcal{S}^{\prime}(\rho_{\mathcal{S}})>\frac{2}{(1+\rho_{\mathcal{S}})^{2}}-1.$

This is always satisfied if $\rho_{\mathcal{S}}=\infty$, for which the right-
hand side equals $-1$ per convention. In particular, it encompasses the case
when $\mathcal{S}$ is finite. The subclass $\mathcal{S}$ of simple
permutations plays an analogous role for substitution-closed classes of
permutations as the class of blocks does for block-stable classes of graphs.
Inequality (5.11) is the analogon to the subcriticality condition in
Definition (5.1) for subcritical classes of graphs. The condition also crops
up in work on permutron limits [3, 15].

If a Boltzmann sampling procedure is available for the subclass $\mathcal{S}$
of simple permutations (for example, when this class if finite), and if the
class $\mathcal{C}$ is subcritical in the sense defined above, then a
Boltzmann sampler for $\mathcal{C}$ may be constructed that lets us generate a
uniform $n$-sized permutation from $\mathcal{C}$ in expected time $O(n^{2})$.
In the following, we pursue a different approach that allows us to perform
this task in time $O(n)$ instead, assuming that we may compute the number
$[x^{k}]\mathcal{S}(x)$ of simple permutations of size $k$ in $\mathcal{C}$ in
at most $e^{o(k)}$ steps.

For all $k\geq 2$ we define the permutations $\oplus_{k}=1\ldots k$ and
$\ominus_{k}=k\ldots 1$. We call a permutation _$\oplus$ -indecomposable_ if
it cannot be expressed as a substitution $\oplus_{k}(\nu_{1},\ldots,\nu_{k})$
for some $k\geq 2$. The term _$\ominus$ -indecomposable_ is defined
analogously. As detailed in [1, Prop. 2], any permutation in $\mathcal{C}$ of
size at least $2$ may be uniquely represented as a substitution
$\sigma[\nu_{1},\ldots,\nu_{n}]$ where $\nu_{1},\ldots,\nu_{n}\in\mathcal{C}$
and exactly one of the following three cases hold:

  1. (a)

$\sigma\in\mathcal{S}$, or

  2. (b)

$\sigma\in\\{\oplus_{k}\mid k\geq 2\\}$ and $\nu_{1},\ldots,\nu_{k}$ are
$\oplus$-indecomposable, or

  3. (c)

$\sigma\in\\{\ominus_{k}\mid k\geq 2\\}$ and $\nu_{1},\ldots,\nu_{k}$ are
$\ominus$-indecomposable.

This leads to unique representations of permutations from the class
$\mathcal{C}$ as canonical decomposition trees, which are plane trees whose
inner vertices are decorated with permutations from
$\mathcal{S}\cup\bigcup_{k\geq 2}\\{\oplus_{k},\ominus_{k}\\}$, such that no
two adjacent vertices may carry both an $\oplus$-decoration or both an
$\ominus$-decoration. If the permutation is of the form
$\sigma[\nu_{1},\ldots,\nu_{n}]$ as in one of the three discussed cases, then
the root of the associated tree is decorated with $\sigma$, and its $n$
children are roots of the (recursively defined) canonical decomposition trees
corresponding to the permutations $\nu_{1},\ldots,\nu_{k}$. See Figure 8 for
an illustration. This way, the size of the permutation corresponds to the
number of leaves of the associated canonical decomposition tree.

Figure 8. The permutation $46518723$ and its associated canonical
decomposition tree.

Our first observation describes how the permutation associated to a canonical
decomposition tree may be computed in linear time.

######  Lemma 5.16.

A canonical decomposition tree with $n$ leaves may be transformed into a
permutation in $O(n)$ steps.

###### Proof.

A canonical decomposition tree with $n$ leaves is given by a plane tree $T$
with $n$ leaves, together with a family of permutations $(\sigma_{v})_{v}$
from $\mathcal{S}\cup\bigcup_{k\geq 2}\\{\oplus_{k},\ominus_{k}\\}$ with the
index $v$ ranging over all inner vertices of $T$. Of course, $T$ and
$(\sigma_{v})_{v}$ are subject to the discussed constraints, so that the size
of $\sigma_{v}$ is equal to the number of children of $v$ for each inner
vertex $v$, and so that no two adjacent inner vertices of $T$ are both
decorated with a $\oplus$-permutation, or both with a $\ominus$-permutation.

#### First step: assign labels to the leaves.

Note that any inner vertex of $T$ has at least two children, because all
permutations from $\mathcal{S}\cup\bigcup_{k\geq
2}\\{\oplus_{k},\ominus_{k}\\}$ have size at least $2$. Hence the total number
of vertices in such a tree with $n$ leaves is at most $2n-1$. Hence we may
assign numeric labels from $1$ to $n$ to the leaves of $T$ according to their
lexicographic order in $O(n)$ time by performing a depth-first-search
traversal.

#### Second step: recursively calculate a linked list of numbers.

The next step is to form a linked list that represents the inverse of the
permutation that we want to compute. We use a data type that additionally has
pointers to the first and last element of the list, so that we may concatenate
two such lists in a bounded number of steps, regardless of their length. See
[32, Ch. 2] for details on this data structure.

The algorithm works recursively: If the tree consists of a single vertex, we
return its numeric label as a linked list of length $1$. If it is not, then
the root is decorated with some permutation $\sigma$, and has some number
$d\geq 2$ of children. The decorated fringe subtrees $T_{1},\ldots,T_{d}$
corresponding to these children have disjoint leaf label sets, and calling the
algorithm recursively for each returns linked lists $L_{1},\ldots,L_{d}$. The
inverse of a permutation may be computed in linear time, hence we may
calculate the inverse $\sigma^{-1}$ of $\sigma$ in $O(d)$ steps. The employed
datatype allows us to form the concatenation $L$ of
$L_{\sigma^{-1}(1)},\ldots,L_{\sigma^{-1}(d)}$ in that order in $O(d)$ steps.

Now, the number of steps required for this algorithm is $O(d)$ plus the number
of steps required for the recursive calls to compute $L_{1},\ldots,L_{d}$.
Hence, each vertex of $T$ contributes an $O(d^{+}_{T}(v))$ number of steps,
with $d^{+}_{T}(v)$ denoting its number of children. Hence the total number of
steps required to compute the list $L$ is $O(\sum_{v\in T}d^{+}_{T}(v))=O(n)$.

#### Third step: return the inverse of the permutation associated to that
list.

The list $L$ computed in the second step corresponds to a permutation that for
each $1\leq i\leq n$ maps the number $i$ to the $i$th element of $L$. The
inverse $\sigma$ of this permutation may be calculated in $O(n)$ steps.

#### Correctness and time complexity

We have argued that each of the three steps may be completed in $O(n)$ steps,
hence the algorithm completes in linear time. In order to check that it
actually computes the permutation associated to $(T,(\sigma_{v})_{v})$, simply
note in the second step that if for each $1\leq i\leq d$ the list $L_{i}$
represents the inverse of the permutation corresponding to the tree $T_{i}$,
then the concatenation $L$ of $L_{\sigma^{-1}(1)},\ldots,L_{\sigma^{-1}(d)}$
represents the inverse of the permutation corresponding to $T$. Hence
correctness of the algorithm follows by structural induction.

#### A closing example

Let us close with an example. The canonical decomposition tree $T$ in Figure 8
consists of an outdegree $d=4$ root vertex decorated by the permutation
$\sigma=3142$, with $4$ decorated trees $T_{1},\ldots,T_{4}$ attached to it.
The first step of the algorithm labels the leaves from $1$ to $8$ in
lexicographic order, that is, from left to right in the drawing in Figure 8.
The lists corresponding to the subtrees in the second step are given by
$L_{1}=(1,3,2)$, $L_{2}=(4)$, $L_{3}=(6,5)$, and $L_{4}=(7,8)$. The inverse of
$\sigma$ is given by $\sigma^{-1}=2413$. Hence the list $L$ is given by the
concatenation of $L_{2},L_{4},L_{1},L_{3}$, that is, $L=(4,7,8,1,3,2,6,5)$.
Its inverse is the permutation $47813265$ corresponding to the tree $T$. ∎

The drawback of canonical decomposition trees is that the constraints for the
decoration of the children of a vertex depend on the decoration of the vertex
itself. This violates one of the requirements of $\mathcal{R}$-enriched trees,
where the decoration of a vertex is only constrained by the number of its
children.

For this reason, packed trees were introduced in [15]. The idea is to encode
canonical decomposition trees by trees with different kinds of decorations. To
this end, we define a _gadget_ as a special kind of canonical decomposition
tree, with the additional requirements that it has height at most $2$, and the
root is an internal vertex decorated by a simple permutation, and each child
of the root is either a leaf or an internal vertex decorated by an increasing
permutation from $\\{\oplus_{k}\mid k\geq 2\\}$. The size of a gadget is its
number of leaves. We define the class $\mathcal{Q}$ as the union of the
collection of all gadgets and the collection $\\{\circledast_{k}\mid k\geq
2\\}$ of formal objects, the index $k$ denoting the formal size of such an
object $\circledast_{k}$. Thus, the ordinary generating series of the class
$\mathcal{Q}$ is given by

(5.12)
$\displaystyle\mathcal{Q}(x)=\frac{x^{2}}{1-x}+\mathcal{S}\left(\frac{x}{1-x}\right).$

A _packed tree_ is a rooted plane tree where each internal vertex is decorated
by an object from the class $\mathcal{Q}$, with the size of the object
matching the number of children of the vertex. The size of a packed tree is
defined to be its number of leaves.

Figure 9. A canonical decomposition tree and its corresponding packed tree.

As argued in [15, Prop. 2.15], there is a size-preserving bijection between
the class of packed trees and the subclass of canonical decomposition trees
whose root is not decorated by an increasing permutation from
$\\{\oplus_{k}\mid k\geq 2\\}$. That is, those that correspond to
$\oplus$-indecomposable permutations in $\mathcal{C}$. Let us call such
decomposition trees $\oplus$-indecomposable, and define
$\ominus$-indecomposable decomposition trees analogously.

Our next observation tells us that the number steps required for applying this
bijection is linear in the size of the input.

######  Lemma 5.17.

The $\oplus$-indecomposable canonical decomposition tree corresponding to a
given packed tree with $n$ leaves may be computed in $O(n)$ steps.

###### Proof.

The canonical decomposition tree associated to a packed tree $P$ gets
constructed in two steps:

#### First step: Blow-up gadgets.

We perform a blow-up procedure where each internal vertex $v$ of $P$ that is
decorated by a gadget $G$ gets replaced by its gadget. That is, we delete $v$
and add an edge between its parent and the root of $G$. For each integer $i$
from $1$ to the number $d$ of children of $v$ we merge the root of the $i$-th
subtree attached to $v$ with the $i$-th leaf of $G$.

The time required to perform a single blow-up of $v$ is $O(d)$. Hence the
total time required for all blow-ups is linear in the number of vertices of
$P$. Since $P$ has $n$ leaves and each internal vertex has at least two
children, its number of vertices is at most $2n-1$. Hence the time required
for the first step is $O(n)$.

#### Second step: Replace $\circledast$-signs.

We traverse the vertices of the tree $\tilde{P}$ resulting from the first step
in a breadth-first-search order. Whenever we encounter a vertex $v$ that is
decorated by $\circledast_{k}$ for some $k\geq 2$, we replace
$\circledast_{k}$ by either $\ominus_{k}$ or $\oplus_{k}$ according to the
following rule. If $v$ is the root of $\tilde{P}$, then we replace it with
$\ominus_{k}$. If $v$ is not equal to the root of $\tilde{P}$, then its parent
is decorated with $\ominus_{k}$ or $\oplus_{k}$ (possibly due to modifications
done in prior steps of the breadth-first-search traversal), and we replace the
decoration of $v$ with the opposite sign of its parent.

The time required for this is linear in the number of vertices of $\tilde{P}$.
As $\tilde{P}$ has $n$ leaves and each internal vertex has at least two
children, it has at most $2n-1$ vertices. Hence the time required for the
second step is $O(n)$.

∎

Note that packed trees also correspond bijectively to $\ominus$-indecomposable
canonical decomposition trees. The only difference to the bijection with
$\oplus$-indecomposable permutations here is that in the second step we
replace the decoration of the root by $\oplus_{k}$ in case that it previously
carried $\circledast_{k}$ for some $k\geq 2$.

Next, we are going to describe how uniform packed trees may be generated in
expected linear time. The class $\mathcal{P}$ of packed trees (with leaves as
atoms) is related to the class $\mathcal{Q}$ via

(5.13) $\displaystyle\mathcal{P}(x)=x+\mathcal{Q}(\mathcal{P}(x)).$

This identifies the class $\mathcal{P}$ as $\mathcal{Q}$-enriched Schröder
parenthesizations, which are in bijection to
$\textsc{SEQ}(\mathcal{Q}/\mathcal{X})$-enriched trees by the Ehrenborg–Méndez
bijection [25]. (Here $\mathcal{Q}/\mathcal{X}$ denotes the class constructed
from $\mathcal{Q}$ by shifting the sizes of the objects so that its generating
series is given by $\mathcal{Q}(x)/x$.) We hence have two options for
generating them in expected linear time. The first is to employ this bijection
and apply our main Algorithm 2.1 for
$\mathcal{R}=\textsc{SEQ}(\mathcal{Q}/\mathcal{X})$. The second option is to
employ a variant of this algorithm that uses Galton–Watson trees conditioned
on their number of leaves instead, as opposed to the total number of vertices.
This is possible, since Algorithm 5.10 allows us to sample these trees in
expected linear time. From our viewpoint it is more natural to go with the
second option.

Throughout the rest of this section let us assume that the class $\mathcal{C}$
is subcritical, that is, Inequality (5.11) holds. We let $\rho_{\mathcal{P}}$
denote the radius of convergence of $\mathcal{P}(x)$. It was shown in [15,
Proof of Prop. 3.5 and Sec. 3.1] that in this case $\mathcal{Q}(x)$ has a
positive radius of convergence $\rho_{\mathcal{Q}}>0$, and that there is a
unique number $0<\kappa\leq\rho_{\mathcal{S}}$ with

(5.14) $\displaystyle\mathcal{S}^{\prime}(\kappa)=2/(1+\kappa)^{2}-1.$

Moreover, it was shown that
$y:=\mathcal{P}(\rho_{\mathcal{P}})=\kappa/(1+\kappa)\in]0,\rho_{\mathcal{S}}[$
satisfies $\mathcal{Q}^{\prime}(y)=1$, and we may define a random non-negative
integer $\zeta$222The constant $y$ and the random variable $\zeta$ defined
here correspond to the constant $t_{0}$ and the random variable $\xi$ defined
in [15, Prop. 3.5]. with probability generating function

(5.15)
$\displaystyle\mathbb{E}[x^{\zeta}]=1-\mathcal{Q}(y)/y+\mathcal{Q}(xy)/y$

having radius of convergence strictly larger than $1$, so that $\zeta$ has
finite exponential moments. It follows that $\zeta$ satisfies

(5.16) $\displaystyle\mathbb{E}[\zeta]=\mathcal{Q}^{\prime}(y)=1.$

As shown in [44, Sec. 6.4] for general enriched Schröder parenthesizations,
and noted in [15, Lem. 3.4, Sec. 3.4] for the special case of the present
setting, a uniform packed tree may be generated by conditioning a
$\zeta$-Galton–Watson tree on having $n$ leaves, and adding uniform
$\mathcal{Q}$-decorations to each internal vertex in the second step. The
result of the present work enable us to perform this in expected linear time,
in analogy to Algorithm 2.1. Suppose that for some $t_{0}>0$ with
$\mathcal{P}(\rho_{\mathcal{P}})<t_{0}<\rho_{\mathcal{S}}$ there is a
Boltzmann sampler $\Gamma\mathcal{Q}(t_{0})$ that runs in expected finite
time. Recall that we assume that $[x^{k}]\mathcal{S}(x)$ (and hence also
$\mathbb{P}(\zeta=k)$) may be computed in $\exp(o(k))$ steps.

######  Algorithm 5.18.

A generator for a uniform packed tree with $n$ leaves that runs in expected
time $O(n)$.

  1. (1)

Generate a $\zeta$-Galton–Watson tree $\mathsf{A}_{n}$ conditioned having $n$
leaves using Algorithm 5.10 for the special case $\Omega=\\{0\\}$.

  2. (2)

For each internal vertex $v$ of $\mathsf{A}_{n}$ let $d\geq 2$ denote its
number of children and select a uniform $d$-sized $\mathcal{Q}$-decoration by
repeatedly running the Boltzmann sampler $\Gamma\mathcal{Q}(t_{0})$ until it
produces a $d$-sized object.

Here is a justification why this runs in expected linear time:

###### Proof.

The first step terminates in expected time $O(n)$ as shown in Algorithm 5.10.
The fact that adding decorations using a Boltzmann sampler above the critical
threshold $\mathcal{P}(\rho_{\mathcal{P}})$ also takes expected time $O(n)$
may be verified by recalling that the $\zeta$-Galton–Watson tree
$\mathsf{A}_{n}$ with $n$ leaves is constructed in Algorithm 5.10 from an
associated $\xi$-Galton–Watson tree with $n$ vertices, enabling us to adapt
the arguments of the proof of Algorithm 2.1 in a straight-forward way. ∎

Recall that a packed tree corresponds bijectively to an
$\ominus$-indecomposable canonical decomposition tree, and likewise to an
$\oplus$-indecomposable canonical decomposition tree.

######  Algorithm 5.19.

A generator for a uniform $n$-sized permutation from the subcritical class
$\mathcal{C}$ that runs in expected time $O(n)$.

  1. (1)

Use Algorithm 5.18 twice to sample two independent $n$-sized packed trees
$P_{1}$ and $P_{2}$. If both have a root decorated by $\circledast$-symbols,
discard them and try again until at least one of the two has a root decorated
by a gadget.

  2. (2)

We make a case distinction.

    1. (a)

If both $P_{1}$ and $P_{2}$ have a root decorated by a gadget, use the
procedure from Lemma 5.17 to compute the canonical decoration tree $T$
corresponding to $P_{1}$.

    2. (b)

If $P_{1}$ has a root decorated by a gadget, but $P_{2}$ doesn’t, then use the
procedure from Lemma 5.17 to compute the canonical decoration
$\ominus$-indecomposable tree $T$ corresponding to $P_{2}$.

    3. (c)

If $P_{2}$ has a root decorated by a gadget, but $P_{1}$ doesn’t, then use
(minor adaption of) the procedure from Lemma 5.17 to compute the canonical
decoration $\oplus$-indecomposable tree $T$ corresponding to $P_{1}$.

  3. (3)

Use the procedure from Lemma 5.16 to compute the permutation corresponding to
the canonical decomposition tree $T$. Return this permutation.

###### Proof.

First, let us verify that this algorithm actually samples a uniform
permutation from $\mathcal{C}$. The generating series $\mathcal{T}(x)$ for
canonical trees (identical to $\mathcal{C}(x)$) may be split up into three
series,

$\mathcal{T}(x)=\mathcal{T}_{\oplus}(x)+\mathcal{T}_{\ominus}(x)+\mathcal{T}_{S}(x),$

depending on whether the root is decorated with an $\oplus$-symbol, and
$\ominus$-symbol, or a simple permutation from $\mathcal{S}$. By symmetry it
holds that

$\mathcal{T}_{\oplus}(x)=\mathcal{T}_{\ominus}(x).$

A packed tree whose root is decorated with a $\circledast$-symbol may be
interpreted either as an element from $\mathcal{T}_{\oplus}$ or from
$\mathcal{T}_{\ominus}$. A packed tree whose root is decorated by a gadget
corresponds to a canonical decoration tree from $\mathcal{T}_{S}$.

Hence $a_{n}=[x^{n}]\mathcal{T}_{\oplus}(z)=[x^{n}]\mathcal{T}_{\ominus}(x)$
equals the number of packed trees with a $\circledast$-root, and
$b_{n}=[x^{n}]\mathcal{T}_{S}(x)$ equals the number of packed trees with a
gadget root. The canonical tree $T$ generated in the first two steps of the
procedure satisfies

$\mathbb{P}(T\in\mathcal{T}_{S})=\left(\frac{b_{n}}{a_{n}+b_{n}}\right)^{2}\left(1-\left(\frac{a_{n}}{a_{n}+b_{n}}\right)^{2}\right)^{-1}=\frac{b_{n}}{2a_{n}+b_{n}}.$

Likewise,

$\mathbb{P}(T\in\mathcal{T}_{\ominus})=\mathbb{P}(T\in\mathcal{T}_{\oplus})=\frac{a_{n}b_{n}}{(a_{n}+b_{n})^{2}}\left(1-\left(\frac{a_{n}}{a_{n}+b_{n}}\right)^{2}\right)^{-1}=\frac{a_{n}}{2a_{n}+b_{n}}.$

Conditional on belonging to either of these three classes the tree $T$ is
uniformly distributed. Hence $T$ is uniformly distributed among all canonical
decomposition trees with $n$ leaves. Consequently, the Algorithm produces a
uniform $n$-sized permutation from the class $\mathcal{C}$.

As for the performance of this algorithm, note that the number of pairs
$(P_{1},P_{2})$ we need to sample in the first step follows a geometric
waiting time for an event with probability
$1-\left(\frac{a_{n}}{a_{n}+b_{n}}\right)^{2}$. By for example [15, Eq. (12),
(13)] we know that $c_{n}:=[x^{n}]\mathcal{T}(x)=2a_{n}+b_{n}$ satisfies
$c_{n}\sim(a_{n}+b_{n})/(1-\mathcal{P}(\rho_{\mathcal{P}}))^{2}$ with
$\mathcal{P}(\rho_{\mathcal{P}})\in]0,1[$. Dividing by $a_{n}+b_{n}$ on both
sides it follows that

$\lim_{n\to\infty}\frac{a_{n}}{a_{n}+b_{n}}=\frac{1}{(1-\mathcal{P}(\rho_{\mathcal{P}}))^{2}}-1\in]0,1[.$

Hence we need an expected finite number of pairs, each of which may be sampled
with an expected time $O(n)$ by Algorithm 5.18. Hence the first step takes
time $O(n)$ in expectation. The time for the second step admits a
deterministic $O(n)$ upper bound by Lemma 5.17. Likewise, the time for the
third step takes is $O(n)$ by Lemma 5.16. Hence the expected time for the
entire algorithm is $O(n)$. ∎

###  5.4. Further examples

As mentioned in the introduction, the framework of the present work allows for
the construction of linear-time exact-size samplers for a large variety of
classes. The key property are bijections between these classes to instances of
$\mathcal{R}$-enriched trees and resulting connections to mono-type branching
processes.

Going through the details would require us to recall large amounts of
combinatorial background on these classes and their bijective encodings. Since
the construction of the samplers may be performed in analogous manner as in
the treated examples, we will only briefly comment on each case. We also
remark that the list presented in the present work makes no claim to be
exhaustive. Further class might be treated in the same way.

####  5.4.1. Outerplanar maps

Planar maps are embeddings of planar graphs into the $2$-sphere, considered up
to orientation-preserving homeomorphism. The faces of a planar map are the
connected components that remain after removing the map from the sphere.
Usually one distinguishes and orients a root-edge, and calls the face to its
right the outer face. A planar map is called outerplanar if all its vertices
lie on the frontier of the outer face.

As mentioned in the introduction, earlier work [14] already described a
linear-time exact-size sampler for uniform random $n$-vertex simple
outerplanar maps. Later, [42] established a bijective encoding between
outerplanar maps in terms of $\mathcal{R}$-enriched trees for

$\mathcal{R}=\textsc{SEQ}\circ\mathcal{D},$

with $\mathcal{D}$ the class of dissections. Similar as for the block-stable
graph classes treated in Subsection 5.1, this class of $\mathcal{R}$-enriched
trees can be shown to be tame and the bijection may be applied in an expected
linear time. This results in an alternative exact-size sampler that operates
in expected linear time.

####  5.4.2. Cographs

Cographs may be characterized recursively as follows: Any graph consisting of
a single vertex and no edges is a cographs. The disjoint union of two cographs
is a cograph. The complement of cograph is a cograph.

The recent work [46, Lem. 5.1] describes how a uniformly chosen cograph with
$n$ labelled vertices may be generated from a tree $\tau_{n}$ obtained by
conditioning a Bienaymé–Galton–Watson tree on having $n$ leaves. The offspring
distribution $\zeta$ is given by its probability generating function

$\mathbb{E}[z^{\zeta}]=2(1-1/\log 2)+2^{z}/\log 2-z.$

A parity $p\in\\{\text{even},\text{odd}\\}$ is chosen uniformly at random
(only once). The $n$ leaves of the random tree $\tau_{n}$ form the vertex set
of the associated cograph. Any two distinct leaves of the tree are adjacent in
the cograph if the parity of the height of their lowest common ancestor in
$\tau_{n}$ equals $p$.

The tree $\tau_{n}$ may be generated in expected time $O(n)$ as described in
Subsection 5.2. The corresponding cograph may be generated in generated in
$O(n^{2})$ steps. The average runtime of the resulting exact-size sampling
procedure is linear in the output size, since the expected number of edges of
the random cograph has order $n^{2}$ by [46].

####  5.4.3. Level-$k$ phylogenetic networks

Phylogenetic networks model the evolutionary history of species that have
undergone reticulation events. From a mathematical perspective, they are
simple rooted directed graphs with no directed cycles subject to the following
constraints: The root has indegree $0$ and outdegree $2$. All non-root
vertices are either tree nodes (indegree $1$, outdegree $2$), reticulation
nodes (indegree $2$, outdegree $1$), or leaves (indegree $1$, outdegree $0$).

The leaves of a phylogenetic network are labelled by elements of a finite
collection of species, similar to labels of a graph. Roughly speaking, given
an integer $k\geq 1$ a level-$k$ network $N$ is a phylogenetic network where
each block (of the associated undirected graph) contains at most $k$
reticulation nodes of $N$. Additionally, any block with at least $3$ vertices
is required to contain at least $2$ vertices that are sources of bridges of
$N$.

At least for $k=1$ and $k=2$, it was shown by [16] that Boltzmann samplers may
be constructed that allow approximate-size sampling of random level-$k$
networks in expected linear time, and exact-size sampling in expected
quadratic time. Recent work [45, Sec. 2] showed that for $k\geq 1$ random
$n$-leaf phylogenetic networks may be generated by applying a blow-up
procedure to a Bienaymé–Galton–Watson tree (with offspring distribution
depending on $k$) conditioned on having $n$ leaves. This random tree may be
generated in time $O(n)$ as described in Subsection 5.2, and the expected time
for applying the blow-up procedure is $O(n)$ by analogous arguments as in
Subsection 5.1. This results in a linear time exact-size sampler for random
$n$-leaf level-$k$ phylogenetic networks.

## References

  * [1] M. Albert and M. Atkinson.  Simple permutations and pattern restricted permutations.  Discrete Math., 300(1):1–15, 2005.
  * [2] M. Bahrani and J. Lumbroso.  Split-decomposition trees with prime nodes: enumeration and random generation of cactus graphs.  In Proceedings of the 15th workshop on analytic algorithmics and combinatorics, ANALCO ’18, New Orleans, LA, January 8–9, 2018, pages 143–157. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2018.
  * [3] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot.  Universal limits of substitution-closed permutation classes.  J. Eur. Math. Soc. (JEMS), 22(11):3565–3639, 2020.
  * [4] F. Bassino, M. Bouvel, A. Pierrot, C. Pivoteau, and D. Rossin.  An algorithm computing combinatorial specifications of permutation classes.  Discrete Appl. Math., 224:16–44, 2017.
  * [5] M. Bendkowski, O. Bodini, and S. Dovgal.  Polynomial tuning of multiparametric combinatorial samplers.  In 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 92–106. SIAM, Philadelphia, PA, 2018.
  * [6] F. Bergeron, G. Labelle, and P. Leroux.  Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1998.  Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota.
  * [7] N. Bernasconi, K. Panagiotou, and A. Steger.  The degree sequence of random graphs from subcritical classes.  Combin. Probab. Comput., 18(5):647–681, 2009.
  * [8] O. Bodini, E. Fusy, and C. Pivoteau.  Random sampling of plane partitions.  Combin. Probab. Comput., 19(2):201–226, 2010.
  * [9] O. Bodini, D. Gardy, and A. Jacquot.  Asymptotics and random sampling for BCI and BCK lambda terms.  Theoret. Comput. Sci., 502:227–238, 2013.
  * [10] O. Bodini and Y. Ponty.  Multi-dimensional Boltzmann sampling of languages.  In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’10), Discrete Math. Theor. Comput. Sci. Proc., AM, pages 49–63. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2010.
  * [11] O. Bodini, O. Roussel, and M. Soria.  Boltzmann samplers for first-order differential specifications.  Discrete Appl. Math., 160(18):2563–2572, 2012.
  * [12] M. Bodirsky, É. Fusy, M. Kang, and S. Vigerske.  Boltzmann samplers, Pólya theory, and cycle pointing.  SIAM J. Comput., 40(3):721–769, 2011.
  * [13] M. Bodirsky and M. Kang.  Generating outerplanar graphs uniformly at random.  Comb. Probab. Comput., 15(3):333–343, 2006.
  * [14] N. Bonichon, C. Gavoille, and N. Hanusse.  Canonical decomposition of outerplanar maps and application to enumeration, coding and generation.  J. Graph Algorithms Appl., 9(2):185–204 (electronic), 2005.
  * [15] J. Borga, M. Bouvel, V. Féray, and B. Stufler.  A decorated tree approach to random permutations in substitution-closed classes.  Electronic Journal of Probability, 25(none):1 – 52, 2020.
  * [16] M. Bouvel, P. Gambette, and M. Mansouri.  Counting phylogenetic networks of level 1 and 2.  J. Math. Biol., 81(6-7):1357–1395, 2020.
  * [17] G. Chapuy, E. Fusy, M. Kang, and B. Shoilekova.  A complete grammar for decomposing a family of graphs into 3-connected components.  Electron. J. Combin., 15(1):Research Paper 148, 39, 2008.
  * [18] N. Curien and I. Kortchemski.  Random non-crossing plane configurations: a conditioned Galton-Watson tree approach.  Random Structures Algorithms, 45(2):236–260, 2014.
  * [19] A. Denise and P. Zimmermann.  Uniform random generation of decomposable structures using floating-point arithmetic.  Theoretical Computer Science, 218(2):233–248, 1999.
  * [20] N. Dershowitz and S. Zaks.  The cycle lemma and some applications.  European J. Combin., 11(1):35–40, 1990.
  * [21] L. Devroye.  Simulating size-constrained Galton-Watson trees.  SIAM J. Comput., 41(1):1–11, 2012.
  * [22] M. Drmota, É. Fusy, M. Kang, V. Kraus, and J. Rué.  Asymptotic study of subcritical graph classes.  SIAM J. Discrete Math., 25(4):1615–1651, 2011.
  * [23] M. Drmota and M. Noy.  Extremal parameters in sub-critical graph classes.  In ANALCO13—Meeting on Analytic Algorithmics and Combinatorics, pages 1–7. SIAM, Philadelphia, PA, 2013.
  * [24] P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer.  Boltzmann samplers for the random generation of combinatorial structures.  Combin. Probab. Comput., 13(4-5):577–625, 2004.
  * [25] R. Ehrenborg and M. Méndez.  Schröder parenthesizations and chordates.  J. Combin. Theory Ser. A, 67(2):127–139, 1994.
  * [26] P. Flajolet, É. Fusy, and C. Pivoteau.  Boltzmann sampling of unlabelled structures.  In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics, pages 201–211. SIAM, Philadelphia, PA, 2007\.
  * [27] P. Flajolet and R. Sedgewick.  Analytic combinatorics.  Cambridge University Press, Cambridge, 2009.
  * [28] P. Flajolet, P. Zimmerman, and B. Van Cutsem.  A calculus for the random generation of labelled combinatorial structures.  Theoret. Comput. Sci., 132(1-2):1–35, 1994.
  * [29] E. Fusy.  Uniform random sampling of planar graphs in linear time.  Random Structures Algorithms, 35(4):464–522, 2009.
  * [30] O. Giménez, D. Mitsche, and M. Noy.  Maximum degree in minor-closed classes of graphs.  Eur. J. Comb., 55:41–61, 2016.
  * [31] S. Janson.  Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation.  Probab. Surv., 9:103–252, 2012.
  * [32] D. E. Knuth.  The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms.  Addison Wesley Longman Publishing Co., Inc., USA, 1997.
  * [33] I. Kortchemski.  Invariance principles for Galton-Watson trees conditioned on the number of leaves.  Stochastic Process. Appl., 122(9):3126–3172, 2012.
  * [34] A. Nijenhuis and H. S. Wilf.  Combinatorial algorithms.  Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, second edition, 1978.  For computers and calculators, Computer Science and Applied Mathematics.
  * [35] K. Panagiotou and A. Steger.  Maximal biconnected subgraphs of random planar graphs.  ACM Trans. Algorithms, 6(2):Art. 31, 21, 2010.
  * [36] K. Panagiotou and B. Stufler.  Scaling limits of random Pólya trees.  Probab. Theory Related Fields, 170(3-4):801–820, 2018.
  * [37] K. Panagiotou, B. Stufler, and K. Weller.  Scaling limits of random graphs from subcritical classes.  Ann. Probab., 44(5):3291–3334, 2016.
  * [38] C. Pivoteau, B. Salvy, and M. Soria.  Algorithms for combinatorial structures: well-founded systems and Newton iterations.  J. Combin. Theory Ser. A, 119(8):1711–1773, 2012.
  * [39] D. Rizzolo.  Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set.  Ann. Inst. Henri Poincaré Probab. Stat., 51(2):512–532, 2015\.
  * [40] S. S. Skiena.  The Algorithm Design Manual.  Texts in Computer Science. Springer International Publishing, London, 3 edition, 2020.
  * [41] A. Sportiello.  Boltzmann sampling of irreducible context-free structures in linear time, 2021.
  * [42] B. Stufler.  Scaling limits of random outerplanar maps with independent link-weights.  Ann. Inst. H. Poincaré Probab. Statist., 53(2):900–915, 05 2017\.
  * [43] B. Stufler.  Random enriched trees with applications to random graphs.  Electronic Journal of Combinatorics, 25(3), 2018.
  * [44] B. Stufler.  Limits of random tree-like discrete structures.  Probab. Surv., 17:318–477, 2020.
  * [45] B. Stufler.  A branching process approach to level-$k$ phylogenetic networks.  Random Structures & Algorithms, to appear, 2021+.
  * [46] B. Stufler.  Graphon convergence of random cographs.  Random Structures & Algorithms, 59(3):464–491, 2021.