Parking on a random tree
Consider a uniform random rooted labelled tree on n vertices. We imagine that each node of the tree has space for a single car to park. A number m ≤ n of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it fol...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Cambridge University Press
2018
|
| _version_ | 1826258046713593856 |
|---|---|
| author | Goldschmidt, C Przykucki, M |
| author_facet | Goldschmidt, C Przykucki, M |
| author_sort | Goldschmidt, C |
| collection | OXFORD |
| description | Consider a uniform random rooted labelled tree on n vertices. We imagine that each node of the tree has space for a single car to park. A number m ≤ n of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider m = ⌊α n⌋ and let An,α denote the event that all ⌊α n⌋ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if α ≤ 1/2, we have , whereas if α > 1/2 we have . We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we consider the following variant of the problem: take the tree to be the family tree of a Galton–Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson(α) number of cars arrive at each vertex. Let X be the number of cars which visit the root of the tree. We show that undergoes a discontinuous phase transition, which turns out to be a generic phenomenon for arbitrary offspring distributions of mean at least 1 for the tree and arbitrary arrival distributions. |
| first_indexed | 2024-03-06T18:27:50Z |
| format | Journal article |
| id | oxford-uuid:0897bfee-1e40-46b3-9042-ea00da728b91 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:27:50Z |
| publishDate | 2018 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | oxford-uuid:0897bfee-1e40-46b3-9042-ea00da728b912022-03-26T09:13:40ZParking on a random treeJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0897bfee-1e40-46b3-9042-ea00da728b91Symplectic Elements at OxfordCambridge University Press2018Goldschmidt, CPrzykucki, MConsider a uniform random rooted labelled tree on n vertices. We imagine that each node of the tree has space for a single car to park. A number m ≤ n of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider m = ⌊α n⌋ and let An,α denote the event that all ⌊α n⌋ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if α ≤ 1/2, we have , whereas if α > 1/2 we have . We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we consider the following variant of the problem: take the tree to be the family tree of a Galton–Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson(α) number of cars arrive at each vertex. Let X be the number of cars which visit the root of the tree. We show that undergoes a discontinuous phase transition, which turns out to be a generic phenomenon for arbitrary offspring distributions of mean at least 1 for the tree and arbitrary arrival distributions. |
| spellingShingle | Goldschmidt, C Przykucki, M Parking on a random tree |
| title | Parking on a random tree |
| title_full | Parking on a random tree |
| title_fullStr | Parking on a random tree |
| title_full_unstemmed | Parking on a random tree |
| title_short | Parking on a random tree |
| title_sort | parking on a random tree |
| work_keys_str_mv | AT goldschmidtc parkingonarandomtree AT przykuckim parkingonarandomtree |