Bounds on the expected size of the maximum agreement subtree for a given tree shape

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 $\Theta (\sqrt{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 for random tree distributions that are exchangeable and not necessarily sampling consistent.

9 pages, 5 figures