On the extremal maximum agreement subtree problem

Abstract Given two phylogenetic trees with leaf set { 1 , … , n } the maximum agreement subtree problem asks what is the maximum size of the subset A ⊆ { 1 , … , n } such that the two trees are equivalent when restricted to A . The long-standing extremal version of this problem focuses on the smallest number of leaves, mast ( n ) , on which any two (binary and unrooted) phylogenetic trees with n leaves must agree. In this work, we prove that this number grows asymptotically as Θ ( log n ) ; thus closing the enduring gap between the lower and upper asymptotic bounds on mast ( n ) .