Parking on a random tree

DOI10.1017/S0963548318000457MaRDI QIDQ5219309zbMATH OpenOpenAlexWikidataFDO

Authors Christina Goldschmidt, Michał Przykucki

Publication date 11 March 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.08786

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: Consider a uniform random rooted tree on vertices labelled by $[n]=1,2,ldots,n$, with edges directed towards the root. We imagine that each node of the tree has space for a single car to park. A number $mlen$ 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 oriented 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=[alphan]$ and let $A_{n,alpha}$ denote the event that all $[alphan]$ 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 $alphale1/2$, we have $mathbbP(A_{n,alpha})ofracsqrt1-2alpha1-alpha$, whereas if $alpha>1/2$ we have $mathbbP(A_{n,alpha})o0$. We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we are led to 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($alpha$) number of cars arrive at each vertex. Let $X$ be the number of cars which visit the root of the tree. Then for $alphale1/2$, we have $mathbbE[X]leq1$, whereas for $alpha>1/2$, we have $mathbbE[X]=infty$. This discontinuous phase transition turns out to be a generic phenomenon in settings with an arbitrary offspring distribution of mean at least 1 for the tree and arbitrary arrival distribution.

Recommendations

• Parking on a random rooted plane tree
• Parking on a random tree
• scientific article; zbMATH DE number 7643620
• Parking on supercritical Galton-Watson trees
• Sharpness of the phase transition for parking on random trees

Cites work

• A survey of max-type recursive distributional equations
• An Occupancy Discipline and Applications
• Building uniformly random subtrees
• Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component
• scientific article; zbMATH DE number 3711987 (Why is no real title available?)
• scientific article; zbMATH DE number 1182849 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Hyperplane arrangements, interval orders, and trees.
• On the Lambert \(w\) function
• Parking functions and noncrossing partitions
• Parking functions for mappings
• Random walk on the incipient infinite cluster on trees
• Recurrence of distributional limits of finite planar graphs
• SOME RESULTS FOR SKIP-FREE RANDOM WALK
• Subdiffusive behavior of random walk on a random cluster

Cited in

(27)

• An exactly solvable continuous-time Derrida-Retaux model
• Parking function varieties for combinatorial tree models
• The Derrida-Retaux conjecture on recursive models
• Two-type annihilating systems on the complete and star graph
• The sustainability probability for the critical Derrida-Retaux model
• Diffusion-limited annihilating systems and the increasing convex order
• Parking on a random rooted plane tree
• Parking on transitive unimodular graphs
• A max-type recursive model: some properties and open questions
• Parking on supercritical Galton-Watson trees
• Runoff on rooted trees
• scientific article; zbMATH DE number 7643620 (Why is no real title available?)
• Stretched exponential decay for subcritical parking times on
• Sharpness of the phase transition for parking on random trees
• Parking on the infinite binary tree
• Parking on the integers
• The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses
• Universality: random matrices, random geometry and SPDEs. Abstracts from the workshop held May 29 -- June 4, 2022
• The dual Derrida-Retaux conjecture
• Parking on Cayley trees and frozen Erdős-Rényi
• Particle density in diffusion-limited annihilating systems
• Parking on supercritical geometric Bienaymé-Galton-Watson trees
• Last car decomposition of planar maps
• Asymptotic behavior of the generalized Derrida-Retaux recursive model
• Parking on trees with a (random) given degree sequence and the frozen configuration model
• Where do (random) trees grow leaves?
• Parking on a random tree

This page was built for publication: Parking on a random tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219309)