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

Andrej Srakar

REVIEW 4 major objections 6 minor 27 references

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

T0 review · 4 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The parking problem on random trees undergoes a sharp phase transition when the number of drivers approaches half the number of vertices, and its critical scaling limit is the Brownian growth-fragmentation tree.

desk verdict Useful bibliography but the paper's central open-problem claim is contradicted by a theorem it cites; needs major revision before it can serve as a survey. read the letter →

arxiv 2505.15826 v1 pith:6IC5BNX5 submitted 2025-05-13 math.PR

Andrej Srakar This is my paper · ORCID

classification math.PR MSC 60-02

keywords parkingfunctionsrandomtreesphasetransitionscalinglimitsBrowniangrowth-fragmentationtreeGromov-Hausdorff-ProkhorovtopologyfrozenErdős-RényimodelBienaymé-Galton-Watson

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This survey assembles the known results on parking problems on random trees and presents them as a single storyline with a sharp phase transition. If $m$ drivers arrive on a random tree with $n$ vertices, almost all park when $m\lesssim n/2$; once $m$ crosses $n/2$, a positive fraction of drivers fail, and at the critical point the fully parked tree has a universal scaling limit. The survey's forward-looking claim is that the natural next step is to study these limits under other metric topologies, especially Gromov–Hausdorff–Prokhorov convergence, and to connect the results to random planar maps. A careful reader would care because the same transition and the same limiting objects appear across several different random-tree models, which points to a robust underlying mechanism.

What carries the argument

The central object is the tree parking function: a length-$m$ sequence of preferred vertices on a rooted tree in which every driver can move toward the root and eventually reach a vacant vertex. The phase transition is located by comparing $m$ with $n/2$, and the counting formulas of Lackner and Panholzer make this comparison exact for Cayley trees. At the scaling level the argument is carried by catalytic functional equations for the flux of cars: universal singularity exponents $p^{-3/2}$ and $p^{-5/2}$ select the limiting trees $\mathcal{T}_{1/2}$ and $\mathcal{T}_{3/2}$, where $\mathcal{T}_{3/2}$ is the Brownian growth-fragmentation tree. Convergence is stated in the Gromov–Hausdorff–Prokhorov hypograph topology, and the accompanying frozen Erdős–Rényi coupling explains why the same critical objects reappear across models.

What would settle it

A reader could settle the claimed universality by computing the singularity exponent of the flux generating function at criticality for Poisson car arrivals on critical Cayley trees with $m=n/2$; if the exponent is not $p^{-5/2}$, or if the reconstructed rooted metric tree converges to Aldous's Brownian continuum random tree instead of the Brownian growth-fragmentation tree, the claim fails.

Watch

Extended reading notes

Core claim

The central discovery is that the parking process on a random tree changes behavior at $m\approx n/2$: in the subcritical regime almost every driver parks, at criticality the number of unsuccessful drivers fluctuates on scale $n^{1/6}$, and in the supercritical regime a positive fraction of drivers never park. When critical trees are conditioned to be fully parked, their scaling limit is the Brownian growth-fragmentation tree $\mathcal{T}_{3/2}$, a self-similar Markov tree associated with the $3/2$-stable process, rather than Aldous's Brownian continuum random tree; the limit is stated under Gromov–Hausdorff–Prokhorov hypograph convergence and rests on universal asymptotics $p^{-3/2}$ below criticality and $p^{-5/2}$ at criticality. The paper's own contribution is to make this collection of results visible as a research program and to name the missing pieces, especially the behavior of parking limits in other metric topologies and the connection to random planar maps.

Load-bearing premise

The survey's agenda assumes that the open problems it lists are still open—particularly parking limits under other ways of measuring distance between trees—and it does not systematically show that the wider literature has not already addressed them.

Editorial extensions

If this is right

Below $m\approx n/2$ the parking process is subcritical: almost all drivers park, and the number of parked cars is close to $m$.
At criticality, the number of drivers who fail to park fluctuates on scale $n^{1/6}$, and a conditioned fully parked tree converges to the Brownian growth-fragmentation tree $\mathcal{T}_{3/2}$ rather than to Aldous's Brownian continuum random tree.
The singularity exponents $p^{-3/2}$ (subcritical) and $p^{-5/2}$ (critical) are universal across a broad class of car-arrival laws, not just the specific cases computed so far.
If the metric-topology program goes through, parking on random trees will connect to inhomogeneous continuum random trees and to the literature on random planar maps.
The open problems inherited from Lackner and Panholzer—total displacement, defective parking functions, and restricted parking functions—remain natural targets for probabilistic analysis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension would be to run the parking process on critical Cayley trees with power-law car arrivals and compare the reconstructed metric tree with the Brownian growth-fragmentation tree; the survey identifies heavy tails as a boundary case but does not predict the outcome.
If the Gromov–Hausdorff–Prokhorov program succeeds, the critical parking tree could become a standard example of a random metric space that is not the Brownian continuum random tree yet arises from a simple discrete parking rule.
The survey's hint at queueing theory can be made concrete by reading total displacement as a waiting-time or busy-period statistic in a rooted queue, which would bring queueing results to bear on parking problems; the paper does not develop this mapping.
The contrast between the $n/2$ transition on Cayley trees and the density-zero transition on random recursive trees suggests that degree growth changes the critical window fundamentally; one could test whether intermediate degree sequences interpolate between these two regimes.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a short survey with a genuinely useful bibliography, but it is not publishable as is. The advertised open direction—parking problems in different metric topologies—is undercut by Theorem 4 in the paper's own Section 4, where the cited Contat–Curien result proves convergence in Gromov–Hausdorff–Prokhorov hypograph topology. Section 5 says such questions are "largely unaddressed" and the abstract offers them as the main future direction. That is an internal contradiction, and it survives any copy edit.

What is new here is limited to the packaging. The survey does reasonably gather the recent Contat and coauthor results and places them next to Lackner and Panholzer, and it points to connections with random planar maps, frozen Erdős–Rényi models, and growth-fragmentation trees. Those pointers are useful for someone entering the area. But the actual content is a compilation, with no new theorems, derivations, or data. The open-problems list in Section 5 largely restates Lackner–Panholzer items 4–6 with slight reframing.

The soft spots are not minor. The manuscript has many transcription errors ('integerdivide', 'quotesingle.ts1s', repeated 'E_υ[m] ≤ 1' in Contat's Theorem 2, the Pollak map garbled, and a reference to the map from PF_n to Z_{n+1}^{n-1} that doesn't match the written formula). These are not just cosmetic: they make the survey untrustworthy for a reader who does not already know the literature. It also does not establish systematically that the open problems are still open; several references appear in the list but are never cited in the text.

Who should read it? A newcomer to the area might use it as a rough map, but only with the original papers open next to it. As a submitted survey, I would not send it to a referee in this state. It needs a careful revision: fix the contradiction about GHP topology, clean up the LaTeX damage, verify each theorem statement against the source, and prune or cite the dangling references. After that, a shorter or more careful version could be a useful contribution. My recommendation: desk reject with an invitation to resubmit after major revisions.

Referee Report

4 major / 6 minor

Summary. The paper is a short survey of parking problems on random trees. It begins in Section 2 with classical combinatorial parking functions, including the Konheim-Weiss occupancy model, Pollak's bijection, and representation-theoretic connections (Haiman; Berget-Rhoades). Section 3 summarizes Lackner and Panholzer's enumeration results for tree and mapping parking functions, including the phase transition near m ≈ n/2 and their list of open problems. Section 4 surveys recent work by Contat and coauthors: phase transitions on Bienaymé-Galton-Watson trees, the frozen Erdős-Rényi/Cayley-tree coupling, parking on the infinite binary tree, geometric BGW trees, random recursive trees, and the Contat-Curien scaling limit of fully parked trees to the Brownian growth-fragmentation tree. Section 5 proposes future directions, most prominently the study of parking problems in different metric topologies, connections to random planar maps, total displacement, defective parking functions, and various enumeration problems.

Significance. The survey is timely: it collects the main recent papers in an active area and highlights the conceptual bridge between parking functions, multiplicative coalescents, and random planar maps. It is useful as a starting bibliography. However, the paper as written does not yet function as a reliable survey. The central advertised open direction is contradicted by a theorem quoted in the paper itself, and at least one key theorem statement from the recent literature is transcribed with corrupted assumptions. These are fixable, but they are not cosmetic: they concern the paper's main message. The manuscript also makes several unsupported claims about which topics 'remain underaddressed.' With careful revision, the survey could be a valuable resource.

major comments (4)

[§5 vs. §4 (Theorem 4)] The abstract and Section 5 present 'the study of problem in different metric topologies' as the key open direction, and Section 5 states that 'issues of studying parking problems in different metric topologies remains largely unaddressed.' Yet Section 4 quotes Theorem 4 of Contat and Curien (2025) as establishing convergence of fully parked critical trees to the Brownian growth-fragmentation tree 'for the Gromov-Hausdorff-Prokhorov hypograph convergence.' GHP hypograph convergence is precisely a metric-topology convergence framework, so the cited theorem directly contradicts the claim that this direction is unaddressed. If the intended open problem is more specific (e.g., other topologies, heavy-tailed arrivals, or convergence of objects other than fully parked trees), the text must state that. As written, the paper's central novelty claim is internally inconsistent.
[§4, Theorem 2 (Contat, 2023)] The statement of the phase-transition theorem for the frozen configuration model is corrupted. The assumptions read 'with E_υ[m] ≤ 1 and Eυ[m] ≤ 1', which is redundant, and the displayed formula 'Θ = (1 − Eυ [m])2−Σ2Eυ [σ 2+m2−m]' is missing parentheses and exponents, making the phase-transition criterion unreadable. Since the theorem is one of the main results surveyed, the author must verify the statement against the original paper and correct it. This is not a mere typo: the criterion 'Cλ = 0 if and only if Θ ≥ 0' is the content of the result.
[§4, Corollary 3 (Contat and Curien, 2025)] The displayed universality result uses F(x,y), [y^p]F(x,y), W_x^p, and the auxiliary quantities x_cr and y_x^cr without defining them anywhere in the survey. A reader cannot understand the statement or its role in the subsequent scaling-limit theorem. At minimum, the survey should say that F is the relevant bivariate generating function of fully parked trees (or for the catalytic equation) and should list the 'standing assumptions' that are invoked. As it stands, the theorem is presented as a black box with undefined notation.
[§5, open-problems list] The survey does not substantiate its claims that certain problems 'remain underaddressed.' For example, Section 5 lists total displacement, individual displacement, defective parking functions, and restricted enumeration, but it only repeats Lackner and Panholzer's 2016 open problems without reporting what has happened since and without citing the substantial ordinary-parking-functions literature on these quantities. A survey of open problems should either document prior partial results or state explicitly that the open question is whether these quantities can be analyzed in the random-tree setting. Without that, the reader cannot judge the novelty of the proposed agenda.

minor comments (6)

[Abstract and §1] 'My intent it to point' is ungrammatical; 'problem in different metric topologies' should be plural. The reference to Aldous's n^{2/3} result should be phrased as a scaling of component sizes at criticality, not of the random graphs themselves.
[§2] The author names are misspelled: 'Kovalinka and Towari' should be Konvalinka and Tewari, and 'Foata in Riorda' should be Foata and Riordan.
[§2] There are LaTeX artifacts in the text, including 'quotesingle.ts1s' and '/integerdivide', and several displayed formulas (e.g., Theorem 1's expression for E{s_k}) are typeset ambiguously with missing parentheses and fraction bars. These must be cleaned before the paper can be read.
[§4] There is a typo 'there esists' in the paragraph after Theorem 2, and the phrase 'Benjamini-Schramm quenched' should probably be 'Benjamini-Schramm convergence, quenched' or similar.
[References] Several entries have corrupted page ranges or missing separators, for example [3] '647706', [15] '4452', and [18] '1776'. In addition, [22] (Kung and Yan) and [24] (Macdonald) are listed but never cited in the text; either cite them or remove them.
[§5] The phrase 'provide an at present blank field of research' is awkward; consider 'remain largely unexplored' or similar.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper is an expository survey whose load-bearing statements are cited from independent external sources, with no fitted inputs or self-citation chains.

full rationale

The paper performs no original derivations and introduces no fitted parameters, normalization choices, or predictions of its own. Its mathematical content consists of summaries and quotations of results by Konheim and Weiss, Lackner and Panholzer, Contat, Curien, Chen, Laulin, and others. These are independent, citable, externally checkable results rather than premises defined in terms of the survey's own conclusions. There is no self-citation by the present author that carries any load-bearing argument, and no ansatz is smuggled in through a citation chain. The nearest issue to a consistency problem is that Section 5 describes the study of parking problems in different metric topologies as 'largely unaddressed' while Section 4 correctly reports Theorem 4 of Contat and Curien (2025), which establishes convergence of fully parked critical trees in the Gromov-Hausdorff-Prokhorov hypograph topology. This is an internal tension or imprecision in the framing of the open-problems agenda, not circularity: the cited theorem is external evidence, not an input defined by the survey, and the survey does not claim to derive that theorem from its own statements. Therefore the paper's account is self-contained as a survey and no circular step can be exhibited from its equations or citations.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

This is a survey, so it introduces no new free parameters or invented entities. It depends on standard mathematical background and on the correctness of the original theorems it summarizes. The axiom entries capture the main external results that the survey's narrative rests on.

assumptions (4)

standard math Pollak bijection: the map from PF_n to Z_{n+1}^{n-1} is a bijection.
Stated in Section 2 without proof, attributed to Foata and Riordan (1974). The survey uses this to state |PF_n| = (n+1)^{n-1}.
standard math Frobenius characteristic map is an isometry between the representation ring of S_n and symmetric functions.
Used in Section 2 to derive character formulas; no proof given.
domain assumption Theorems of Lackner and Panholzer (2016) on exact and asymptotic counts of tree and mapping parking functions.
Section 3 is a summary of these theorems; the survey takes them as established without proof.
domain assumption The scaling limit theorems of Contat and Curien (2025) (Corollary 3 and Theorem 4) are correct as quoted.
Section 4 relies on these for the claimed universality and Brownian growth-fragmentation limit.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Short survey of results and open problems for parking problems on random trees." pith.science (2026). https://pith.science/paper/6IC5BNX5

@misc{pith2026250515826,
  author       = {Pith},
  title        = {Pith review of: Short survey of results and open problems for parking problems on random trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6IC5BNX5}},
  note         = {Machine review of arXiv:2505.15826}
}

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 \approx \frac{n}{2}$. This relates to the renowned result by David Aldous of convergence results on Erd\H{o}s-Renyi random graphs of order $n^{\frac{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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 22 canonical work pages

[1]

Aldous, D. 1997. Brownian excursions, critical random gr aphs and the multiplicative coalescent. Ann. Probab. 25(2): 812-854 (A pril 1997). DOI: 10.1214/aop/1024404421

arXiv 1997
[2]

Aldous, D., Contat, A., Curien, N., Hénard, O. 2023. Parki ng on the inﬁnite binary tree. Probab. Theory Relat. Fields 187:481- 504, DOI: 10.1007/s00440-023-01189-6

work page doi:10.1007/s00440-023-01189-6 2023
[3]

Armstrong, D., Reiner, V., Rhoades, B. 2015. Parking spac es. Adv. Math., 269:647706

work page 2015
[4]

Berget, A., Rhoades, B. 2014. Extending the parking space . J. Combin. Theory Ser. A, 123:43-56

work page 2014
[5]

Self-similar ma rkov trees and scaling limits

Bertoin, J., Curien, N., Riera, A., 2024. Self-similar ma rkov trees and scaling limits. arXiv preprint arXiv:2407.07888

arXiv 2024
[6]

Bhamidi, S., van der Hofstad, R., Sen, S. 2018. The multipl icative co- alescent, inhomogeneous continuum random trees, and new un iversality classes for critical random graphs. Probability Theory and Related Fields, 170:387-474

work page 2018
[7]

Broutin, N., Duquesne, T., Wang, M. 2018. Limits of multip lica- tive inhomogeneous random graphs and L évy trees, arXiv preprint arXiv:1804.05871

work page Pith review arXiv 2018
[8]

Chen, L., Contat, A. 2024. Parking on supercritical geome tric Bienaymé- Galton-Watson trees. arXiv preprint arXiv:2402.05612

work page Pith review arXiv 2024

Show all 27 references

[9]

Conchon-Kerjan, G., Goldschmidt, C. 2023. The stable gra ph: the metric space scaling limit of a critical random graph with iid power -law degrees. Annals of Probability, 51(1):1-69. DOI: 10.1214/22-AOP15 87

2023 doi
[10]

Contat, A. 2022. Sharpness of the phase transition for pa rking on random trees. Random Structures and Algorithms, Volume 61, Issue 1 , August 2022:84-100

2022
[11]

Contat, A. 2023. Parking on trees with a (random) given de gree sequence and the Frozen conﬁguration model. arXiv preprint arXiv:23 12.04472

2023
[12]

Contat, A., Curien, N. 2023. Parking on Cayley trees and F rozen Erdős-Renyi. Annals of Probability, 51(6):1993-2055. DOI : 10.1214/23- AOP1632

2023 doi
[13]

Contat, A., Curien, N. 2025. Universality for catalytic equations and fully parked trees. arXiv preprint arXiv:2503.17348v1

2025 arXiv
[14]

Contat, A., Laulin, L. 2025. Parking on the random recurs ive tree. arXiv preprint arXiv:2501.03195. 16

2025 arXiv
[15]

Cori, R., Le Borgne, Y. 2003. The sand-pile model and Tutt e polynomials. Adv. in Appl. Math., 30(1-2):4452

2003
[16]

Foata, D., Riordan, J. 1974. Mappings of acyclic and park ing functions. Aequationes Math., 10:10-22

1974
[17]

Goldschmidt, C., Przykucki, M. 2019. Parking on a random tree. Combi- natorics, Probability and Computing, 28(1):23-45

2019
[18]

Haiman, M.D. 1994. Conjectures on the quotient ring by di agonal invari- ants. J. Algebraic Combin., 3(1):1776

1994
[19]

Hutchcroft, T. 2025. Critical cluster volumes in hierar chical percolation. Proc.Lond.Math.Soc. 130 (2025) 1, e70023

2025
[20]

Konheim, A.G., Weiss, B. 1966. An occupancy discipline a nd applications. SIAM J. Applied Math. 14:1266-1274

1966
[21]

Konvalinka, M., Tewari, V. 2021. Some natural extension s of the parking space. Journal of Combinatorial Theory, Series A, Volume 18 0, 2021, 105394, ISSN 0097-3165, DOI: 10.1016/j.jcta.2020.105394

2021
[22]

Kung, J.P.S., Yan, C. 2003. Gončarov polynomials and par king functions. Journal of Combinatorial Theory Ser. A, 102:16-37

2003
[23]

Lackner, M.-L., Panholzer, A. 2016. Parking functions f or mappings. Jour- nal of Combinatorial Theory, Series A, 142:1-28

2016
[24]

Macdonald, I.G. 1995. Symmetric functions and Hall poly nomials. Ox- ford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, second edition, 1995

1995
[25]

Pak, I.M., Postnikov, A.E. 1994. Resolvents for Sn-modu les that corre- spond to skew hooks, and combinatorial applications. Funkt sional. Anal. i Prilozhen., 28(2):7275

1994
[26]

Peterson, W.W. 1957. Addressing for random access stora ge. IBM J. Res. Develop., 1:130-146

1957
[27]

Stanley, R.P., Pitman, J. 2002. A polytope related to emp irical distri- butions, plane trees, parking functions, and the associahe dron. Discrete Comput. Geom., 27(4):603634. 17

2002

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Aldous, D. 1997. Brownian excursions, critical random gr aphs and the multiplicative coalescent. Ann. Probab. 25(2): 812-854 (A pril 1997). DOI: 10.1214/aop/1024404421

arXiv 1997

[2] [2]

Aldous, D., Contat, A., Curien, N., Hénard, O. 2023. Parki ng on the inﬁnite binary tree. Probab. Theory Relat. Fields 187:481- 504, DOI: 10.1007/s00440-023-01189-6

work page doi:10.1007/s00440-023-01189-6 2023

[3] [3]

Armstrong, D., Reiner, V., Rhoades, B. 2015. Parking spac es. Adv. Math., 269:647706

work page 2015

[4] [4]

Berget, A., Rhoades, B. 2014. Extending the parking space . J. Combin. Theory Ser. A, 123:43-56

work page 2014

[5] [5]

Self-similar ma rkov trees and scaling limits

Bertoin, J., Curien, N., Riera, A., 2024. Self-similar ma rkov trees and scaling limits. arXiv preprint arXiv:2407.07888

arXiv 2024

[6] [6]

Bhamidi, S., van der Hofstad, R., Sen, S. 2018. The multipl icative co- alescent, inhomogeneous continuum random trees, and new un iversality classes for critical random graphs. Probability Theory and Related Fields, 170:387-474

work page 2018

[7] [7]

Broutin, N., Duquesne, T., Wang, M. 2018. Limits of multip lica- tive inhomogeneous random graphs and L évy trees, arXiv preprint arXiv:1804.05871

work page Pith review arXiv 2018

[8] [8]

Chen, L., Contat, A. 2024. Parking on supercritical geome tric Bienaymé- Galton-Watson trees. arXiv preprint arXiv:2402.05612

work page Pith review arXiv 2024