Packing and covering random trees
Abstract
We study the sizes of optimal packings and coverings of conditioned branching processes by balls with growing radii. We find a universal limiting constant, and thereby establish universality of packing and covering numbers across different scales and different offspring distributions. To be precise, for μ an offspring distribution with mean $1$ and finite variance σ2 we let Tn be a Bienaymé tree with offspring distribution μ conditioned to have size n. We prove that the packing number (resp. covering number) of Tn with balls of radii 1≪ γn ≪ n1/2 is asymptotically equivalent to C n /(σ2 γn2) (resp. C n /(4σ2 γn2)), for a universal constant C. We also show that the order of limits can be exchanged and that the same limit occurs when we first consider the limiting covering number of Tn by balls of fixed radius R, and thereafter let R tend to ∞. We then extend these results to the Brownian continuum random tree conditioned to have mass $1$. For this model, we prove that the packing (resp. covering) number with balls of radii ε are asymptotically equivalent to C/ε2 (resp. C/(4ε2)), for the same constant C, in contrast with a conjecture by Aldous. Finally, our results answer a question by Devroye, Eide and Pralat on the asymptotic burning number of mean $1$ finite variance Bienaymé trees of size n, by showing that it lies between (c+o(1)) n1/3 and (2c+o(1))n1/3 with high probability, for a constant c that only depends on the offspring variance.
Related
- The packing and covering number of trees are local
- A proof of the generalized packing-covering conjecture
- A non-lattice periodic point set beating the optimal lattice packing-covering constant in dimension five
- Auxiliary Codes and the Generalized Packing-Covering Conjecture
- A covering construction of labelled packing measure and content
BibTeX
@misc{atamanchuk2026packing,
title = {{Packing and covering random trees}},
author = {Caelan Atamanchuk and Simon Briend and Serte Donderwinkel and Elaine Herrera},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40150},
eprint = {2610.40150},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40150},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Packing and covering random trees
AU - Caelan Atamanchuk
AU - Simon Briend
AU - Serte Donderwinkel
AU - Elaine Herrera
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40150
UR - https://arxiv.org/abs/2610.40150
AB - We study the sizes of optimal packings and coverings of conditioned branching processes by balls with growing radii. We find a universal limiting constant, and thereby establish universality of packing and covering numbers across different scales and different offspring distributions. To be precise, for μ an offspring distribution with mean $1$ and finite variance σ^2 we let T_n be a Bienaymé tree with offspring distribution μ conditioned to have size n. We prove that the packing number (resp. covering number) of T_n with balls of radii 1≪ γ_n ≪ n^1/2 is asymptotically equivalent to C n /(σ^2 γ_n^2) (resp. C n /(4σ^2 γ_n^2)), for a universal constant C. We also show that the order of limits can be exchanged and that the same limit occurs when we first consider the limiting covering number of T_n by balls of fixed radius R, and thereafter let R tend to ∞. We then extend these results to the Brownian continuum random tree conditioned to have mass $1$. For this model, we prove that the packing (resp. covering) number with balls of radii ε are asymptotically equivalent to C/ε^2 (resp. C/(4ε^2)), for the same constant C, in contrast with a conjecture by Aldous. Finally, our results answer a question by Devroye, Eide and Pralat on the asymptotic burning number of mean $1$ finite variance Bienaymé trees of size n, by showing that it lies between (c+o(1)) n^1/3 and (2c+o(1))n^1/3 with high probability, for a constant c that only depends on the offspring variance.
ER -