Parking on a random rooted plane tree

DOI10.3150/20-BEJ1227MaRDI QIDQ2214237zbMATH OpenOpenAlexFDO

Authors Qizhao Chen, Christina Goldschmidt

Publication date 7 December 2020

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.03816, https://projecteuclid.org/euclid.bj/1605841237

zbMATH Keywords

parkingphase transitionrandom trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: In this paper, we investigate a parking process on a uniform random rooted plane tree with $n$ vertices. Every vertex of the tree has a parking space for a single car. Cars arrive at independent uniformly random vertices of the tree. If the parking space at a vertex is unoccupied when a car arrives there, it parks. If not, the car drives towards the root and parks in the first empty space it encounters (if there is one). We are interested in asymptotics of the probability of the event that all cars can park when $lflooralphanfloor$ cars arrive, for $alpha>0$. We observe that there is a phase transition at $alph{a}_c:=sqrt2-1$: if $alpha<alph{a}_c$ then the event has positive probability, whereas for $alpha>alph{a}_c$ it has probability 0. Analogous results have been proved by Lackner and Panholzer, Goldschmidt and Przykucki, and Jones for different underlying random tree models.

Review text

This paper investigates a parking process on a uniform random rooted plane tree with \(n\) vertices. Every vertex of the tree has a parking space for a single car. Cars arrive at independent uniformly random vertices of the tree. If the parking space at a vertex is unoccupied when a car arrives there, it parks. If not, the car drives towards the root and parks in the first empty space it encounters if there is one. The asymptotic of the probability of the event that all cars can park when \(\lfloor \alpha n \rfloor\) cars arrive for \(\alpha > 0\) is given. The result shows that the event has positive limiting probability if \(\alpha \leq \alpha_c=\sqrt{2}-1\), whereas its probability tends to 0 for \(\alpha > \alpha_c\).

Recommendations

• Parking on a random tree
• Parking on a random tree
• scientific article; zbMATH DE number 7643620
• Parking on supercritical Galton-Watson trees
• A combinatorial approach for discrete car parking on random labelled trees

Cites work

• An Occupancy Discipline and Applications
• Building uniformly random subtrees
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Parking functions for mappings
• Parking on a random tree
• Runoff on rooted trees
• SOME RESULTS FOR SKIP-FREE RANDOM WALK
• Subdiffusive behavior of random walk on a random cluster

Cited in

(19)

• Parking function varieties for combinatorial tree models
• Diffusion-limited annihilating systems and the increasing convex order
• Parking on transitive unimodular graphs
• Parking on supercritical Galton-Watson trees
• Brussels sprouts, noncrossing trees, and parking functions
• A binomial splitting process in connection with corner parking problems
• Parking on a random tree
• scientific article; zbMATH DE number 7643620 (Why is no real title available?)
• Parking functions, empirical processes, and the width of rooted labeled trees
• 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
• Parking on Cayley trees and frozen Erdős-Rényi
• Burning cars in a parking lot
• Last car decomposition of planar maps
• Parking on trees with a (random) given degree sequence and the frozen configuration model
• Parking on a random tree
• Multilayer parking with screening on a random tree

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

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