Online packing of the three largest trees
Abstract
For every n≥4, arbitrary trees of orders $n,n-1,n-2$ can be packed into Kn online, in decreasing order of size: each tree must be embedded before the next is revealed, and earlier embeddings cannot be changed. This strengthens the classical three-tree packing theorem of Hobbs, Bourgeois and Kasiraj (1987). In particular, the second tree is embedded without knowing the third, and the resulting pair of copies can be extended to accommodate every possible third tree. Our strategy is to embed the first two trees so that their union is $2$-degenerate. We prove that the complement of every $2$-degenerate graph on n vertices contains every tree of order n−2, which guarantees the final move. The main ingredient is an embedding lemma for spiders whose center must occupy a prescribed vertex having degree at most two in the forbidden graph. We then extend this lemma to arbitrary trees by induction.
Related
- On the largest common subtree of uniform attachment trees
- The packing and covering number of trees are local
- Largest Rashomon sets of decision trees for robust contextual optimization
- Packing and covering random trees
- Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments
BibTeX
@misc{cisinski2026online,
title = {{Online packing of the three largest trees}},
author = {Maciej Cisiński},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04674},
eprint = {2611.04674},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04674},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Online packing of the three largest trees
AU - Maciej Cisiński
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04674
UR - https://arxiv.org/abs/2611.04674
AB - For every n≥4, arbitrary trees of orders $n,n-1,n-2$ can be packed into K_n online, in decreasing order of size: each tree must be embedded before the next is revealed, and earlier embeddings cannot be changed. This strengthens the classical three-tree packing theorem of Hobbs, Bourgeois and Kasiraj (1987). In particular, the second tree is embedded without knowing the third, and the resulting pair of copies can be extended to accommodate every possible third tree. Our strategy is to embed the first two trees so that their union is $2$-degenerate. We prove that the complement of every $2$-degenerate graph on n vertices contains every tree of order n−2, which guarantees the final move. The main ingredient is an embedding lemma for spiders whose center must occupy a prescribed vertex having degree at most two in the forbidden graph. We then extend this lemma to arbitrary trees by induction.
ER -