REVIEW 2 major objections 3 minor 31 references
Uniform temporal trees
T0 review · 2 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read A new class of random temporal trees has a size that fluctuates on the exponential scale and a height that settles at e times np.
desk verdict A nicely motivated new tree model with an appealing exponential size law, but the proof of the central comparison lemma has a real gap that needs a rewrite. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument is carried by two linked devices. First, the uniform spacings coupling replaces the independent edge labels with spacings: a vertex with label $\ell$ has children whose labels are $\ell$ minus cumulative sums of independent uniform spacings, which are distributed as exponential variables divided by their total sum. This makes the label of a vertex equal to $p$ minus a sum of spacing terms indexed by the vertex's rank among its siblings. Second, the paper maps the vertices of small index in $T_{n,p}$ into an infinite complete binary branching random walk whose edge steps are independent exponential random variables divided by $n$, using the event that fixed-index vertices have enough children to support the injection. The size of $T_{n,p}$ is then bounded above and below by sums of independent copies of smaller temporal trees with modified thresholds $p_i$, controlled by a second-moment inequality and by distributional properties of the branching random walk. The height proof instead trims the tree to its $K$ largest-label children and uses large-deviation estimates for gamma sums to show that a supercritical Galton-Watson process survives, forcing vertices at depth roughly $\gamma n$ for every $\gamma < e$.
What would settle it
Simulate $T_{n,p}$ for fixed $p$ (for example $p=1/2$) and increasing $n$, and compare the empirical survival function of $|T_{n,p}|/e^{np}$ with $e^{-x}$. If the proportion of runs with normalized size above 1 does not tend to $e^{-1} \approx 0.368$, the exponential limit law of Theorem 2.1 is false. A complementary check is to compute the second-moment ratio $E|T_{n,p}|^2/(E|T_{n,p}|)^2$ directly for finite $n$ and see whether it remains bounded by 5 as required by Lemma 4.1.
Extended reading notes
Core claim
The paper's central claim is that $|T_{n,p}|$, the number of vertices in the $p$-percolated uniform temporal tree, has expectation $e^{np}$ and satisfies $|T_{n,p}|/e^{np}$ converging in distribution to an Exponential(1) random variable. It also proves a joint version of this limit for the subtrees attached to the root's highest-label children: after division by $e^{np}$, their sizes converge to $(E_1 U_1, E_2 U_1 U_2, \ldots, E_m U_1 \cdots U_m)$ with independent exponentials $E_i$ and independent uniform random variables $U_i$. The height $H_{n,p}$ satisfies $H_{n,p}/(np) \to e$ and $H_{n,p}/\log|T_{n,p}| \to e$ in probability, and a uniformly chosen vertex has depth $D_{n,p}$ with $D_{n,p}/(np) \to 1$ and $D_{n,p}/\log|T_{n,p}| \to 1$. Finally, the expected number of vertices with outdegree $k$ satisfies $E L_{n,k}/e^{np} \to 2^{-(k+1)}$. Read together, the tree has random volume on the exponential scale but a deterministic shape profile.
Load-bearing premise
The load-bearing step is the assumption that every vertex among the first few index levels of the temporal tree has enough surviving children to be matched injectively into the binary branching-random-walk tree; the paper proves this event has probability tending to one but does not quantify how fast, and the two-sided bounds on the total size inherit that unquantified high-probability event.
Editorial extensions
If this is right
- The size of a uniform temporal tree does not concentrate: even at large $n$, the total number of surviving vertices fluctuates by a factor comparable to its mean, with an exponential limiting distribution.
- The height is deterministic at scale $np$: with high probability the deepest vertex sits at depth about $e \cdot np$, so the tree is roughly $e$ times as deep as a typical vertex's depth.
- Because $H/\log|T|$ tends to $e$, the height is about $e$ times the natural logarithm of the number of vertices, the same logarithmic relation seen in uniform random recursive trees.
- A uniformly random vertex lies near depth $np$, so almost all of the tree's mass sits in a band around $np$ whose width is small relative to $n$.
- The expected degree distribution stabilizes in a geometric form: about half of all vertices are leaves, one quarter have exactly one child, and so on.
Reading between the lines
- If uniform temporal trees are the local tree limit of sparse random simple temporal graphs, the height law would imply that temporal paths in such networks reach depth about $e \log$ of the local tree size; this is an inference beyond the paper, which only proposes the tree as a motivated model.
- The same spacings-coupling machinery should extend to labels with other continuous distributions; the constant $e$ in the height law would likely change to a functional of the label distribution, giving a testable family of temporal tree models.
- The joint limit for root-subtree masses suggests a recursive stick-breaking representation of the exponential limit; one could test whether conditioning $T_{n,p}$ on its total size produces a mass-splitting structure close to that of uniform random recursive trees despite the different root-degree behaviour.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines uniform temporal trees T_{n,p} by assigning independent uniform labels to the edges of an infinite rooted n-ary tree and retaining vertices for which labels along the root-to-vertex path are decreasing and below p. It proves four main results: E|T_{n,p}|=e^{np} and the distributional limit |T_{n,p}|/e^{np}→Exponential(1); a joint limit for the masses of the largest root subtrees; the height law H_{n,p}/(np)→e in probability; the typical depth law D_{n,p}/(np)→1 in probability; and an asymptotic expected degree distribution with weights 2^{-(k+1)}. The proofs use a uniform-spacings coupling, a branching-random-walk decomposition, concentration bounds, and Cramér large deviations. The results are plausible and well motivated, but the proof of Theorem 2.1 depends on a coupling lemma whose current construction is not valid. The paper is a candidate for acceptance after a substantive revision of that proof.
Significance. If the proofs are repaired, the paper gives a clean set of first-order asymptotics for a natural random-tree model and demonstrates an interesting contrast: the total number of vertices is random on the exponential scale, while the height is deterministic at scale np. The branching-random-walk method and the uniform-spacings coupling are well suited to the problem, and the paper states explicit, falsifiable limits with no fitted parameters. The height, depth, and degree results are likely correct and potentially useful for the analysis of random temporal graphs. However, the size theorem, which is one of the paper's central claims, is currently not rigorously established because its key approximation lemma is flawed.
major comments (2)
- [Section 8, proof of Lemma 4.3] The construction of Tnew is not well-defined and does not have the claimed law. The text first assigns labels ℓ*_{u_i} to n new vertices u_i attached to a root and then says: 'we attach Tn(v_{r(v)+i}) to the vertices u_i ... for 1 ≤ i ≤ n − r(v)'. Under the paper's notation, Tn(v_{r(v)+i}) is the actual subtree of the original complete tree rooted at the sibling v_{r(v)+i}; these are exactly the subtrees that determine F(v). A tree with the law T_{n,ℓ^-_v(ϵ)} would require, below a child with label ℓ*_{u_i}, an independent copy of T_{n,ℓ*_{u_i}} generated from fresh spacings, not the original subtree whose root label is ℓ_{v_{r(v)+i}}. Consequently, Tnew is not distributed as claimed and is not conditionally independent of Tn(v). Since Lemma 4.2 uses Lemma 4.3 for both directions of the two-sided comparison, Theorem 2.1 is not established by the present proof.
- [Section 8, proof of Lemma 4.3] The sentence 'For the vertices ui with n < i≤ n + r(v) we make ui the root of independently sampled trees distributed like Tn' refers to vertices u_i that have not been defined: only u_1,...,u_n were introduced. The construction must specify which of the n attachment vertices receive independent copies and which receive the original subtrees; the current indexing makes the definition of Tnew ambiguous. This is not merely a typographical issue, as the proof later compares |Tnew(u_i)| for i=1,...,k and needs a precise prescription of those subtrees.
minor comments (3)
- [Section 5, proof of Theorem 2.2] The sentence 'D is smaller than the sum of 2KM random variables distributed as S*_K' is incorrect as written. There are K^M vertices at depth M, each with M increments, so the sum should involve K^M M random variables, or a fixed constant depending on K and M. Since K and M are fixed and E[S*_K]=O(1/n), the asserted o_n(1) conclusion remains valid, so this appears to be a harmless typo.
- [Section 5, proof of Lemma 5.1] In the displayed inequality after defining I(x), the supremum is written as sup_{λ>0}(λx+log(−λ)); since log(−λ) is undefined for λ>0, this should read sup_{λ<0}(...) or, after the substitution μ=−λ, sup_{μ>0}(−μx+log μ).
- [Section 8, proof of Lemma 4.1] The displayed ratio f(k+1)/f(k) contains a redundant factor (ℓ−k+m)!/(ℓ−k+m)! in the numerator and denominator; the intended simplification to (ℓ−k+m)/(ℓ−k+2m) is correct, but the formula as printed is confusing.
Circularity Check
No significant circularity: the limit laws are derived from the model definition via standard external tools, with no fitted parameters or load-bearing self-citations.
full rationale
The paper introduces a new object (uniform temporal trees) and derives its properties from first principles. The expectation E|T_{n,p}| = e^{np} is computed directly by summing per-depth probabilities p^k/k!, and the second-moment bound in Lemma 4.1 is a direct calculation. Theorem 2.1's limit law is obtained by a branching-random-walk comparison whose step-size distribution is the standard exponential spacings representation of uniform order statistics (Devroye 1986), an external and parameter-free fact. The upper and lower bounds in Lemma 4.2 replace |F(v)| by independent copies of T_{n,ℓ_v^±(ϵ)}; this is a coupling approximation, not a fit of the target quantity. Even if the coupling in Lemma 4.3 were imperfect, that would be a correctness gap, not circularity: the claimed distribution does not presuppose the exponential limit. Theorem 2.2 uses the union bound and Cramér's large-deviation theorem; Theorem 2.3 uses Markov's inequality with Stirling bounds; Theorem 2.4 computes E L_{n,k} directly and lets n → ∞. The self-citations (Atamanchuk, Devroye, Lugosi 2024; Broutin, Kamčev, Lugosi 2023) are contextual or motivational and are not used to justify any of the paper's theorems. Technical citations (Cramér 1938/1944, Biggins 1976/1977, Durrett 2019, Klenke 2008, Addario-Berry-Reed 2009) are standard external results. No parameter is fitted to a subset of the data, no prediction is renamed as an input, and no load-bearing argument reduces to a self-citation chain. The derivation is self-contained against the stated model and external benchmarks, so the circularity score is 0.
Assumptions & free parameters
assumptions (6)
- domain assumption Edge labels are independent Uniform[0,1] random variables, and survival requires monotonically decreasing labels along each root-to-vertex path.
- standard math Sorted iid uniforms have spacings distributed as normalized exponentials, and the rotation lemma preserves uniformity.
- standard math Cramer's large deviation theorem applies to the mixture-of-gamma step distribution with the stated rate function.
- standard math Biggins-Hammersley-Kingman theorem gives linear order for extremes of the branching random walk, allowing epsilon(L) = L^{-2}.
- standard math The almost sure limit X of the branching random walk martingale is identified by its moments through the Stieltjes moment problem.
- domain assumption For every fixed finite index, the outdegree of a vertex tends to infinity, so the event E in Lemma 4.2 has probability tending to 1.
Cite this review
Pith. "Pith review of Uniform temporal trees." pith.science (2026). https://pith.science/paper/E5XL62L2
@misc{pith2026250113044,
author = {Pith},
title = {Pith review of: Uniform temporal trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/E5XL62L2}},
note = {Machine review of arXiv:2501.13044}
}
abstract
Motivated by the study of random temporal networks, we introduce a class of random trees that we coin \emph{uniform temporal trees}. A uniform temporal tree is obtained by assigning independent uniform $[0,1]$ labels to the edges of a rooted complete infinite $n$-ary tree and keeping only those vertices for which the path from the root to the vertex has decreasing edge labels. The $p$-percolated uniform temporal tree, denoted by $\mathcal{T}_{n,p}$, is obtained similarly, with the additional constraint that the edge labels on each path are all below $p$. We study several properties of these trees, including their size, height, the typical depth of a vertex, and degree distribution. In particular, we establish a limit law for the size of $\mathcal{T}_{n,p}$ which states that $\frac{|\mathcal{T}_{n,p}|}{e^{np}}$ converges in distribution to an $\exponential(1)$ random variable as $n \to \infty$. For the height $H_{n,p}$, we prove that $\frac{H_{n,p}}{np}$ converges to $e$ in probability. Uniform temporal trees show some remarkable similarities to uniform random recursive trees.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
Addario-Berry, L. and Eslava, L. (2018). High degrees in random recursive trees. Random Structures and Algorithms , 52(4):560--575
work page 2018
-
[2]
Addario-Berry, L. and Reed, B. (2009). Minima in branching random walks. The Annals of Probability , pages 1044--1079
work page 2009
-
[3]
Angel, O., Ferber, A., Sudakov, B., and Tassion, V. (2020). Long monotone trails in random edge-labellings of random graphs. Combinatorics, Probability and Computing , 29(1):22--30
work page 2020
-
[4]
Atamanchuk, C., Devroye, L., and Lugosi, G. (2024). On the size of temporal cliques in subcritical random temporal graphs. arXiv , 2404.04462
arXiv 2024
-
[5]
Becker, R., Casteigts, A., Crescenzi, P., Kodric, B., Renken, M., Raskin, M., and Zamaraev, V. (2022). Giant components in random temporal graphs. arXiv , 2205.14888
arXiv 2022
-
[6]
Biggins, J. (1976). The first and last-birth problems for a multitype age-dependent branching process. Advances in Applied Probability , 8:446--459
work page 1976
-
[7]
Biggins, J. (1977). Chernoff's theorem in the branching random walk. Journal of Applied Probability , 14:630--636
work page 1977
-
[8]
Broutin, N., Kam c ev, N., and Lugosi, G. (2023). Increasing paths in random temporal graphs. arXiv , 2306.11401
work page Pith review arXiv 2023
Show all 31 references
-
[9]
Casteigts, A., Raskin, M., Renken, M., and Zamaraev, V. (2024). Sharp thresholds in random simple temporal graphs. SIAM Journal on Computing , 53(2):346--388
2024
-
[10]
D., Steele, R
Coath, C. D., Steele, R. C., and Lunnon, W. F. (2013). Statistical bias in isotope ratios. Journal of Analytical Atomic Spectrometry , 28(1):52--58
2013
-
[11]
Cram\'er, H. (1938). Sur un nouveau th\'eor\`eme-limite de la th\'eorie des probabilit\'es. In Colloque consacr\'e \`a la Th\'eorie des Probabilit\'es , volume 736, pages 2--23. Hermann
1938
-
[12]
Cram\'er, H. (1944). On a new limit theorem of the theory of probability. Uspekhi Mat. Nauk. , 10:166--178
1944
-
[13]
and Touchette, H
Cram\'er, H. and Touchette, H. (2022). On a new limit theorem in probability theory (translation of 'sur un nouveau th\'eor\`eme-limite de la th\'eorie des probabilit\'es'). arXiv , 1802.05988
2022 arXiv
-
[14]
Devroye, L. (1986). Non-Uniform Random Variate Generation . Springer-Verlag, New York
1986
-
[15]
Devroye, L. (1987). Branching processes in the analysis of the heights of trees. Acta Informatica , 24(3):277--298
1987
-
[16]
Devroye, L. (1988). Applications of the theory of records in the study of random trees. Acta Informatica , 26(1-2):123--130
1988
-
[17]
and Lu, J
Devroye, L. and Lu, J. (1995). The strong convergence of maximal degrees in uniform random recursive trees and dags. Random Structures and Algorithms , 7(1):1--14
1995
-
[18]
Drmota, M. (2009). Random Trees: an Interplay between Combinatorics and Probability . Springer Science & Business Media
2009
-
[19]
Durrett, R. (2019). Probability: Theory and Examples , volume 49. Cambridge University Press
2019
-
[20]
Eslava, L. (2022). Depth of vertices with high degree in random recursive trees. ALEA. Latin American Journal of Probability & Mathematical Statistics , 19(1)
2022
-
[21]
and Saram \"a ki, J
Holme, P. and Saram \"a ki, J. (2013). Temporal networks as a modeling framework. In Temporal Networks , pages 1--14. Springer
2013
-
[22]
and Saram \"a ki, J
Holme, P. and Saram \"a ki, J. (2019). Temporal Network Theory , volume 2. Springer
2019
-
[23]
and Saramäki, J
Holme, P. and Saramäki, J. (2012). Temporal networks. Physics Reports , 519(3):97--125
2012
-
[24]
M., Cannataro, M., Guzzi, P
Hosseinzadeh, M. M., Cannataro, M., Guzzi, P. H., and Dondi, R. (2022). Temporal networks in biology and medicine: a survey on models, algorithms, and tools. Network Modeling Analysis in Health Informatics and Bioinformatics , 12(1):10
2022
-
[25]
Janson, S. (2005). Asymptotic degree distribution in random recursive trees. Random Structures and Algorithms , 26(1-2):69--83
2005
-
[26]
Klenke, A. (2008). Probability Theory . Springer
2008
-
[27]
and Moon, J
Meir, A. and Moon, J. W. (1978). On the altitude of nodes in random trees. Canadian Journal of Mathematics , 30(5):997–1015
1978
-
[28]
B., Nikoletseas, S., Raptopoulos, C., and Spirakis, P
Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., and Spirakis, P. G. (2024). On the existence of -temporal cliques in random simple temporal graphs. arXiv , 2404.07147
2024 arXiv
-
[29]
Pittel, B. (1994). Note on the heights of random recursive trees and random m -ary search trees. Random Structures and Algorithms , 5(2):337--347
1994
-
[30]
Sanjay Kumar, N. B. and Panda, B. S. (2020). Analysis of social network metrics based on the model of random recursive tree. Journal of Interdisciplinary Mathematics , 23(1):237--246
2020
-
[31]
Shi, Z. (2015). Branching Random Walks , volume 2151. Springer
2015
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.