Packing and covering random trees
math.PR, math.CO
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 74 pages, 8 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the sizes of optimal packings and coverings of conditioned branching processes by balls with growing radii.
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 σ squared 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 much less than γ n much less than n 1/2 is asymptotically equivalent to C n /(σ squared γ n 2) (resp. C n /(4σ squared γ 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 infinity. 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 epsilon are asymptotically equivalent to C/epsilon squared (resp. C/(4 epsilon 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.
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves
- A zero-one law for swap-invariant events in uniform spanning forests
- Bernoulli flow for Erd s-R'enyi graphs