On the Largest Common Subtree of Random Leaf-Labeled Binary Trees
| Autor: | Aldous, David J. |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The size of the largest common subtree (maximum agreement subtree) of two independent uniform random binary trees on $n$ leaves is known to be between orders $n^{1/8}$ and $n^{1/2}$. By a construction based on recursive splitting and analyzable by standard "stochastic fragmentation" methods, we improve the lower bound to order $n^\beta$ for $\beta = \frac{\sqrt{3} - 1}{2} = 0.366$. Improving the upper bound remains a challenging problem. Comment: 24 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|