On the Maximum Quartet Distance between Phylogenetic Trees
Noga Alon, Humberto Naves, Benny Sudakov · SIAM Journal on Discrete Mathematics · 2016
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))\binom{n}{4}$. 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))\binom{n}{4}$. 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))\binom{n}{4}$.