Parking On A Random 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 arrive 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 wishes to park at a space which is already occupied, it follows the unique path oriented towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, 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 = \lfloor \alpha n \rfloor$. Then if $\alpha \le 1/2$, $\mathbb{P}(A_{n,\lfloor \alpha n \rfloor}) \to \frac{\sqrt{1-2\alpha}}{1-\alpha}$, whereas if $\alpha > 1/2$ we have $\mathbb{P}(A_{n,\lfloor \alpha n \rfloor}) \to 0$. In this talk, we will give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method.

Joint work with Christina Goldschmidt.