A High Quartets Distance Construction

Abstract

Given two binary trees on $N$ labeled leaves, the quartet distance between the trees is the number of disagreeing quartets. By permuting the leaves at random, the expected quartets distance between the two trees is $\frac{2}{3}\left(\genfrac{}{}{0ex}{}{N}{4}\right)$. However, no strongly explicit construction reaching this bound asymptotically was known. We consider complete, balanced binary trees on $N=2^n$ leaves, labeled by $n$ long bit sequences. Ordering the leaves in one tree by the prefix order, and in the other tree by the suffix order, we show that the resulting quartet distance is $\left(\frac{2}{3}+o(1)\right)\left(\genfrac{}{}{0ex}{}{N}{4}\right)$, and it always exceeds the $\frac{2}{3}\left(\genfrac{}{}{0ex}{}{N}{4}\right)$ bound.