The maximum agreement subtree problem

In this paper, we investigate an extremal problem on binary phylogenetic trees. Given two such trees T1T1 and  T2T2, both with leaf-set {1,2,…,n}{1,2,…,n}, we are interested in the size of the largest subset S⊆{1,2,…,n}S⊆{1,2,…,n} of leaves in a common subtree of  T1T1 and  T2T2. We show that any two binary phylogenetic trees have a common subtree on Ω(logn) leaves, thus improving on the previously known bound of Ω(loglogn)Ω(loglogn) due to Steel and Székely. To achieve this improved bound, we first consider two special cases of the problem: when one of the trees is balanced or a caterpillar, we show that the largest common subtree has Ω(logn)Ω(logn) leaves. We then handle the general case by proving and applying a Ramsey-type result: that every binary tree contains either a large balanced subtree or a large caterpillar. We also show that there are constants c,α>0c,α>0 such that, when both trees are balanced, they have a common subtree on cnαcnα leaves. We conjecture that it is possible to take α=1/2α=1/2 in the unrooted case, and both c=1c=1 and α=1/2α=1/2 in the rooted case.