Parking on the Random Recursive Tree

2025/01/06 by Alice Contat, Contat, Alice, Lucile Laulin +1 · 1 citation
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Mathematical Dynamics and Fractals #Data Management and Algorithms

paper · pdf · doi:10.48550/arxiv.2501.03195

Abstract

We study the parking process on the random recursive tree. We first prove that although the random recursive tree has a non-degenerate Benjamini--Schramm limit, the phase transition for the parking process appears at density 0. We then identify the critical window for appearance of a positive flux of cars with high probability. In the case of binary car arrivals, this happens at density log (n)^-2+o(1) where n is the size of the tree. This is the first work that studies the parking process on trees with possibly large degree vertices.

Cited by

• Short survey of results and open problems for parking problems on random trees

Related

• Parking on a random rooted binary tree
• Parking On A Random Rooted Plane Tree
• Sharpness of the phase transition for parking on random trees
• Short survey of results and open problems for parking problems on random trees
• Parking on the infinite binary tree