# The phase transition for parking on Galton–Watson trees

Nicolas Curien 111Université Paris-Saclay and Institut Universitaire de
France. E-mail<EMAIL_ADDRESS>and Olivier Hénard222Université
Paris-Saclay E-mail<EMAIL_ADDRESS>
###### Abstract

We establish a phase transition for the parking process on critical
Galton–Watson trees. In this model, a random number of cars with mean $m$ and
variance $\sigma^{2}$ arrive independently on the vertices of a critical
Galton–Watson tree with finite variance $\Sigma^{2}$ conditioned to be large.
The cars go down the tree and try to park on empty vertices as soon as
possible. We show a phase transition depending on

$\Theta:=(1-m)^{2}-\Sigma^{2}(\sigma^{2}+m^{2}-m).$

Specifically, if $\Theta>0,$ then most cars will manage to park, whereas if
$\Theta<0$, then a positive fraction of the cars will not find a spot and exit
the tree through the root. This confirms a conjecture of Goldschmidt and
Przykucki [6].

Figure 1: Middle: A plane tree together with a configuration of cars trying to
park. Left: the resulting parking configuration, where $2$ cars did not manage
to park on the tree. Right: the same parked tree with flux on the edges (all
the non-labeled edges have flux zero).

##  1 Introduction

The parking process on the line is a very classical problem in probability and
combinatorics. Recently, a generalization of this process on plane trees
received much attention [11, 6, 5, 9, 7]. In this paper, we shall see, in full
generality, that this process displays a rich phase transition phenomenon
(sharing many similarities with the usual phase transition for Bernoulli
percolations on deterministic lattices) and we pinpoint the location of the
phase transition which depends only the means and variances of the car
arrivals and of the critical offspring distribution of the underlying
Galton–Watson trees thereby confirming a conjecture of Goldschmidt and
Przykucki.

#### Parking on a rooted plane tree.

We consider a finite plane tree $\mathfrak{t}$ whose vertices will be
interpreted as free parking spots, each spot accomodating at most 1 car,
together with a configuration
$\ell:\mathrm{Vertices}(\mathfrak{t})\to\\{0,1,2,\dots\\}$ representing the
number of cars arriving on each vertex. Each car tries to park on its arrival
vertex, and if the spot is occupied, it travels downward towards the root of
the tree until it finds an empty vertex to park. If there is no such vertex on
its way, the car exits the tree through the root $\varnothing$. The outgoing
_flux_ $\varphi(\mathfrak{t},\ell)$ is the number of cars which did not manage
to park. Let us note two important properties of the model: First, the final
configuration and the outgoing flux do not depend upon the order chosen to
park the cars: we call it the Abelian property of the model. Second, we have a
monotonicity property, and in particular the outgoing flux is an increasing
function of $\ell$ for a given tree $\mathfrak{t}$.

Our stochastic model of parking is as follows. Given a (random) rooted plane
tree $\mathfrak{t}$, we shall suppose that the arrival of cars on each vertex
of $\mathfrak{t}$ are independent identically distributed random variables
with law

$\displaystyle\mu\quad\mbox{ with mean }m>0\mbox{ and finite variance
}\sigma^{2}$ $\displaystyle\mbox{ {(car arrivals)}}.$

That is, conditionally on $\mathfrak{t}$, the variables
$(\ell(x))_{x\in\mathrm{Vertices}(\mathfrak{t})}$ are i.i.d. with law $\mu$.
By abuse of notation, in the rest of this paper we shall always deal with
i.i.d. labeled trees and do not specify it further, e.g. we shall write
$\varphi(\mathfrak{t})\equiv\varphi(\mathfrak{t},\ell)$ for the (random)
outgoing flux of cars. In what follows, the random tree $\mathfrak{t}$ will be
a version of a critical Bienaymé–Galton–Watson tree with offspring
distribution

$\displaystyle\nu\quad\mbox{aperiodic with mean }1\mbox{ and finite variance
}\Sigma^{2}$ $\displaystyle\mbox{ {(offspring distribution)}}.$

Specifically, we shall consider the parking process on three different types
of random trees: the (unconditioned) Galton–Watson tree $\mathcal{T}$, its
version $\mathcal{T}_{n}$ conditioned to have $n$ vertices, and the weak local
limit $\mathcal{T}_{\infty}$ of the family $(\mathcal{T}_{n})_{n\geqslant 1}$,
that one may also regard as the original Galton–Watson tree $\mathcal{T}$
conditioned to survive forever. Both distributions $\mu,\nu$ will be taken
distinct from $\delta_{1}$ without further notice.

#### The phase transition.

Our main result establishes a sharp phase transition for the parking process
on these random trees. To describe it, let us first focus on the case of
$\mathcal{T}_{n}$ for large $n$’s. Heuristically if the “density” of cars is
small enough, we expect that most of them can park on $\mathcal{T}_{n}$ and
the outgoing flux should be small (we can still have local conflicts near the
root of the tree so some cars may not manage to park). On the other hand, if
there are “too many” cars, then we expect that a positive fraction of the cars
will not park, hence $\varphi(\mathcal{T}_{n})$ is asymptotically linear in
$n$. This is indeed the case:

######  Theorem 1 (Phase transition for parking on Galton–Watson trees).

If $m$ and $\sigma^{2}$ respectively are the mean and variance of $\mu$ (car
arrivals), and if $\Sigma^{2}$ is the variance of the critical offspring
distribution $\nu$, then we let

$\Theta:=(1-m)^{2}-\Sigma^{2}(\sigma^{2}+m^{2}-m).$

Assuming $m\leqslant 1$, we have three regimes classified as follows:

|  | subcritical | critical | supercritical
---|---|---|---|---
|  | $\Theta>0$ | $\Theta=0$ | $\Theta<0$
(i) |  $\varphi(\mathcal{T}_{n})$ as $n\to\infty$ | finite limit law | $\xrightarrow[n\to\infty]{(\mathbb{P})}\infty\mbox{ but is }o(n)$ | $\approx cn,\quad c>0$
(ii) | $\Sigma^{2}\mathbb{E}[\varphi(\mathcal{T})]+m-1$ | $-\sqrt{\Theta}$ | $0$ | $\infty$
(iii) | $\mathbb{P}(\varnothing\mbox{ has a car in }\mathcal{T})$ | $m$ | $m$ | $m-c$

Let us comment on our result. The first line $(i)$ of the above table shows
that there is indeed a phase transition for the outgoing flux
$\varphi(\mathcal{T}_{n})$ that jumps from values of order $O(1)$ to $cn$ (the
latter meaning that $\varphi(\mathcal{T}_{n})/n$ converges to $c$ in
probability) in a small variation of the parameter
$\Theta=\Theta(m,\sigma^{2},\Sigma^{2})$. The assumption $m\leqslant 1$ is not
demanding since otherwise the model is clearly supercritical (there are
typically more cars than parking spots !). By $(ii)$ this transition also
coincides with the moment where the mean flux at the root of $\mathcal{T}$
jumps from a finite to an infinite value. The effect is even more dramatic
(and easier to analyse) on the infinite tree $\mathcal{T}_{\infty}$. By the
classical spinal decomposition, $\mathcal{T}_{\infty}$ is obtained by grafting
independently on each vertex of a semi-infinite line, a random number $Y-1$ of
(unconditioned) Galton–Watson trees $\mathcal{T}$ where $Y$ follows the size-
biased distribution $\overline{\nu}(k)=k\nu(k)$ for $k\geqslant 1$. It follows
that the law of $\varphi(\mathcal{T}_{\infty})$ is simply related with the one
of the supremum of the random walk with i.i.d. increments with law

$\sum_{i=1}^{Y-1}F_{i}+P-1,$

where $Y\sim\overline{\nu}$, $F_{i}\sim\varphi(\mathcal{T})$ and $P\sim\mu$
are all independent, see equation (2) for details. In particular, from line
$(ii)$ of the previous table we see that this random walk has a negative drift
in the subcritical regime (and so its supremum is finite), has zero mean in
the critical regime and infinite mean in the supercritical one (and so its
supremum is infinite). The last line of the table is connected to the law of
large number on $\varphi(\mathcal{T}_{n})$ via the quenched convergence of the
fringe subtree distribution established by Janson [8], see Lemma 2.

######  Remark.

It may appear as a “little miracle” that the location of the phase transition
only depends on the first two moments and not on more complicated observables
of the underlying distributions. This was indeed conjectured in [6] using a
non-rigorous variance analysis of $\varphi(\mathcal{T})$. For example, if
$\sigma^{2}=\infty$ or simply if $\sigma^{2}\Sigma^{2}\geqslant 1$ then the
model is supercritical regardless of the density $m>0$ of cars.

#### Previous works.

To the best of our knowledge, the parking process on random trees has first
been studied by Lackner & Panholzer [11] in the case of Poisson car arrivals
on Cayley trees where they established a phase transition using involved
analytic combinatorics techniques, see also [13]. This phase transition was
further explained by Goldschmidt & Przykucki [6] using the infinite tree
$\mathcal{T}_{\infty}$. In [6] the results are transfered from
$\mathcal{T}_{\infty}$ to $\mathcal{T}_{n}$ using increasing couplings. Their
arguments were later applied to the case of geometric plane trees (still with
Poisson car arrivals) by Chen & Goldschmidt [5]. Motivated by hydrological
modeling problem, Jones [9] independently considered the parking process on
random trees in the case of binary arrivals on binary tree. All these models
are encompassed by our general framework. Notice however that Lackner &
Panholzer [11] and Jones [9] got some critical exponents in the critical case.
We defer the study of the critical case to a forthcoming paper that tackles
the case of uniform trees ($\nu$ is geometric) with the help of tools from
analytic combinatorics, in particular the enumeration of planar maps. Perhaps
surprisingly we will show in that there is a family of scaling limits for the
critical parking depending on the tail distribution of $\mu$. Those scaling
limits are intimately connected to random growth-fragmentation processes
introduced by Bertoin and which appear in the study of random planar maps [4].
The parking process on trees is also related to the Derrida-Retaux model on
supercritical Galton–Watson trees recently tackled in [7] and more generally
to recursive $(\min,+)$ distributional equations, see [2].

Contrary to [11, 5, 6] which ultimately rely on some explicit computation, our
method of proof in this paper is general and purely probabilist. It relies on
classical tools in percolation theory such as differential (in)equalities
obtained through increasing couplings combined with the use of many-to-one
lemmas and spinal decompositions of random trees (see Eq. (3)).

Acknowledgments. We thank Bastien Mallein and Christina Goldschmidt for an
interesting discussion. Also, we are indebted to Alice Contat for spotting a
typo in the proof of Proposition 1, and, together with Linxiao Chen, for
pointing the necessity of the assumption $m\leqslant 1$ in Theorem 1. The
first author acknowledges the support of the ERC Advanced Grant 740943
“GeoBrown”.

##  2 The different trees and their relations

We recall here the basic properties of the Galton–Watson tree $\mathcal{T}$,
its version $\mathcal{T}_{n}$ conditioned to have $n$ vertices, and of
Kesten’s tree, the infinite Galton–Watson tree $\mathcal{T}_{\infty}$ obtained
as the local limit of $\mathcal{T}_{n}$ as $n\to\infty$. We refer to [1] for
background on these objects.

###  2.1 Parking on $\mathcal{T}_{\infty}$ and a random walk

We quickly recall the construction of Kesten’s tree $\mathcal{T}_{\infty}$. We
denote by $\overline{\nu}$ the size biased distribution of $\nu$ obtained by
putting for $k\geqslant 0$

$\overline{\nu}_{k}=k\nu_{k}.$

By criticality of $\nu$, this defines a probability distribution with
expectation $\Sigma^{2}+1$. The random tree $\mathcal{T}_{\infty}$ is an
infinite plane tree, obtained as follows: Start from a semi-infinite line
$\\{S_{0},S_{1},\dots\\}$ of vertices rooted at $S_{0}$, called the _spine_ ,
and graft independently on each $S_{i}$ a random number $Y-1$ of independent
Galton–Watson trees where $Y\sim\overline{\nu}$. To get a plane tree (i.e. a
tree with a planar orientation), independently for each vertex of the spine,
consider a random uniform ordering of the children. See [1] for details and
Figure 2 for an illustration. In particular the mean number of trees grafted
on each vertex of the spine is $\sum_{k\geqslant
1}\overline{\nu}_{k}\cdot(k-1)=\Sigma^{2}$.

Figure 2:  The construction of $\mathcal{T}_{\infty}$ from a spine and a
random $\overline{\nu}-1$ number of $\nu$-Galton–Watson trees grafted on each
vertex. After assigning random plane orientations to the children of each
vertex of the spine we obtain the plane tree $\mathcal{T}_{\infty}$.

The parking process is easy to analyse on $\mathcal{T}_{\infty}$ as observed
in [6]. To do this, we shall perform the parking process in two stages: we
first (try to) park all the cars arriving in the subtrees grafted to the spine
of $\mathcal{T}_{\infty}$ and then park the remaining cars arriving on the
spine of $\mathcal{T}_{\infty}$. After performing the first stage, let us
focus on the number of incoming cars at $S_{h}$ the $h$-th vertex on the spine
coming for the “branches on the sides” (first stage of the parking process)
together with the possible cars arriving precisely at this vertex. By the
description of $\mathcal{T}_{\infty}$, these quantities are i.i.d. with law

$\displaystyle Z=\sum_{i=1}^{Y-1}F_{i}+P,$ (1)

where $Y\sim\overline{\nu}$, $F_{i}\sim\varphi(\mathcal{T})$, $P\sim\mu$ are
all independent. In particular, the mean of $Z$ is equal to
$\Sigma^{2}\mathbb{E}[\varphi(\mathcal{T})]+m$ which is the quantity appearing
in Line (ii) of Theorem 1. Performing the second stage of the parking, it is
easy to see that the flux at the root can be written as

$\displaystyle\varphi(\mathcal{T}_{\infty})=\sup_{h\geqslant
0}\big{(}Z_{0}+\dots+Z_{h}-(h+1)\big{)}\vee 0,$ (2)

where $Z_{i}$ are i.i.d. copies of $Z$. This settles the case of the local
limit easily: when $\mathbb{E}[Z]\geqslant 1$ (which corresponds to the
supercritical or critical case), the random walk $W$ with i.i.d. increments
with law $Z-1$ oscillates or drifts to $+\infty$ and the flux at the root of
$\mathcal{T}_{\infty}$ is infinite with probability $1$. When
$\mathbb{E}[Z]<1$ (which corresponds to the subcritical case), the random walk
$W$ has a negative drift, and $\varphi(\mathcal{T}_{\infty})$ is almost surely
finite.

###  2.2 Spinal decomposition for $\mathcal{T}$

If $\mathfrak{t}$ is a plane tree given with a distinguished vertex
$x\in\mathfrak{t}$, we denote by $\mathrm{Top}(\mathfrak{t},x)$ the subtree of
the descendants of $x$ and let $\mathrm{Pruned}(\mathfrak{t},x)$ be the tree
obtained from $\mathfrak{t}$ by removing
$\mathrm{Top}(\mathfrak{t},x)\backslash\\{x\\}$, see Figure 3. This tree is
naturally pointed at $x$. The spinal decomposition for a _critical_
Galton–Watson tree $\mathcal{T}$ reads as follows:

$\displaystyle\mathbb{E}\left[\sum_{x\in\mathcal{T}}F\Big{(}\mathrm{Pruned}(\mathcal{T},x),\mathrm{Top}(\mathcal{T},x)\Big{)}\right]=\sum_{h\geqslant
0}\mathbb{E}\left[F\Big{(}\mathrm{Pruned}(\mathcal{T}_{\infty},S_{h}),\mathcal{T}\Big{)}\right],$
(3)

for any positive function $F$, where in the last expectation
$\mathcal{T}_{\infty}$ and $\mathcal{T}$ are independent. See [12, Chapter
12.1] from which the statement is easily derived. We shall use the
straightforward extension of this equation to trees decorated with i.i.d.
labels.

###  2.3 Comparisons between $\mathcal{T}_{n}$ and $\mathcal{T}_{\infty}$

In the case of $\mathcal{T}_{n}$, the spinal decomposition is more intricate
but we will only need a rough control. To define a spine in $\mathcal{T}_{n}$,
conditionally on $\mathcal{T}_{n}$ we sample a uniform vertex
$\mathcal{V}_{n}\in\mathcal{T}_{n}$. It is standard that the height
$|\mathcal{V}_{n}|$ of $\mathcal{V}_{n}$ converges once renormalized by
$\sqrt{n}$ towards a Rayleigh distribution, more precisely, we have the
following local limit law established in [10, Eq (12)]

$\displaystyle\sup_{\varepsilon<t<1/\varepsilon}\sqrt{n}\left|\mathbb{P}\left(|\mathcal{V}_{n}|=\lfloor
t\frac{\sqrt{2n}}{\Sigma}\rfloor\right)-\frac{\Sigma}{\sqrt{2n}}\cdot
2t\mathrm{e}^{-t^{2}/2}\right|\xrightarrow[n\to\infty]{}0,$ (4)

for any $\varepsilon>0$. To get a control on large parts of the tree
$\mathcal{T}_{n}$, we shall decompose it into three pieces. Recall the
definition of $\mathrm{Pruned}(\mathfrak{t},x)$ for a plane tree
$\mathfrak{t}$ with a distinguished vertex $x$. We shall further decompose
$\mathrm{Pruned}(\mathfrak{t},x)$ into two rooted plane trees carrying a
distinguished vertex by considering
$\mathrm{Down}(\mathfrak{t},x)=\mathrm{Pruned}(\mathfrak{t},y)$ where $y$ is
the ancestor of $x$ at generation $\lfloor|x|/2\rfloor$ where $|x|$ is the
height of $x$. We also set
$\mathrm{Up}(\mathfrak{t},x)=\mathrm{Top}(\mathrm{Pruned}(\mathfrak{t},x),y)$.
See Figure 3 for an illustration.

Figure 3:  The different pieces cut out of a plane tree $\mathfrak{t}$ with a
distinguished vertex $x$.

######  Lemma 1 (Rough control).

Conditionally on $\mathcal{T}_{n}$, let $\mathcal{V}_{n}$ be a uniform vertex
in $\mathcal{T}_{n}$ whose height is denoted by $H_{n}$ and let
$\mathcal{T}_{\infty}$ be independent of $(\mathcal{T}_{n},\mathcal{V}_{n})$.
For every $\varepsilon>0$, there exists $\delta>0$ and $n_{0}\geqslant 0$ such
that for all $n\geqslant n_{0}$ and any event $A$

$\mathbb{P}\left(\mathrm{Down}(\mathcal{T}_{\infty},S_{H_{n}})\in
A\right)\leqslant\delta\quad\Longrightarrow\quad\mathbb{P}\left(\mathrm{Down}(\mathcal{T}_{n},\mathcal{V}_{n})\in
A\right)\leqslant\varepsilon.$

A similar statement holds when the $\mathrm{Down}$ parts are replaced by the
$\mathrm{Up}$ parts.

###### Proof.

Fix a tree $\mathfrak{t}^{\bullet}$ with $n_{0}\leqslant n$ vertices and a
distinguished leaf at height $\lfloor h/2\rfloor$. An easy calculation shows
that

$\frac{\mathbb{P}(\mathrm{Down}(\mathcal{T}_{n},\mathcal{V}_{n})=\mathfrak{t}^{\bullet}\mid|\mathcal{V}_{n}|=h)}{\mathbb{P}(\mathrm{Down}(\mathcal{T}_{\infty},S_{h})=\mathfrak{t}^{\bullet})}=\frac{(n-n_{0}+1)\cdot\mathbb{P}(|\mathcal{T}|=n-n_{0}+1)\mathbb{P}(|\mathcal{V}_{n-n_{0}+1}|=h-\lfloor
h/2\rfloor)}{n\cdot\mathbb{P}(|\mathcal{T}|=n)\mathbb{P}(|\mathcal{V}_{n}|=h)}.$

Using (4), the last display is bounded by some absolute constant
$C_{\alpha}>0$ as long as $\alpha\sqrt{n}\leqslant
h\leqslant\alpha^{-1}\sqrt{n}$ and $n_{0}\leqslant(1-\alpha)n$. We deduce that
for any event $A$ we have

$\displaystyle\mathbb{P}(\mathrm{Down}(\mathcal{T}_{n},\mathcal{V}_{n})\in A)$
$\displaystyle\leqslant$ $\displaystyle
C_{\alpha}\mathbb{P}(\mathrm{Down}(\mathcal{T}_{\infty},S_{H_{n}})\in A)$
$\displaystyle+\mathbb{P}(H_{n}/\sqrt{n}\notin[\alpha,\alpha^{-1}]\mbox{ \ \
or \ \
}|\mathrm{Down}(\mathcal{T}_{n},\mathcal{V}_{n})|\geqslant(1-\alpha)n).$

Using standard scaling limit results for $(\mathcal{T}_{n},\mathcal{V}_{n})$,
the second probability in the right-hand side can be made smaller than
$\varepsilon/2$ (for all $n$ large enough) by choosing $\alpha>0$ small
enough. Putting $\delta=\varepsilon/(2C_{\alpha})$ we indeed deduce that
$\mathbb{P}(\mathrm{Down}(\mathcal{T}_{\infty},S_{H_{n}})\in
A)\leqslant\delta$ implies
$\mathbb{P}(\mathrm{Down}(\mathcal{T}_{n},\mathcal{V}_{n})\in
A)\leqslant\varepsilon$ as desired. The result for the $\mathrm{Up}$ part can
be deduced by symmetry. ∎

###  2.4 Fringe trees and a law of large number for the flux

Given a plane tree $\mathfrak{t}$, the fringe subtree distribution is the
empirical measure

$\mathrm{Fringe}(\mathfrak{t})=\frac{1}{\\#\mathfrak{t}}\sum_{x\in\mathfrak{t}}\delta_{\mathrm{Top}(\mathfrak{t},x)}.$

The result of Janson [8, Theorem 1.3, Quenched version, formula (1.11)] states
that $\mathrm{Fringe}(\mathcal{T}_{n})$ converges in probability (for the
total variation distance) towards the distribution of the $\nu$-Galton–Watson
measure. For our purposes, the definition of $\mathrm{Fringe}$ is easily
extended by taking care of the labeling
$\ell:\mathcal{T}_{n}\to\mathbb{Z}_{\geqslant 0}$ and enables us to establish
an “abstract” law of large numbers for the flux $\varphi(\mathcal{T}_{n})$:

######  Lemma 2.

(Weak law of large numbers for the flux in conditioned Galton–Watson trees).
Recall that $m$ is the mean of $\mu$. The flux at the root of
$\mathcal{T}_{n}$ satisfies

$\displaystyle\frac{\varphi(\mathcal{T}_{n})}{n}\quad\xrightarrow[n\to\infty]{(\mathbb{P})}\quad
m-\mathbb{P}(\varnothing\mbox{ contains a car in }\mathcal{T}).$ (5)

###### Proof.

Recall that conditionally on $\mathcal{T}_{n}$, the car arrivals
$(L_{x}:x\in\mathcal{T}_{n})$ are i.i.d. with law $\mu$. By the conservation
of cars 333This argument does not work in France on New Year’s Eve where about
$1000$ cars are burned. we have

$\left(\sum_{x\in\mathcal{T}_{n}}L_{x}\right)-\varphi(\mathcal{T}_{n})=\sum_{x\in\mathcal{T}_{n}}\mathds{1}_{\mbox{
the root of }\mathrm{Top}(\mathcal{T}_{n},x)\mbox{ contains a car}}.$

The latter quantity is an additive functional on the fringe subtrees
(decorated with car arrivals) of $\mathcal{T}_{n}$, whose empirical measure
converges in probability to the (decorated) $\nu$–Galton–Watson measure, as we
just recalled. It follows that

$\frac{1}{n}\sum_{x\in\mathcal{T}_{n}}\mathds{1}_{\mbox{ the root of
}\mathrm{Top}(\mathcal{T}_{n},x)\mbox{ contains a
car}}\quad\xrightarrow[n\to\infty]{(\mathbb{P})}\quad\mathbb{P}(\varnothing\mbox{
contains a car in }\mathcal{T}).$

Since $\frac{1}{n}\sum_{x\in\mathcal{T}_{n}}L_{x}\to m$ in probability by the
law of large numbers, the desired result follows. ∎

##  3 $\mathbb{E}[\varphi(\mathcal{T})]$ via spine decomposition and a
differential equation

In this section we compute $\mathbb{E}[\varphi(\mathcal{T})]$ thus proving
line $(ii)$ in Theorem 1. This is done using a differential equation (more
precisely its integral version) obtained, roughly speaking, by letting the
cars arriving one-by-one and computing the marginal contribution to the flux
using the spine decomposition (3). The same method is applied to estimate
$\mathbb{P}(\varnothing\mbox{ contains a car in }\mathcal{T})$ and yields line
$(iii)$ of Theorem 1 which in turn implies parts of line $(i)$ by Lemma 2.

###  3.1 The mean flux $\mathbb{E}[\varphi(\mathcal{T})]$

Conditionally on $\mathcal{T}$, we define $(A_{x},L_{x})_{x\in\mathcal{T}}$ a
collection of independent random variables distributed as
$\mathrm{Unif}[0,1]\otimes\mu$. The variable ${A}_{x}$ will be thought of as
“the time of arrival” of the ${L}_{x}$ cars on the vertex $x$. This enables us
to define an increasing labeling $L^{(t)}:\mathcal{T}\to\\{0,1,2,\dots\\}$ by
setting

$L^{(t)}(x)=\mathbf{1}_{{A}_{x}\leqslant t}\cdot{L}_{x}\quad\mbox{ with
associated flux }\quad\varphi(t):=\varphi(\mathcal{T},L^{(t)}).$

Obviously, $L^{(t)}$ is an i.i.d. labeling of $\mathcal{T}$ with law
$\mu_{t}=(1-t)\delta_{0}+t\mu$ with mean $mt$. In the following, we take
profit of the arrival times $A_{x}$ to park the cars sequentially (which is
allowed by the Abelian property of the model).

######  Proposition 1 (Phase transition for the mean flux).

For $t\in[0,1]$ let $\varPhi(t)=\mathbb{E}[\varphi(t)]$ be the mean flux in
$\mathcal{T}$ with car arrivals with law $\mu_{t}$. If $t_{\max}$ is the
smallest positive solution of the equation
$(1-mt)^{2}=t\Sigma^{2}(\sigma^{2}+m^{2}-m)$ (set $t_{\max}=+\infty$ in case
no such solution exists), then

$\displaystyle\varPhi(t)=\left\\{\begin{array}[]{lcc}\displaystyle\frac{(1-mt)-\sqrt{(1-mt)^{2}-\Sigma^{2}(\sigma^{2}+m^{2}-m)t}}{\Sigma^{2}}&\mbox{
if }&t\leqslant t_{\max}\\\ +\infty&\mbox{ if }&t>t_{\max}.\end{array}\right.$
(8)

###### Proof of Line $(ii)$ of Theorem 1.

It remains to justify the following alternative characterization of the three
regimes described in Theorem 1 by mean of the parameter
$t_{\max}\in]0,+\infty]$ : $t_{\max}<1$ in the supercritical regime
$\Theta<0$, $t_{\max}=1$ in the critical regime $\Theta=0$ and $t_{\max}>1$ in
the subcritical regime $\Theta>0$. To check these claims, observe that the
function

$t\mapsto(1-mt)^{2}-t\Sigma^{2}(\sigma^{2}+m^{2}-m)$

is decreasing on $[0,1/m]$ (hence on $[0,1]$ since we assumed $m\leq 1$), as
the sum of a decreasing function on $[0;1/m]$, $t\mapsto(1-mt)^{2}$, and a non
increasing-one on $\mathbb{R}$ (the coefficient
$\sigma^{2}+m^{2}-m=\mathbb{E}[L(L-1)]$ is non-negative). ∎

###### Proof of Proposition 1 .

Let $t\in[0,1]$ and write

$\displaystyle\varPhi(t)$
$\displaystyle=\mathbb{E}\Big{[}\sum_{x\in\mathcal{T}}I^{x}(A_{x})\mathds{1}_{0\leqslant
A_{x}\leqslant t}\Big{]}$

where $I^{x}(s)$ is the number $\in\\{0,1,\dots,L_{x}\\}$ of cars that arrived
at time $s$ on the vertex $x$ which contribute to $\varphi(t)$, i.e. those
that did not manage to park at their arrival time $s\leqslant t$. Integrating
on the value $s=A_{x}$ and using the spinal decomposition (3) – more precisely
its easy extension to decorated Galton–Watson trees– we can write the previous
display as

$\displaystyle\varPhi(t)=\mathbb{E}\Big{[}\sum_{x\in\mathcal{T}}I^{x}(A_{x})\mathds{1}_{0\leqslant
A_{x}\leqslant t}\Big{]}$
$\displaystyle\underset{\eqref{eq:spinal}}{=}\int_{0}^{t}\mathrm{d}s\
\sum_{h=0}^{\infty}\mathbb{E}[I(s,h)]$ (9)

where $I(s,h)$ is obtained as follows: For $h\geqslant 0$ define a tree
$\mathcal{T}(h)$ by grafting an independent copy of $\mathcal{T}$ on top of
$\mathrm{Pruned}(\mathcal{T}_{\infty},S_{h})$. This tree is decorated by
letting i.i.d. cars arrivals with law $\mu_{s}$ _except_ on the vertex $S_{h}$
where we put an independent number of cars distributed as $\mu$. Then $I(s,h)$
is the number of those cars arriving on $S_{h}$ that do not manage to park
after having parked all other cars of $\mathcal{T}(h)$. See Figure 4 for an
illustration.

Figure 4:  Definition of the variable $I(s,h)$: add on top of
$\mathrm{Pruned}(\mathcal{T}_{\infty},S_{h})$ an independent unconditioned
Galton–Watson $\mathcal{T}$. Labels all the vertices except $S_{h}$ of the
resulting tree with i.i.d. car arrivals with law $\mu_{s}$ and let them park.
The variable $I(s,h)$ is then the number of cars among an independent number
$\sim\mu$ of cars that we add on $S_{h}$ that do not manage to park.

To compute $\mathbb{E}[I(s,h)]$ we proceed as in Section 2.1 and notice that
at time $s-$ the outgoing flux from the vertex $S_{h-i}$ (before parking the
cars arriving on $S_{h}$) is a random walk $(W^{(s)}_{i}:0\leqslant i\leqslant
h)$ of length $h$ with i.i.d. increments with law $Z^{(s)}-1$ where $Z^{(s)}$
is defined as in (1) by

$\displaystyle Z^{(s)}=\sum_{i=1}^{Y-1}F^{(s)}_{i}+P^{(s)},$

where $Y\sim\overline{\nu}$, $F_{i}\sim\varphi(\mathcal{T},L^{(s)})$,
$P\sim\mu_{s}$ are all independent. Besides, the starting point
$W_{0}^{{(s)}}$ is distributed as the sum of $\nu$ independent copies with law
$\varphi(\mathcal{T},L^{(s)})$ (and is independent of the increments of the
walk) minus $1$. Write $T^{(s)}_{-i}$ for the hitting time of $-i\leqslant 0$
by this left-continuous random walk. Consider the $i$-th car arrived on vertex
$S_{h}$ after all the cars whose arrival vertex is distinct from $S_{h}$ have
been parked. This car contributes to the flow at the root iff
$\\{T_{-i}^{(s)}>h\\}$. Summing over the $L\sim\mu$ cars that arrive at vertex
$S_{h}$, we find the representation:
$I(s,h)=\sum_{i=1}^{L}\mathds{1}_{\\{T_{-i}^{(s)}>h\\}}$, hence writing
$\mathbb{P}_{x}$ for the law of the walk $(W_{i}^{(s)})_{i\geqslant 0}$
started at $x$, we obtain:

$\mathbb{E}[I(s,h)]=\mathbb{E}\left[\sum_{i=1}^{L}\mathbb{P}_{W_{0}^{{(s)}}}(T^{(s)}_{-i}>h)\right],$

where $L\sim\mu$ is independent of the walk $W^{(s)}$. Performing the sum on
$h$ we get

$\displaystyle\sum_{h=0}^{\infty}\mathbb{E}[I(s,h)]$
$\displaystyle=\sum_{h=0}^{\infty}\mathbb{E}\Big{[}\sum_{i=1}^{L}\mathbb{P}_{W_{0}^{(s)}}(T_{-i}^{(s)}>h)\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{L}\mathbb{E}_{W_{0}^{(s)}}[T_{-i}^{(s)}]\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{L}(\mathbb{E}[W_{0}^{(s)}]+i)\;\mathbb{E}_{0}[T_{-1}^{(s)}]\Big{]}$
$\displaystyle=\left(\mathbb{E}[L]\mathbb{E}[W_{0}^{(s)}]+\mathbb{E}\Big{[}\frac{L(L+1)}{2}\Big{]}\right)\mathbb{E}_{0}[T_{-1}^{(s)}]$
$\displaystyle=\left(m\varPhi(s)+\frac{1}{2}(\sigma^{2}+m^{2}-m)\right)\mathbb{E}_{0}[T_{-1}^{(s)}].$
(10)

Furthermore, $\mathbb{E}[Z^{(s)}-1]\geqslant 0$ then the random walk $W^{(s)}$
has a positive (or zero) drift, hence $\mathbb{E}_{0}[T_{-1}^{(s)}]=\infty$.
On the other hand, when $\mathbb{E}[Z^{(s)}-1]<0$ i.e. if
$1-ms-\Sigma^{2}\varPhi(s)>0$ then the random walk $W^{(s)}$ has a strictly
negative drift, and an application of Wald’s lemma give:

$\mathbb{E}_{0}[T^{(s)}_{-1}]=\frac{1}{\mathbb{E}[1-Z^{(s)}]}=\frac{1}{1-ms-\Sigma^{2}\varPhi(s)}.$

Combining the previous displays, since $\varPhi$ is left-continuous (by
monotone convergence), we deduce that $\varPhi$ satisfies the integral
equation:

$(\star)\qquad\varPhi(0)=0,\quad\varPhi(t)=\int_{0}^{t}\mathrm{d}s\left(\frac{\frac{1}{2}(\sigma^{2}+m^{2}-m)+m\varPhi(s)}{1-ms-\Sigma^{2}\varPhi(s)}\right),\quad
0\leqslant t\leqslant t_{c}$

where $t_{c}=\inf\\{t\in[0,1]:1-mt-\Sigma^{2}\varPhi(t)<0\\}$, and
$\varPhi(t)=\infty$ for all $t_{c}<t\leqslant 1$. It is easy to check that the
function defined in the right-hand side of (8), call it $f(t)$ for the time
being, is a solution to $(\star)$ with $t_{c}=t_{\mathrm{max}}$.
We will first prove that $\varPhi(t)\geqslant f(t)$ for all $t\in[0,1]$. To
see this, notice that $\varPhi=f$ on $[0,t_{c}\wedge t_{\mathrm{max}})$ since
they satisfy the same well-posed differential equation. This also holds at
$t_{c}\wedge t_{\max}$ by left-continuity of $\varPhi$ and $f$. Since
$\varPhi(t)=\infty$ for $t>t_{c}$ the statement follows.
We now prove that $\varPhi(t)\leqslant f(t)$ for all $t\in[0,1]$. The problem
might come from the fact that $\varPhi$ may coincide with $f$ for small $t$
and then decide to “explode” to $+\infty$ at some $t_{c}<t_{\mathrm{max}}$
before $f$ does so. To show that this cannot happen, we introduce
$\varphi_{n}(t)$ the flux at the root for the tree $\mathcal{T}$ decorated
with $\mu_{t}$-arrivals restricted to those vertices at distance at most $n$
from the root. We write $\varPhi_{n}(t)=\mathbb{E}[\varphi_{n}(t)]$. Clearly
by monotone convergence we have $\varPhi_{n}(t)\uparrow\varPhi(t)$ as
$n\to\infty$ for any $t\geqslant 0$. We also have the bound

$\varPhi_{n}(t)\leqslant\mathbb{E}\Big{[}\sum_{\begin{subarray}{c}x\in\mathcal{T}\\\
|x|\leqslant
n\end{subarray}}L^{(t)}(x)\Big{]}=mt\cdot\mathbb{E}\Big{[}\sum_{\begin{subarray}{c}x\in\mathcal{T}\\\
|x|\leqslant n\end{subarray}}1\Big{]}=mtn,$

and dominated convergence ensures the map $t\mapsto\varPhi_{n}(t)$ is
continuous. Using the monotonicity of the parking process with respect to the
labeling, one can repeat the argument yielding to (9) and (10) and we get this
time the inequality

$\varPhi_{n}(t)\leqslant\int_{0}^{t}\mathrm{d}s\,\frac{\frac{1}{2}(\sigma^{2}+m^{2}-m)+m\varPhi_{n}(s)}{1-ms-\Sigma^{2}\varPhi_{n}(s)},$

valid as long as $(1-mt)-\Sigma^{2}\varPhi_{n}(t)\geqslant 0$. Using the
continuity of $\varPhi_{n}$ and the previous display, it is an easy exercise
to show that for every $n$ we have $\varPhi_{n}\leqslant f$ on $[0,t_{\max}]$
(including $t_{\max}$). Sending $n\to\infty$, we deduce that $\varPhi\leqslant
f$ on $[0,t_{\max}]$ as desired. ∎

###  3.2 The probability the root of a Galton–Watson tree is parked

Recall the characterization of the phases using $t_{\mathrm{max}}$ or
$\Theta$. In the next proposition we control the probability, under
$\mathcal{T}$, that the root vertex contains a car. This gives Line $(iii)$ of
Theorem 1 and combined with Lemma 2 shows that the flux is linear in the
supercritical regime (Line $(i)$ right in Theorem 1) and sublinear in the
critical regime (Line $(i)$ middle).

######  Proposition 2.

With the same notation as in Proposition 1 we have:

$\displaystyle\mathbb{P}(\varnothing\mbox{ is parked in
}\mathcal{T})=\left\\{\begin{array}[]{ccl}\displaystyle m&\mbox{ in the
critical or subcritical case,}\\\ <m&\mbox{ in the supercritical
case}.\end{array}\right.$

###### Proof.

We use the same notation and proceed as in the proof of Proposition 1 where
the cars arrive according to random times $A_{x}$ on the tree $\mathcal{T}$.
Putting $p_{t}=\mathbb{P}(\varnothing\mbox{ contains a car in
}(\mathcal{T},L^{(t)}))$ we have using the spine decomposition

$\displaystyle p_{t}=\int_{0}^{t}\mathrm{d}s\ \sum_{h\geqslant
0}\mathbb{P}(P(s,h)),$

where $P(s,h)$ is the event that in the labeled tree described in Figure 4,
one of the cars arriving on the vertex $S_{h}$ at time $s$ goes down the spine
and manages to park on the empty root vertex $\varnothing$. With the same
notation as in the display after Figure 4 we have
$P(s,h)=\bigcup_{i=1}^{L}\\{T_{-i}^{(s)}=h\\}$ under
$\mathbb{P}_{W_{0}^{(s)}}$ and so performing the sum over $h$ we deduce

$\displaystyle\sum_{h=0}^{\infty}\mathbb{P}(P(s,h))$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{L}\mathbb{P}_{W_{0}^{(s)}}(T^{(s)}_{-i}<\infty)\Big{]}=\mathbb{E}\Big{[}\sum_{i=1}^{L}\mathbb{P}_{0}\big{(}T^{(s)}_{-1}<\infty\big{)}^{W_{0}^{(s)}+i}\Big{]}$
$\displaystyle=\left\\{\begin{array}[]{ccc}\mathbb{E}[L]=m&\mbox{ if
}&s\leqslant t_{\max}\\\ <m&\mbox{ if }&s>t_{\max},\end{array}\right.$

where $t_{\max}$ is as in Proposition 1. The proposition follows by
integration. ∎

##  4 Remaining proofs

We now perform the remaining proofs required for Theorem 1, namely
establishing that $\varphi(\mathcal{T}_{n})$ converges in law in the
subcritical case and diverges in the critical case, as they do in the infinite
model $\mathcal{T}_{\infty}$. Even though the tree $\mathcal{T}_{\infty}$ is
the local limit of $\mathcal{T}_{n}$, the flux is not continuous in the local
topology and so transposing the properties from one model to the other
requires some extra care.

Since $\mathcal{T}_{n}\to\mathcal{T}_{\infty}$ in distribution in the local
sense as $n\to\infty$, we will suppose in this section by Skorokhod embedding
theorem that this convergence holds almost surely, also taking into account
the i.i.d. car arrivals on those trees. We will show that

$\displaystyle\varphi(\mathcal{T}_{n})\xrightarrow[n\to\infty]{a.s.}\varphi(\mathcal{T}_{\infty})$
(12)

which combined with the results of Section 2.1 finishes the proof of Theorem
1.

#### Critical and supercritical cases.

A moment of thought shows that we always have

$\displaystyle\liminf_{n\to\infty}\varphi(\mathcal{T}_{n})\geqslant\varphi(\mathcal{T}_{\infty}),\quad
a.s.$ (13)

but the inequality may be strict444Consider e.g. a line segment of length $n$
with $2n$ cars arriving on top, hence a flux $n$ at the root. This converges
towards the empty half-line with zero flux.. Anyway, in the critical and
supercritical case since $\varphi(\mathcal{T}_{\infty})=\infty$ by Section
2.1, we always have (12) as desired.

#### Subcritical case.

We suppose here that we are in the subcritical regime. The convergence (12) is
granted provided that we can show that the parking process is local, i.e. that
no car contributing to $\varphi(\mathcal{T}_{n})$ comes from far away. To this
end, let $\mathcal{V}_{n}$ be a uniform vertex of $\mathcal{T}_{n}$ and for
$M\geqslant 1$ denote the event

$\mathrm{Good}(M)=\\{\exists x\mbox{ ancestor of }\mathcal{V}_{n}\mbox{ at
height }\leqslant M\mbox{ which contains no car after parking}\\}.$

######  Lemma 3 (Locality of the parking process in the subcritical phase).

Suppose that $\mu$ is subcritical. For any $\varepsilon>0$, we can find
$M_{0}$ so that for all $M\geqslant M_{0}$ and all $n$ large enough we have

$\mathbb{P}(\mathcal{T}_{n}\in\mathrm{Good}(M))\geqslant 1-\varepsilon.$

###### Proof.

Fix $\varepsilon>0$. Recall the decomposition of $\mathcal{T}_{n}$ into three
parts $\mathrm{Top}(\mathcal{T}_{n},\mathcal{V}_{n})$,
$\mathrm{Up}(\mathcal{T}_{n},\mathcal{V}_{n})$ and
$\mathrm{Down}(\mathcal{T}_{n},\mathcal{V}_{n})$ from Section 2.3. We denote
these parts labeled by their associated car arrivals (on the vertices common
to two parts, we duplicate the car arrivals) by
$\mathrm{Top}_{n},\mathrm{Up}_{n}$ and $\mathrm{Down}_{n}$ to simplify
notation. We claim that the event $\mathrm{Good}(M)$ happens for
$\mathcal{T}_{n}$ if after proceeding to the parking separately in each part
we have

  * •

The flux at the root of $\mathrm{Top}_{n}$ is less than $M$,

  * •

The flux at the root of $\mathrm{Up}_{n}$ is less than $M$,

  * •

There are more than $3M$ empty spots on the “spine” of $\mathrm{Down}_{n}$ and
at least one of this spot is at height less than $M$.

Figure 5: On the right, the three events ensuring $\mathrm{Good}(M)$ happens
are realized for each of the three parts $\mathrm{Top}_{n}$, $\mathrm{Up}_{n}$
and $\mathrm{Down}_{n}$. After gluing back the pieces together and parking,
the flux coming down from $\mathrm{Top}_{n}$ and $\mathrm{Up}_{n}$ will be
absorbed by the empty spots on the spine of $\mathrm{Down}_{n}$, and an empty
spot will remain on the spine of $\mathrm{Down}_{n}$ at height less than $M$.

We now use our controls separately on each part to ensure that the
_complementary_ of each of the previous three events has probability at most
$\varepsilon/3$ when $M$ is large enough. For $\mathrm{Top}_{n}$. This tree
converges in distribution towards an (a.s. finite) unconditioned labeled
$\nu$-Galton–Watson tree $\mathcal{T}$, [8, Theorem 1.3], so defining
$A=A_{M}=\\{\varphi>M\\}$, we may choose $M$ large enough so that
$\mathbb{P}(\mathcal{T}\in A_{M})<\varepsilon/3$, which implies that for $n$
large enough, $\mathbb{P}(\mathrm{Top}_{n}\in A_{M})\leqslant\varepsilon/3$.
For $\mathrm{Up}_{n}$. By subcriticality, the flux is bounded in
$\mathcal{T}_{\infty}$, see Section 2.1, hence again there is $M$ large enough
so that for $n$ large enough,
$\mathbb{P}\left(\mathrm{Up}(\mathcal{T}_{\infty},S_{H_{n}})\in
A_{M}\right)\leqslant\delta$ for the value of $\delta$ linked with
$\varepsilon/3$ in Lemma 1, and therefore, for the same values of $n$, we have
$\mathbb{P}\left(\mathrm{Up}_{n}\in A_{M}\right)\leqslant\varepsilon/3$. For
$\mathrm{Down}_{n}$. It follows from Section 2.1 (using the same notation)
that in $\mathcal{T}_{\infty}$, the $h$-th vertex on the spine $S_{h}$ is a
free spot after parking if and only if we have

$\sup_{i\geqslant 0}(Z_{h}+\dots+Z_{h+i}-(i+1))=-1.$

Since the random walk with increments $(Z-1)$ has a strictly negative drift in
the subcritical case, it follows from standard consideration on random walks
and the fact that $H_{n}\to\infty$ in probability that the event

$\\{\exists i\leqslant M:S_{i}\mbox{ is a free
spot}\\}\cap\\{\\#\\{i\leqslant\lfloor H_{n}/2\rfloor:S_{i}\mbox{ is a free
spot}\\}\geqslant 3M\\}$

has probability at least $1-\delta$, provided that $M$ is large enough. We can
then argue as above and apply Lemma 1 to deduce that the third item on
$\mathrm{Down}_{n}$ holds with probability asymptotically larger than
$1-\varepsilon/3$. ∎

From the last lemma, the convergence $\mathcal{T}_{n}\to\mathcal{T}_{\infty}$
as labeled trees, and the fact that $\mathcal{T}_{\infty}$ has a single end,
it is easy to see that we indeed have
$\varphi(\mathcal{T}_{n})\to\varphi(\mathcal{T}_{\infty})$ a.s.

##  5 Comments and extensions

We mention here a few possible developments that we hope to pursue in the
future.

#### On the critical case.

As mentioned in the introduction, probably the most interesting question is to
study the critical case $\Theta=0$. We tackle this problem in a forthcoming
work in the case of plane trees and study the scaling limit of the
renormalized flux on $\mathcal{T}_{n}$. In “generic” situations, the flux is
of order $n^{1/3}$ on $\mathcal{T}_{n}$ and the components of parked vertices
form a stable tree of parameter $3/2$. The components themselves are described
by the growth-fragmentation trees considered in [4] in the context of random
planar maps. We also find a one-parameter family of possible scaling limits
when the car arrivals have a “heavy tail” $\mu([k,\infty))\sim ck^{-\alpha}$
with $\alpha\in(2,3)$, which is again linked to the growth-fragmentation trees
considered in [3].

#### Sharpness of the phase transition.

It is natural to expect that the phase transition for the parking is “sharp”
in the sense that many observables undergo a drastic change when going from
the subcritical to the supercritical regime. For example, we expect that
$\mathbb{P}(\varphi(\mathcal{T}_{n})=0)$ decays exponentially fast in the
supercritical regime, a fact known only in case $\mu$ and $\nu$ are Poisson
through explicit computations, see Corollary 4.11 in [11]. We believe this is
related to a large deviations principle for the fringe subtree distribution
that could be of independent interest. Following [6], in the subcritical
regime this time, we also conjecture that
$\mathrm{Var}(\varphi(\mathcal{T}))<\infty$ and that if $\mu$ has an
exponential tail, then $\varphi(\mathcal{T})$ has an exponential tail.

#### Near-critical dynamics.

Also, in the first line of the table in 1, one could approach the critical
case by letting $\Theta=\Theta(n)$ approach 1 with $n$ while looking at
$\mathcal{T}_{n}$ and try to delimit the regimes where
$\varphi(\mathcal{T}_{n})/\mathbb{E}[\varphi(\mathcal{T}_{n})]$ has a random
limit (the critical window that extends the critical regime) or a non random
limit (the so called near-critical regimes). We hope to be able to study the
dynamical scaling limits of the parking process in the critical window and
compare it with the multiplicative coalescent which appears when studying the
creation of the giant component in Erdös–Rényi random graphs.

## References

  * [1] Romain Abraham and Jean-Francois Delmas.  Local limits of conditioned Galton-Watson trees: the infinite spine case.  Electron. J. Probab., 19:19 pp., 2014.
  * [2] David J. Aldous and Antar Bandyopadhyay.  A survey of max-type recursive distributional equations.  Ann. Appl. Probab., 15(2):1047–1110, 05 2005.
  * [3] Jean Bertoin, Timothy Budd, Nicolas Curien, and Igor Kortchemski.  Martingales in self-similar growth-fragmentations and their connections with random planar maps.  Probability Theory and Related Fields, 172(3):663–724, Dec 2018\.
  * [4] Jean Bertoin, Nicolas Curien, and Igor Kortchemski.  Random planar maps and growth-fragmentations.  Ann. Probab., 46(1):207–260, 01 2018.
  * [5] Qizhao Chen and Christina Goldschmidt.  Parking on a random rooted plane tree.  ArXiv e-prints, 2019.
  * [6] Christina Goldschmidt and Michał Przykucki.  Parking on a random tree.  Combinatorics, Probability and Computing, 28(1):23–45, 2019.
  * [7] Yueyun Hu, Bastien Mallein, and Michel Pain.  An exactly solvable continuous-time Derrida–Retaux model.  Communications in Mathematical Physics, May 2019.
  * [8] Svante Janson.  Asymptotic normality of fringe subtrees and additive functionals in conditioned galton–watson trees.  Random Structures & Algorithms, 48(1):57–101, 2016.
  * [9] Owen D. Jones.  Runoff on rooted trees  Journal of Applied Probability, 56(4):1065–1085, 2019.
  * [10] Igor Kortchemski and Loïc Richier.  The boundary of random planar maps via looptrees, 2018.
  * [11] Marie-Louise Lackner and Alois Panholzer.  Parking functions for mappings.  Journal of Combinatorial Theory, Series A, 142:1 – 28, 2016.
  * [12] Russell Lyons and Yuval Peres.  Probability on Trees and Networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, New York, 2016.  Available at http://pages.iu.edu/~rdlyons/.
  * [13] Alois Panholzer.  Parking function varieties for combinatorial tree models.  ArXiv e-prints, 2020.