Defining a Phylogenetic Tree with the Minimum Number of $r$-State Characters
Magnus Bordewich, Charles Semple · SIAM Journal on Discrete Mathematics · 2015
Semple and Steel (2002) showed that if ${\cal T}$ is a phylogenetic $X$-tree and ${\cal C}$ is a collection of $r$-state characters that defines ${\cal T}$, then $|{\cal C}|\ge \lceil(n-3)/(r-1)\rceil$, where $n=|X|$. In this paper, we show that, provided $n$ is sufficiently large, this lower bound is sharp. Furthermore, we show that, for all n\ge 13, there exists a collection of 4-state characters of size $\lceil(n-3)/3\rceil$ that defines ${\cal T}$, but there is a phylogenetic $X$-tree with n=12 which is not defined by any set of 3 characters.