Pith. sign in

REVIEW 3 major objections 4 minor 18 references

Parking on the Random Recursive Tree

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper proves that parking on a random recursive tree is supercritical at every positive car density, with the critical window for binary arrivals at $\alpha_n = (\log n)^{-2+o(1)}$.

desk verdict New result on parking on random recursive trees: critical density zero, critical window (log n)^{-1/β*}; the upper bound is clean, but the supercritical half needs a real LLN proof. read the letter →

arxiv 2501.03195 v1 pith:RZWBLGPR submitted 2025-01-06 math.PR math.CO

Alice Contat , Lucile Laulin This is my paper · ORCID
classification math.PRmath.CO MSC 60C0505C0560J80
keywords parkingprocessrandomrecursivetreephasetransitionoutgoingfluxBenjamini–SchrammlimitYulecriticalwindowtrees
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

On a random recursive tree, the parking process has no nontrivial phase transition: for any fixed positive arrival density $\alpha$, a positive fraction of cars eventually leaves the root, even though the tree sequence has a non-degenerate Benjamini–Schramm limit. The paper identifies the reason in the infinite spine: ancestors of a typical vertex have degrees growing along the spine, so infinitely many of them harbour parked cars. It then locates the window in which the flux first appears when the density is allowed to vanish with $n$. For binary arrivals the threshold is $\alpha_n = (\log n)^{-2+o(1)}$; for general bounded stochastically increasing families it is $(\log n)^{-1/\beta^*+o(1)}$. This is the first analysis of the parking process on trees that can have large-degree vertices.

What carries the argument

The argument runs through three constructions. (1) The Yule-tree coupling: the discrete recursive trees $(T_n)$ are realized from a continuous-time Yule tree $T_t$ cut at the times of births, so that $T_{\vartheta_n}$ has the law of $T_n$; this lets the paper work in continuous time and then transfer results back to the discrete sequence through the law of $|T_t|$. (2) The spine tree $T_\infty$: the Benjamini–Schramm limit is described as one infinite spine decorated with independent Yule trees along a Poisson process, and the ancestors $(S_k)$ have degrees growing like $k$; this spine is what makes the phase transition trivial. (3) Fully parked trees: for the upper bound, the flux is bounded by summing over all fully parked configurations embedded in the root's parked component, giving a first-moment estimate $\mathbb{E}[\psi(T_t, \mu_\alpha)] \to 0$ when $\alpha^{\beta^*} t$ stays small. The lower bound instead constructs a generation-restricted Galton–Watson tree on vertices that receive $k^*$ cars at multiples of the height $k^*$, and shows this tree reaches a height where its occupied children force a large flux.

What would settle it

Run the standard coupling where vertex $n$ attaches to a uniform earlier vertex and each vertex receives an independent car count from a fixed law of mean $\alpha=0.1$, and plot $\phi(T_n,\mu)/n$ for $n$ up to $10^6$: Theorem 1 predicts a positive limit, so a steady decay toward $0$ would refute it. As a more targeted check, record $\psi(T_n)$ along the same coupling; any single decrease in this sequence would disprove the monotonicity assertion on which the discrete transfer depends.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: the critical parameter for parking on the random recursive tree is $\alpha_c = 0$, meaning that for every stochastically increasing family of arrival laws with $\mu_\alpha(\{0,1\}) < 1$ and every fixed $\alpha > 0$, the flux per vertex $\phi(T_n, \mu_\alpha)/n$ converges in probability to a positive constant $C_\alpha$. The reason is not the root's large degree but the spine of the Benjamini–Schramm limit: the $k$-th ancestor $S_k$ of the distinguished vertex has degree of order $k$, and the probability that $S_k$ remains empty in the final configuration decays like $(1+\delta(\alpha))^{-k}$, so by Borel–Cantelli infinitely many ancestors are occupied and an infinite parked cluster exists. The paper's second claim, Theorem 3, quantifies the transition when $\alpha = \alpha_n \to 0$: the flux vanishes in probability when $\alpha_n \ll (\log n)^{-1/\beta^*}$ and diverges to $+\infty$ when $\alpha_n \gg (\log n)^{-1/\beta^*+\delta}$, where $\beta^* = \inf\{\beta_k : C_k > 0\}$ is read off from the small-$\alpha$ asymptotics $\mu_\alpha(\{k\}) \sim C_k \alpha^{\beta_k k}$; for binary arrivals this gives the critical window $(\log n)^{-2+o(1)}$.

Load-bearing premise

The proof that bounds on the continuous-time version of the tree transfer to the discrete one-vertex-at-a-time version assumes, without proof, that the number of cars passing the root never decreases as the tree grows; if this monotonicity ever failed, the transfer of both the upper and lower bounds would collapse.

Editorial extensions

If this is right

  • For every fixed $\alpha > 0$, the flux fraction $\phi(T_n, \mu_\alpha)/n$ converges in probability to a positive constant, so the random recursive tree is always supercritical.
  • When $\alpha_n \ll (\log n)^{-1/\beta^*}$, the outgoing flux converges to $0$ in probability; when $\alpha_n \gg (\log n)^{-1/\beta^*+\delta}$, it diverges to $+\infty$.
  • For binary car arrivals the critical window is $\alpha_n = (\log n)^{-2+o(1)}$.
  • The first time the flux reaches any fixed level $C$ satisfies $\log \log \theta(\mu_\alpha, C)/|\log \alpha| \to \beta^*$, so the waiting time grows like $\exp(\alpha^{-\beta^*+o(1)})$.
  • The flux time-corollary makes the divergence sharp: once the density parametre is above the window, the flux is not merely positive but unbounded in probability.

Reading between the lines

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

  • The spine mechanism suggests a broader principle: any finite-tree sequence whose Benjamini–Schramm limit has a one-ended spine with side subtrees accumulating along it may also have $\alpha_c = 0$, and the critical window will be governed by the growth of degrees along the spine.
  • The gap between the upper and lower regimes, $\alpha_n \ll (\log n)^{-1/\beta^*}$ versus $\alpha_n \gg (\log n)^{-1/\beta^*+\delta}$, leaves the exact constant and the sharp order of the flux inside the window open; one could test numerically whether the flux scales like a power of $\log n$ at $\alpha_n = c (\log n)^{-1/\beta^*}$.
  • A direct way to check the paper's transfer step is to simulate the natural coupling of $T_n$ and record $\psi(T_n)$; monotonicity of this sequence is asserted without proof, and any decrease would isolate a gap in the proof rather than in the result.
  • The boundedness of arrivals is used only in the upper bound, so simulating Poisson or geometric arrivals at $\alpha_n = c (\log n)^{-1/\beta^*}$ would probe how far the conjectured threshold extends beyond the bounded case.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies the parking process on uniform random recursive trees with i.i.d. car arrivals. It proves that the critical density parameter for the parking phase transition is 0 (Theorem 1), via the Benjamini–Schramm limit and a criterion from the first author's earlier work [8]. It then identifies the critical window for a positive outgoing flux: for a general class of bounded, stochastically increasing arrival families satisfying the small-α asymptotics (2), the flux converges to 0 in probability when α_n ≪ (log n)^{-1/β*}, and to +∞ when α_n ≫ (log n)^{-1/β* + δ} for any δ > 0 (Theorem 3), where β* is determined by the arrival law. In the binary case this gives the window (log n)^{-2+o(1)} (Theorem 2). The upper bound is proved by a first-moment sum over fully parked trees; the lower bound uses a planted multi-level branching structure inside the parked cluster of the root, with continuous-time Yule estimates transferred to discrete recursive trees via an increasing coupling.

Significance. If the technical gaps identified below are fixed, this is a substantial contribution. It is the first parking-process result on trees with unbounded degrees, and it gives a sharp, parameter-free characterization of the critical window through the exponent β*. The upper-bound method via fully parked trees and the spine construction for α_c = 0 are elegant and likely to be reusable. The main weakness is the lower bound: the concentration estimates for the planted branching structure are asserted rather than proved, and one displayed inequality chain in Section 4 is misordered. The central claims are plausible and appear correct, but the manuscript in its current form does not yet provide rigorous proofs of all load-bearing steps.

major comments (3)
  1. [Section 4, definition of V^{(1)} and V^{(j)}_{cars}] The lower bound of Theorem 3 relies on the assertions, introduced by 'By successive applications of the law of large numbers', that P(|V^{(1)}(T_t)| ≥ (1/2)(t/(2k*))^{k*}) → 1 and, after car thinning, P(|V^{(j)}_{cars}(T_t, μ_{α_t})| ≥ m t^{jδ}) ≥ 1 − 2ε. These are concentration statements for a triangular array of embedded branching processes whose offspring distributions depend on t, and the induction passes from generation ℓ to ℓ+1 with only about t^{ℓδ} parents. The paper supplies no variance or second-moment estimates, and the phrase 'successive applications of the law of large numbers' does not by itself justify the high-probability lower bounds at polynomial scale. This is a load-bearing gap: if at any step the relative fluctuations do not vanish, the planted structure may fail to produce a positive flux. Please provide a rigorous induction (e.g., Chebyshev's inequality with explicit bounds on the conditional mean and variance given the previous generation) or replace the construction with one that has a proof.
  2. [Section 4, Equation (10)] In the paragraph containing Equation (10), the displayed chain of inequalities reads P(ψ(T_t, α_t) ≥ C) ≥ P(ψ ≥ (mc/2^{j+1}) t) ≥ P(ψ ≥ (mc/2^{j+1}) t^{δ j+1} α_t^γ) ≥ 1 − 4ε. The middle step is not valid as written: by the choice of j and (9), t^{δ j} α_t^γ > 1, so for large t the threshold (mc/2^{j+1}) t^{δ(j+1)} α_t^γ exceeds (mc/2^{j+1}) t, making the second event the smaller one. The desired conclusion (P(ψ ≥ C) → 1 for every fixed C) follows directly from the previously established bound with B_t := (mc/2^{j+1}) t^{δ(j+1)} α_t^γ, since B_t → ∞; the intermediate comparison with t should be removed or corrected.
  3. [Section 3.2, computation of P(C(ρ,T_t) ⊇ t)] In the paragraph starting 'Given the family of (t^i_v ...)', the product ∏_{v∈t} ∏_{i=1}^{c_v} ∫_0^t dt^i_v is written with c_v denoting the number of cars arriving at v, but the surrounding text says the integrals are over the creation times of the i-th children of v. The total number of such creation times is n−1 (one per edge of t), not m = ∑_v c_v, and the subsequent factor t^{n-1} confirms that the intended upper index is the outdegree of v. This notational inconsistency obscures a load-bearing step: the exponent n−1 is essential for the condition t α^{β*} ≤ c in Proposition 2 (if the exponent were m, the required condition would be of order t^2 α^{β*} ≤ c). Please rewrite this calculation with a clear distinction between car counts and child counts (e.g., use d_v for the number of children).
minor comments (4)
  1. [Section 5, discrete transfer] The monotonicity assertion 'for every fixed α, the sequence (ψ(T_n, μ_α)) is non-decreasing' is used in both directions of the discrete transfer (e.g., in the inequalities with E[ψ(T_t)1_{|T_t|≥n}] and with P(φ(T_{log n})≥K, |T_{log n}|≤n)) but is not proved. Please add a one-sentence justification (adding a leaf cannot decrease the number of cars visiting the root, since existing car paths are unchanged and new cars can only add visits).
  2. [Section 2.3, Borel–Cantelli bound] The bound P(ψ_{S_k}(T∞,μ)=0) ≤ (1/(1+δ(α)))^k should be (1/(1+δ(α)))^{k+1} if the integration runs over k+1 variables τ_0,...,τ_k; the conclusion is unaffected.
  3. [Section 4, recursive definition of V^{(ℓ+1)}] The time cutoff 't − t/2^ℓ' with ℓ=1 gives t/2, the same as in the definition of V^{(1)}; please check the intended time windows (should it be t − t/2^{ℓ+1} or similar?) to avoid ambiguity.
  4. [Section 1 and throughout] There are minor typos: 'supercritial' should be 'supercritical', and 'Bienaym´e' is written with a non-standard accent; the reference list also shows 'Bienaym ´e' in [6].

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the phase-transition black box [8] is an independent general theorem, and the RRT-specific bounds are self-contained first-moment and branching estimates.

full rationale

The paper's central claims are derived from self-contained arguments rather than from their own conclusions. The only self-citation is [8, Theorem 4.1], which the paper uses as a general existence and convergence theorem for the phase transition in parking on tree sequences converging in the Benjamini--Schramm quenched sense to a single-spine tree. Its assumptions do not include the target results αc = 0 or the log-window, so it is independent support under the stated criteria rather than a circular premise. Theorem 1 uses this theorem only after the paper independently proves, via a Borel--Cantelli argument on the ancestors S_k, that for every α > 0 there is an infinite parked cluster in T∞. The critical-window Theorem 3 is also derived separately: the upper bound is a first-moment calculation over fully parked trees in Section 3.2, and the lower bound is an explicit embedded branching construction in Section 4. No fitted parameter is relabeled as a prediction, and no equation is defined in terms of the quantity it is meant to determine. The unproved monotonicity assertion in Section 5 and the informal 'successive applications of the law of large numbers' in Section 4 are correctness gaps or missing rigorous estimates, but they are not circular: they do not assume the theorem's conclusion. The paper is therefore not circular in the sense of reducing its predictions to its inputs.

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

No free parameters are fitted to data; the constants c, C, γ, δ, j in the proofs are chosen for the arguments, not estimated from observations. The exponents β_k and C_k are part of the stated hypotheses on the arrival distributions. No new physical or mathematical entities are postulated; the 'fully parked tree' and the sets V_cars are analytical constructions.

assumptions (5)
  • domain assumption Benjamini-Schramm quenched convergence of random recursive trees to the spine tree T∞ (from [16])
    Used in Section 2.2 to apply the phase-transition characterization from [8].
  • domain assumption Phase-transition characterization [8, Theorem 4.1]: for tree sequences with a single infinite spine, flux/n converges to a constant that is positive iff an infinite parked cluster exists
    Black-box theorem from the first author's thesis, used in Section 2.3 to equate αc with the percolation threshold for parked clusters.
  • domain assumption Monotonicity of ψ(T_n, μ) in n under the increasing coupling
    Asserted without proof in Section 5; used to transfer continuous-time bounds to discrete T_n.
  • domain assumption Concentration of the fast-descendant branching process at fixed depth (successive LLN)
    Used in Section 4 to lower bound |V_cars^{(j)}| and the number of children with ≥2 cars; standard for Poisson branching processes but not proved in detail.
  • domain assumption Small-α asymptotics (2): μ_α({k}) ∼ C_k α^{β_k k} and existence of γ in (8)
    These are hypotheses on the arrival family, stated in Section 1 and recalled in Section 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parking on the Random Recursive Tree." pith.science (2026). https://pith.science/paper/RZWBLGPR

@misc{pith2026250103195,
  author       = {Pith},
  title        = {Pith review of: Parking on the Random Recursive Tree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RZWBLGPR}},
  note         = {Machine review of 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.

Figures

Figures reproduced from arXiv: 2501.03195 by the authors.

Figure 1
Figure 1. On the left, an example of a Yule tree Yt cut at time t. On the right, the recursive Tt tree constructed from this Yule tree. Each vertex is drawn with the same color as its corresponding branch in the Yule tree. 2.2 Description of the local limit of the RRT We now describe the topology that we need in order to apply [8, Theorem 4.1]. Benjamini–Schramm quenched topology. Let (Tn : n ⩾ 1) be a sequence of (possibly r… view at source ↗
Figure 2
Figure 2. On the left side of the figure, we see the two Yule processes Y (0) (in pink) and Y (1) (in orange) that grow for respective times τ0 and τ0 +τ1 in total. On the right side, the tree Ye(1) obtain by gluing Y (1) on the right-hand side of the left most branch of Ye(0) = Y (0) . The two thicker branches are the one that correspond to the vertex S0 (in pink) and S1 (in orange). S3 S2 S1 S0 S0 S1 S2 S3 T (0) T (1) T T (… view at source ↗
Figure 3
Figure 3. On the left side, the tree Ye(3) obtained by gluing Yule tree as described above. The branch corresponding to the ancestors S0,S1,S2 and S3 are drawn thicker. On the right, the recursive tree T (3) constructed from Ye(3) . We also highlight with colors the increasing (for the inclusion) sequence of recursive trees (T (k) : 0 ⩽ k ⩽ 3). This implies (4) by decomposing the functions f and g for all possible values of t… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Example of a fully parked tree with 18 vertices and 20 cars arriving on it: on the left, the car arriving configuration and on the right, the final configuration where all spots are occupied and 2 cars are going out from the tree and contributing to the flux. 3.2 Proof…
Figure 5
Figure 5. Figure 5: On the left, example of a spliting in the Yule tree that creates a vertex in V (1) (Tt ,µαt ). On the right, example of the construction of the sets (V (ℓ) cars(Tt ,µαt ) : ℓ ⩾ 1) when k ∗ = 3. In our example, there are 6 children of V (j) cars(Tt ,µαt on which at leas…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

  1. [8]

    , Parking on random trees, PhD thesis, Universit´e Paris-Saclay, 2023

    work page 2023

  2. [1]

    A LDOUS , Asymptotic fringe distributions for general families of random trees , The Annals of Applied Probability, (1991), pp

    D. A LDOUS , Asymptotic fringe distributions for general families of random trees , The Annals of Applied Probability, (1991), pp. 228–266

    work page 1991

  3. [2]

    A LDOUS , A

    D. A LDOUS , A. C ONTAT, N. C URIEN , AND O. H ´ENARD , Parking on the infinite binary tree, Probability Theory and Related Fields, (2023), pp. 1–24

    work page 2023

  4. [3]

    K. B. A THREYA AND P. E. NEY, Branching processes, vol. 196 of Die Grundlehren der mathematischen Wissenschaften, Springer-Verlag, 1972

    work page 1972

  5. [4]

    Enumeration of fully parked trees

    L. C HEN, Enumeration of fully parked trees, arXiv preprint arXiv:2103.15770, (2021)

    work page Pith review arXiv 2021

  6. [5]

    C HEN AND A

    L. C HEN AND A. C ONTAT, Parking on supercritical geometric Bienaym ´e–Galton– Watson trees, arXiv preprint, (2024)

    work page 2024

  7. [6]

    C HEN AND C

    Q. C HEN AND C. G OLDSCHMIDT , Parking on a random rooted plane tree, Bernoulli, 27 (2021), pp. 93–106. 14

    work page 2021

  8. [7]

    C ONTAT, Sharpness of the phase transition for parking on random trees , Random Structures & Algorithms, 61 (2022), pp

    A. C ONTAT, Sharpness of the phase transition for parking on random trees , Random Structures & Algorithms, 61 (2022), pp. 84–100

    work page 2022

Show all 18 references
  1. [9]

    , Parking on trees with a (random) given degree sequence and the frozen configu- ration model, arXiv preprint arXiv:2312.04472, (2023)

    2023 arXiv

  2. [10]

    C ONTAT AND N

    A. C ONTAT AND N. C URIEN , Parking on Cayley trees and frozen Erd ˝os–R´enyi, The Annals of Probability, 51 (2023), pp. 1993–2055

    2023

  3. [11]

    C URIEN , A random walk among random graphs , arXiv preprint arXiv:2412.19752, (2024)

    N. C URIEN , A random walk among random graphs , arXiv preprint arXiv:2412.19752, (2024)

    2024 arXiv

  4. [12]

    C URIEN AND O

    N. C URIEN AND O. H ´ENARD , The phase transition for parking on Galton–Watson trees, Discrete Analysis, (2022)

    2022

  5. [13]

    D EVROYE AND J

    L. D EVROYE AND J. L U, The strong convergence of maximal degrees in uniform ran- dom recursive trees and dags, Random Structures & Algorithms, 7 (1995), pp. 1–14

    1995

  6. [14]

    D RMOTA, Random trees: an interplay between combinatorics and probability , Springer Science & Business Media, 2009

    M. D RMOTA, Random trees: an interplay between combinatorics and probability , Springer Science & Business Media, 2009

    2009

  7. [15]

    G OLDSCHMIDT AND M

    C. G OLDSCHMIDT AND M. P RZYKUCKI , Parking on a random tree , Combinatorics, Probability and Computing, 28 (2019), pp. 23–45

    2019

  8. [16]

    H OLMGREN AND S

    C. H OLMGREN AND S. J ANSON , Fringe trees, crump–mode–jagers branching pro- cesses and m-ary search trees, (2017)

    2017

  9. [17]

    A. G. K ONHEIM AND B. W EISS , An occupancy discipline and applications , SIAM Journal on Applied Mathematics, 14 (1966), pp. 1266–1274

    1966

  10. [18]

    L ACKNER AND A

    M.-L. L ACKNER AND A. P ANHOLZER , Parking functions for mappings , Journal of Combinatorial Theory, Series A, 142 (2016), pp. 1 – 28. 15

    2016

Pith tools

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