Parking on supercritical geometric Bienaymé--Galton--Watson trees

2024/02/08 by Linxiao Chen, Chen, Linxiao, Alice Contat +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2402.05612

Abstract

Consider a supercritical Bienaymé--Galton--Watson tree T with geometric offspring distribution. Each vertex of this tree represents a parking spot which can accommodate at most one car. On the top of this tree, we add (A_u : u ∈ T) i.i.d. non negative integers sampled according to a given law μ, which are the car arrivals on T. Each car tries to park on its arriving vertex and if the spot is already occupied, it drives towards the root and takes the first available spot. If no spot is found, then it exits the tree without parking. In this paper, we provide a criterion to determine the phase of the parking process (subcritical, critical, or supercritical) depending on the generating function of μ.

Related

• Parking on supercritical Galton-Watson trees
• Parking on the infinite binary tree
• Parking on trees with a (random) given degree sequence and the Frozen configuration model
• Sharpness of the phase transition for parking on random trees
• Enumeration of fully parked trees