Packing and covering random trees

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 σ² we let Tₙ be a Bienaymé tree with offspring distribution $μ$ conditioned to have size n. We prove that the packing number (resp. covering number) of Tₙ with balls of radii 1 γₙ n1/2 is asymptotically equivalent to C n /(σ² γₙ²) (resp. C n /(4σ² γₙ²)), 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ₙ 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/ε² (resp. C/(4ε²)), 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.