# Parking on a tree

Consider the following particle system. We are given a uniform random

rooted tree on vertices labelled by $[n] = \{1,2,\ldots,n\}$, with edges

directed towards the root. Each node of the tree has space for a single

particle (we think of them as cars). A number $m \le n$ of cars arrives

one by one, and car $i$ wishes to park at node $S_i$, $1 \le i \le m$,

where $S_1, S_2, \ldots, S_m$ are i.i.d. uniform random variables on

$[n]$. If a car arrives at a space which is already occupied, it

follows the unique path oriented towards the root until the first time

it encounters an empty space, in which case it parks there; otherwise,

it leaves the tree. Let $A_{n,m}$ denote the event that all m cars find

spaces in the tree. Lackner and Panholzer proved (via analytic

combinatorics methods) that there is a phase transition in this model.

Set $m = [\alpha n]$. Then if $\alpha \le 1/2$, $P(A_{n,[\alpha n]} \to

\frac{\sqrt{1-2\alpha}}{1-\alpha}, whereas if $\alpha > 1/2$ we have

$P(A_{n,[\alpha n]}) \to 0$. (In fact, they proved more precise

asymptotics in $n$ for $\alpha \ge 1/2$.) In this talk, I will give a

probabilistic explanation for this phenomenon, and an alternative proof

via the objective method.

Based on joint work in progress with Michal Przykucki (Oxford).