On the maximum quartet distance between phylogenetic trees

Abstract

A conjecture of Bandelt and Dress states that the maximum quartet distance between any two phylogenetic trees on $n$ leaves is at most $(\frac{2}{3}+o(1))\left(\genfrac{}{}{0ex}{}{n}{4}\right)$. Using the machinery of flag algebras we improve the currently known bounds regarding this conjecture, in particular we show that the maximum is at most $(0.69+o(1))\left(\genfrac{}{}{0ex}{}{n}{4}\right)$. We also give further evidence that the conjecture is true by proving that the maximum distance between caterpillar trees is at most $(\frac{2}{3}+o(1))\left(\genfrac{}{}{0ex}{}{n}{4}\right)$.

arXiv admin note: text overlap with arXiv:1203.2723