Name
Abstract | ||
|---|---|---|
We show that the expected size of the maximum agreement subtree of two n-leaf trees, uniformly random among all trees with the shape, is circle minus(root n). To derive the lower bound, we prove a global structural result on a decomposition of rooted binary trees into subgroups of leaves called blobs. To obtain the upper bound, we generalize a first moment argument from [D. I. Bernstein, et al., SIAM J. Discrete Math., 29 (2015), pp. 2065-2074] for random tree distributions that are exchangeable and not necessarily sampling consistent. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1137/18M1213695 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
maximum agreement subtree,exchangeability,sampling consistency | Discrete mathematics,Combinatorics,Tree (data structure),Mathematics | Journal |
Volume | Issue | ISSN |
33 | 4 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pratik Misra | 1 | 0 | 0.68 |
| Seth Sullivant | 2 | 93 | 19.17 |