pipette
ESEspañol

Packing and covering random trees

Caelan Atamanchuk, Simon Briend, Serte Donderwinkel, Elaine Herrera

Preprint

In the authors' words

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 and finite variance we let be a Bienaym\'e tree with offspring distribution conditioned to have size . We prove that the packing number (resp. covering number) of with balls of radii is asymptotically equivalent to (resp. ), for a universal constant . 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 by balls of fixed radius , and thereafter let tend to . We then extend these results to the Brownian continuum random tree conditioned to have mass . For this model, we prove that the packing (resp. covering) number with balls of radii are asymptotically equivalent to (resp. ), for the same constant , 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 finite variance Bienaym\'e trees of size , by showing that it lies between and with high probability, for a constant that only depends on the offspring variance.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 74 pages, 8 figures