The layer distribution of the random recursive tree and the minimum of the Poisson-weighted infinite tree
The layer of a vertex of a tree is the number of rounds of leaf removal after which the vertex is a leaf. Stepanyants, Krapivsky, Hartle and Krioukov computed the limiting proportion $\ell_k$ of vertices at layer $k$ in a random recursive tree as an integral of an iterated nonlinear recursion, showed $e^{-k}\lesssim\sum_{j\ge k}\ell_j\lesssim e^{-k/e}$, and conjectured that $\ell_k=\exp[-k/e-\tfrac{3}{2e}\log k-O(1)]$. We prove that $\ell_k e^{k/e}k^{3/(2e)}$ converges to a positive finite constant. The recursion is the law of the minimal position $M_k$ in generation $k$ of the Poisson-weighted infinite tree, so that $\sum_{j\ge k}\ell_j=\mathbb{E} e^{-M_k}$, and the asymptotics follow from the results of Addario-Berry and Ford and of Aïdékon on that branching random walk. We also prove the layer half of their second conjecture: the largest layer $L_n$ of a random recursive tree on $n$ vertices equals half its diameter rounded down, and $L_n=e\log n-\tfrac32\log\log n+O_\mathbb{P}(1)$.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-08
- DOI
- https://doi.org/10.5281/zenodo.24064371
- Primary Topic
- Stochastic processes and statistical mechanics
- Type
- preprint