Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 13 min ago
PreprintCC BY-NC-SA 4.0arXiv

The packing and covering number of trees are local

  • Caelan Atamanchuk
  • Simon Briend
  • Serte Donderwinkel
  • Elaine Herrera
Open at sourcePDFDOICite

Abstract

For a graph, its r-packing number is the size of the largest r-separated set and its r-covering number is the size of the smallest r-net. We show that the r-covering number and r-packing number are continuous in the fringe topology on locally finite trees. This recovers convergence results by Meir and Moon for e.g. uniform binary trees, uniform plane trees, uniform Polyá trees and random recursive trees, and proves new results for many other tree models, such as size-conditioned Bienaymé trees, simply generated trees, m-ary search trees, the minimum spanning tree of the complete graph and preferential attachment trees. Moreover, our formulation provides an intuitive interpretation of the limiting constant, that also provides an easy route for explicit computations in the case of size-conditioned Bienaymé trees. Our method relies on the definition of a canonical minimum r-net, and a relation between covering numbers and packing numbers due to Meir and Moon.

Related

  1. Packing and covering random trees
    Caelan Atamanchuk, Simon Briend, Serte Donderwinkel +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  2. A proof of the generalized packing-covering conjecture
    Gianira N. Alfarano, Giuseppe Marino, Alessandro Neri +1
    HALPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsHALarXiv
  3. A non-lattice periodic point set beating the optimal lattice packing-covering constant in dimension five
    Sven Ahrend, Mathieu Dutour Sikirić
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  4. Auxiliary Codes and the Generalized Packing-Covering Conjecture
    Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. A covering construction of labelled packing measure and content
    Peizhi Liu
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{atamanchuk2026packing,
  title = {{The packing and covering number of trees are local}},
  author = {Caelan Atamanchuk and Simon Briend and Serte Donderwinkel and Elaine Herrera},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.37539},
  eprint = {2610.37539},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37539},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - The packing and covering number of trees are local
AU  - Caelan Atamanchuk
AU  - Simon Briend
AU  - Serte Donderwinkel
AU  - Elaine Herrera
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.37539
UR  - https://arxiv.org/abs/2610.37539
AB  - For a graph, its r-packing number is the size of the largest r-separated set and its r-covering number is the size of the smallest r-net. We show that the r-covering number and r-packing number are continuous in the fringe topology on locally finite trees. This recovers convergence results by Meir and Moon for e.g. uniform binary trees, uniform plane trees, uniform Polyá trees and random recursive trees, and proves new results for many other tree models, such as size-conditioned Bienaymé trees, simply generated trees, m-ary search trees, the minimum spanning tree of the complete graph and preferential attachment trees. Moreover, our formulation provides an intuitive interpretation of the limiting constant, that also provides an easy route for explicit computations in the case of size-conditioned Bienaymé trees. Our method relies on the definition of a canonical minimum r-net, and a relation between covering numbers and packing numbers due to Meir and Moon.
ER  -