Capturing a phylogenetic tree when the number of character states varies with the number of leaves

We show that for any two values $\alpha ,\beta >0$ for which $\alpha +\beta >1$ then there is a value $N$ so that for all $n\ge N$ the following holds. For any binary phylogenetic tree $T$ on $n$ leaves there is a set of $\lfloor n^{\alpha }\rfloor$ characters that capture $T$, and for which each character takes at most $\lfloor n^{\beta }\rfloor$ distinct states. Here `capture’ means that $T$ is the unique perfect phylogeny for these characters. Our short proof of this combinatorial result is based on the probabilistic method.