:: An Improved Lower Bound on the Largest Common Subtree of Random Leaf-Labeled Binary Trees (Dr. Ali Khezeli)

In some models of random combinatorial structures‎, ‎an object of interest is the largest common substructures of two samples‎. ‎A well-studied example is the size of the largest increasing subsequence in a random permutation‎, ‎which can be regarded as the largest common subset in which the permutation induces the same total order as the identity permutation (or another random permutation)‎. ‎In the context of trees‎, ‎the largest common subtree has been proposed in biology as a measure of similarity between two phylogenetic trees (also known as the maximum agreement subtree)‎. ‎With this motivations‎, ‎some works have studied the expected size of the largest common subtree of two independent random trees‎.

‎ In this paper‎, ‎we consider two random binary trees built on n common labeled leaves‎. ‎It is known that the expected size of the largest common subtree is of order between n^0.366 and n^½‎. ‎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‎.