A High Quartets Distance Construction

Chor, B. and Erdős, Péter and Komornik, J. (2019) A High Quartets Distance Construction. ANNALS OF COMBINATORICS, 23 (1). pp. 51-65. ISSN 0218-0006

Preview

Text 1606.02641.pdf Download (174kB) | Preview

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 quartet distance between the two trees is 23(N4) . However, no strongly explicit construction reaching this bound asymptotically was known. We consider complete, balanced binary trees on N=2n leaves, labeled by n bits long 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 (23+o(1))(N4) , and it always exceeds the 23(N4) bound.

Actions (login required)

Edit Item