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

Pratik Misra, Seth Sullivant

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,…