Parking on Cayley trees & Frozen Erdös-Rényi

Abstract

Consider a uniform rooted Cayley tree $T_n$ with $n$ vertices and let $m$ cars arrive sequentially, independently, and uniformly on its vertices. Each car tries to park on its arrival node, and if the spot is already occupied, it drives towards the root of the tree and parks as soon as possible. Lackner & Panholzer (arXiv:1504.04972) established a phase transition for this process when $m\approx \frac{n}{2}$. In this work, we couple this model with a variant of the classical Erdös-Rényi random graph process. This enables us to describe the phase transition for the size of the components of parked cars using a modification of the multiplicative coalescent which we name the frozen multiplicative coalescent. The geometry of critical parked clusters is also studied. Those trees are very different from Bienaymé-Galton-Watson trees and should converge towards the growth-fragmentation trees canonically associated to the $3/2$-stable process that already appeared in the study of random planar maps.

arXiv comment26 figures

References in corpus (14)

• Conditional Distribution of Heavy Tailed Random Variables on Large Deviations of their Sum
• Mean field frozen percolation
• Rigid representations of the multiplicative coalescent with linear deletion
• The phase transition for parking on Galton--Watson trees
• Diffusion-limited annihilating systems and the increasing convex order
• The Derrida--Retaux conjecture on recursive models
• Expansion of percolation critical points for Hamming graphs
• Fighting Fish: enumerative properties
• Parking on supercritical Galton-Watson trees
• Scaling limit of dynamical percolation on critical Erdös-Rényi random graphs
• Parking On A Random Rooted Plane Tree
• Parking Functions on Directed Graphs and Some Directed Trees
• Enumeration of fully parked trees
• Surprising identities for the greedy independent set on Cayley trees