An improved bound on the Maximum Agreement Subtree problem

Abstract

We improve the lower bound on the extremal version of the Maximum Agreement Subtree problem. Namely we prove that two binary trees on the same $n$ leaves have subtrees with the same $\ge c\log \log n$ leaves which are homeomorphic, such that homeomorphism is identity on the leaves.

5 pages, 1 figure