A strengthened bound on the number of states required to characterize maximum parsimony distance

Mareike Fischer; Steven Kelk; Sofia Vazquez Alferez

paper

A strengthened bound on the number of states required to characterize maximum parsimony distance

arXiv:2506.09888

Abstract

In this article we prove that the distance $d_{MP} (T_{1}, T_{2}) = k$ between two unrooted binary phylogenetic trees $T_{1}, T_{2}$ on the same set of taxa can be defined by a character that is convex on one of $T_{1}, T_{2}$ and which has at most $2 k$ states. This significantly improves upon the previous bound of $7 k - 5$ states. We also show that for every $k \geq 1$ there exist two trees $T_{1}, T_{2}$ with $d_{MP} (T_{1}, T_{2}) = k$ such that at least $k + 1$ states are necessary in any character that achieves this distance and which is convex on one of $T_{1}, T_{2}$ . We augment these lower and upper bounds with an empirical analysis which shows that in practice significantly fewer than $k + 1$ states are usually required.