The maximum agreement subtree problem

par Bhalchandra D. Thatte (Universidade Federal de Minas Gerais, Brasil)

mardi 12 févr. 2019, 10:45 → 11:45 Europe/Paris

Bât. Braconnier, salle Fokko du Cloux (ICJ, Université Lyon 1)

(Joint work with Daniel Martin, Universidade Federal do ABC, Brasil)

Given two two binary phylogenetic trees on the leaf set {1,2,...,n}, we consider their maximum agreement subtree. It has been conjectured that any maximum agreement subtree of the two trees has $\Theta(\log n)$ leaves. We show that there is an agreement subtree with $\Omega(\sqrt{\log n})$ leaves, thus improving on an earlier bound of $\Omega(\log\log n)$.

To achieve this bound, we combine different special cases: we first prove the conjecture when one of the trees is balanced or when one of the trees is a caterpillar. We then prove a Ramsey theoretic result that roughly says that every binary phylogenetic tree contains a sufficiently large balanced subtree or a sufficiently large caterpillar, a result that is interesting on its own. We use this result to get the $\Omega(\sqrt{\log n})$ bound. Finally, we show that there is an $\alpha > 0$ such that when both the trees are balanced, they have a common subtree with $\Omega(n^\alpha)$ leaves.