Does freezing impede the growth of random recursive trees?
Pith reviewed 2026-05-22 02:16 UTC · model grok-4.3
The pith
Freezing cannot substantially decrease the height of random recursive trees.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In the uniform attachment with freezing model, vertices may freeze so that no new vertex can attach to them. Removing an attachment step can increase expected height, whereas freezing cannot substantially decrease the height of the trees relative to the classical unfrozen model. The proofs rely on coupling arguments that compare the two processes.
What carries the argument
Coupling arguments that maintain stochastic orderings between the heights of frozen and non-frozen attachment processes.
If this is right
- Removing attachment steps tends to increase expected tree height.
- Freezing preserves the asymptotic height distribution of the trees.
- The height of the frozen trees remains comparable to the classical case for large numbers of vertices.
- Coupling techniques suffice to transfer height results across the two models.
Where Pith is reading between the lines
- If the ordering is preserved, then known height asymptotics for ordinary random recursive trees carry over directly to the frozen version.
- The result suggests that deactivation constraints in network models do not require separate height analysis.
- One could test whether the same coupling works for preferential attachment or other attachment rules with freezing.
- Finite-n simulations could quantify how quickly any height gap between frozen and unfrozen trees closes.
Load-bearing premise
The coupling arguments preserve the necessary stochastic orderings on tree heights.
What would settle it
Large-scale simulation of both the frozen and unfrozen processes that finds the frozen trees to be substantially shorter would refute the claim.
read the original abstract
Uniform attachment with freezing is an extension of the classical model of random recursive trees, in which trees are recursively built by attaching new vertices to old ones. In the model of uniform attachment with freezing, vertices are allowed to freeze, in the sense that new vertices cannot be attached to already frozen ones. We study the impact of removing attachment and/or freezing steps on the height of the trees. We show in particular that removing an attachment step can increase the expected height, and that freezing cannot substantially decrease the height of random recursive trees. Our methods are based on coupling arguments.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper extends the classical uniform attachment model of random recursive trees by allowing vertices to freeze, after which no further attachments are possible to them. It examines the effect on tree height of removing attachment steps and of introducing freezing, proving in particular that deleting an attachment step can increase expected height and that freezing cannot substantially decrease height. All comparisons are obtained via coupling arguments between the modified and unmodified processes.
Significance. If the couplings are valid, the results establish a form of robustness for the height of random recursive trees under freezing perturbations. The coupling approach supplies direct stochastic comparisons without parameter fitting or simulation, which strengthens the quantitative claims about height differences.
major comments (1)
- [Proof of the main height comparison theorem] The coupling argument used to compare the frozen and non-frozen processes (detailed in the proof of the main height theorem) preserves the marginal law of the number of active vertices but does not explicitly verify stochastic ordering of the height random variables. Because height is a global supremum over path lengths, the construction must additionally control how a freeze event reroutes subsequent attachments; without an inductive step or explicit domination on the depth process after each freeze, the claimed bound on the height difference may fail even if local properties remain ordered.
minor comments (2)
- [Model and notation section] The definition of the height process H_n should be stated formally before the coupling is introduced, including whether it is measured from the root or includes the frozen vertices.
- [Statement of results] A short remark on the rate at which the height difference tends to zero (or remains bounded) would help the reader interpret the phrase 'cannot substantially decrease'.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for identifying a point where the coupling argument for the main height comparison could be presented with greater explicitness. We address the concern below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: The coupling argument used to compare the frozen and non-frozen processes (detailed in the proof of the main height theorem) preserves the marginal law of the number of active vertices but does not explicitly verify stochastic ordering of the height random variables. Because height is a global supremum over path lengths, the construction must additionally control how a freeze event reroutes subsequent attachments; without an inductive step or explicit domination on the depth process after each freeze, the claimed bound on the height difference may fail even if local properties remain ordered.
Authors: We agree that the current write-up would benefit from an explicit inductive verification of the stochastic ordering on heights. In the revised manuscript we will insert a short inductive argument (on the number of vertices added) immediately after the coupling construction. The induction hypothesis maintains that, up to the current step, the depth of every vertex in the frozen tree is at least as large as the depth of its counterpart in the non-frozen tree (modulo the controlled error term arising from the number of frozen vertices). When a freeze occurs, the coupling reroutes all future attachments uniformly among the still-active vertices in both processes; because the set of active vertices in the frozen process is always a subset of those in the non-frozen process under the coupling, the uniform choice preserves the depth ordering for the newly attached vertex. The base case is immediate, and the inductive step directly controls the global supremum that defines height. This addition makes the domination on the depth process after each freeze fully rigorous while leaving the rest of the argument unchanged. revision: yes
Circularity Check
No circularity detected; results follow from explicit coupling constructions
full rationale
The paper establishes its claims—that removing attachment steps can increase expected height and that freezing cannot substantially decrease height—via direct coupling arguments between the frozen and non-frozen uniform attachment processes. These couplings are defined to compare the processes while preserving the relevant stochastic orderings on heights, without any fitted parameters, self-referential definitions, or load-bearing self-citations. No equation or step reduces a derived quantity to an input by construction; the height comparisons are obtained from the monotonicity properties of the couplings themselves. The derivation is therefore self-contained against external probabilistic benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard axioms of probability and stochastic ordering for coupling arguments
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.