Résumé : Consider the following particle system. We are given a uniform random rooted tree on vertices labelled by {1,2,...,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 of cars arrives one by one, and car i wishes to park at node S_i, where S₁, S₂,... , S_m are i.i.d. uniform random variables on {1,2,...,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 = [α n]. Then if α ≤ 1/2, P(A_{n,[α n]}) → sqrt(1-2α)/(1-α), whereas if α > 1/2 we have P(A_{n,[α n]}) → 0. (In fact, they proved more precise asymptotics in n for α ≥ 1/2.) In this talk, I will give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Time permitting, I will also discuss some generalisations.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr