The phase transition for parking on Galton--Watson trees

Nicolas Curien, Olivier Hénard

Published 2019-12-12Version 1

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.