An Improved Lower Bound on the Largest Common Subtree of Random Leaf-Labeled Binary Trees

It is known that the size of the largest common subtree (i.e., the maximum agreement subtree) of two independent random binary trees with n given labeled leaves is of order between n^(0.366) and n^(1/2). We improve the lower bound to order n^(0.4464) by constructing a common subtree recursively and by proving a lower bound for its asymptotic growth. The construction is a modification of an algorithm proposed by D. Aldous by splitting the tree at the centroid and by proceeding recursively.