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

2025/05/13 by Andrej Srakar, Srakar, Andrej
Computer Science · Mathematics · #60-02 #Complexity and Algorithms in Graphs #FOS: Mathematics #G.3 #Optimization and Search Problems #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2505.15826

openalex publication_date 2025/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Parking problems derive from works in combinatorics by Konheim and Weiss in the 1960s. In a memorable contribution, Lackner and Panholzer (2016) studied parking on a random tree and established a phase transition for this process when \(m ≈ (n)/(2)\). This relates to the renowned result by David Aldous of convergence results on Erdős-Renyi random graphs of order \(n^(2)/(3)\). In a series of recent articles, Contat and coauthors have studied the problem in various random tree contexts and derived several novel scaling limit and phase transition results. We survey the present state-of-the-art of this literature and point to its extensions, open directions and possibilities, in particular related to the study of problem in different metric topologies. My intent it to point to importance of this line of research and novel open problems for future study.

Citations

• Parking on the Random Recursive Tree
• Self-similar Markov trees and scaling limits
• Critical cluster volumes in hierarchical percolation
• Sharpness of the phase transition for parking on random trees
• Some natural extensions of the parking space
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• Extending the parking space
• Parking Spaces
• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron

Related

• Parking on the Random Recursive Tree
• Sharpness of the phase transition for parking on random trees
• Parking on Cayley trees & Frozen Erdös-Rényi
• Parking on a random rooted binary tree
• Parking On A Random Rooted Plane Tree