The largest common subtree of two random trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914229729099776 |
|---|---|
| author | Angel, Omer Atamanchuk, Caelan Brandenberger, Anna Donderwinkel, Serte Khanfir, Robin |
| author_facet | Angel, Omer Atamanchuk, Caelan Brandenberger, Anna Donderwinkel, Serte Khanfir, Robin |
| contents | We study the size and structure of the largest common subtree (LCS) between two independent Bienaymé trees conditioned to have size $n$. When the trees are critical with finite $2$nd and $(2+κ)$th moment respectively for some $κ>0$, we prove that the LCS has size of order $\sqrt{n}$, and is approximated by the length of three paths meeting at a central node. Moreover, we show that the largest common subtree between two critical independent Bienaymé trees with size $n$ and finite second moments may be much larger than $\sqrt{n}$, implying that our result is tight. We also pose a number of open questions and suggestions for future research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_00119 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The largest common subtree of two random trees Angel, Omer Atamanchuk, Caelan Brandenberger, Anna Donderwinkel, Serte Khanfir, Robin Probability Combinatorics 60C05, 60J80, 05C05, 05C60 We study the size and structure of the largest common subtree (LCS) between two independent Bienaymé trees conditioned to have size $n$. When the trees are critical with finite $2$nd and $(2+κ)$th moment respectively for some $κ>0$, we prove that the LCS has size of order $\sqrt{n}$, and is approximated by the length of three paths meeting at a central node. Moreover, we show that the largest common subtree between two critical independent Bienaymé trees with size $n$ and finite second moments may be much larger than $\sqrt{n}$, implying that our result is tight. We also pose a number of open questions and suggestions for future research. |
| title | The largest common subtree of two random trees |
| topic | Probability Combinatorics 60C05, 60J80, 05C05, 05C60 |
| url | https://arxiv.org/abs/2601.00119 |