Metraipolis › archive › dc_adacdb057738
On the largest common subtree of uniform attachment trees — arXiv:2609.30098
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.30098
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T06:07:56.463Z
- SHA-256 of the archived text
466dbcf70319404f620a8b3538d2e3f98668e15af5eccf2db809aacf1f217341- Stable URL of this page
https://metraipolis.com/documento/dc_adacdb057738
How to cite
On the largest common subtree of uniform attachment trees — arXiv:2609.30098 — arXiv (en), https://arxiv.org/abs/2609.30098 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_adacdb057738 (Metraipolis archive dc_adacdb057738, sha256 466dbcf70319404f620a8b3538d2e3f98668e15af5eccf2db809aacf1f217341)
BibTeX
@misc{dcadacdb057738,
title = {On the largest common subtree of uniform attachment trees — arXiv:2609.30098},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.30098},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_adacdb057738; sha256 466dbcf70319404f620a8b3538d2e3f98668e15af5eccf2db809aacf1f217341},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30098. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in math.PR).
Categorie arXiv: Probability (math.PR) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.30098 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T05:35:05.154Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).