Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 21 mars 2018 à 10h00 en B405, Christina Goldschmidt nous parlera de : Parking on a tree

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 Si, where S1, S2,... , Sm 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 An,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(An,[α n]) → sqrt(1-2α)/(1-α), whereas if α > 1/2 we have P(An,[α 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 : lundi 19 février 2018 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at