Analysis and Probability Seminar: Christina Goldschmidt
Wednesday 6 March 2019, 3:15pm to 4:15pm
Venue
PSC - PSC A54 - View MapOpen to
Postgraduates, Staff, UndergraduatesRegistration
Registration not required - just turn upEvent Details
Parking on a tree
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 ≤ n of cars arrives one by one, and car i wishes to park at node Si, 1 ≤ i ≤ m, where S1, S2, ..., Sm are i.i.d. uniform random variables on [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]) → \frac{\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.Joint work with Michał Przykucki (Birmingham), to appear in Combinatorics, Probability and Computing.
Speaker
Christina Goldschmidt
University of Oxford
Contact Details
Name | Dirk Zeindler |
Telephone number |
+44 1524 593644 |