PreprintCC BY 4.0arXiv
On the largest common subtree of uniform attachment trees
Abstract
We study the largest common subtree of two independent unlabeled uniform attachment trees (also known as random recursive trees). Our main result shows that, when the two trees have n vertices each, their largest common subtree has at least n0.83 vertices with high probability. This is obtained by starting with the common subtree induced by the Ulam--Harris labels in the two trees and improving using local optimization steps. We also give some upper bounds and bounds for general random tree growth models. We leave as an intriguing open question to understand the magnitude of the size of the largest common subtree.
Related
- Rare subtree patterns in size-conditioned Bienaymé trees: Poisson approximation and declumping
- Persistent Hubs and Sharp Asymptotics in Eigenvector Preferential Attachment Trees
- Online packing of the three largest trees
- Largest Rashomon sets of decision trees for robust contextual optimization
- A Pittel-type limit law for the largest component of random d-uniform hypergraphs: enumeration and excursions
BibTeX
@misc{baumler2026largest,
title = {{On the largest common subtree of uniform attachment trees}},
author = {Johannes Bäumler and Céline Kerriou and Bas Lodewijks and James Martin and Emil Powierski and Miklós Z. Rácz and Anirudh Sridhar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30098},
eprint = {2609.30098},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30098},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the largest common subtree of uniform attachment trees
AU - Johannes Bäumler
AU - Céline Kerriou
AU - Bas Lodewijks
AU - James Martin
AU - Emil Powierski
AU - Miklós Z. Rácz
AU - Anirudh Sridhar
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30098
UR - https://arxiv.org/abs/2609.30098
AB - We study the largest common subtree of two independent unlabeled uniform attachment trees (also known as random recursive trees). Our main result shows that, when the two trees have n vertices each, their largest common subtree has at least n^0.83 vertices with high probability. This is obtained by starting with the common subtree induced by the Ulam--Harris labels in the two trees and improving using local optimization steps. We also give some upper bounds and bounds for general random tree growth models. We leave as an intriguing open question to understand the magnitude of the size of the largest common subtree.
ER -