{"id":"arxiv/2606.06905","url":"https://arxiv.org/abs/2606.06905","tags":["math.CO"],"score":0,"title":"An Explicit $O(r\\log r)$ Threshold for Attaining the Semple--Steel Bound with $r$-State Characters","domain":"math.CO","source":"arxiv","authors":["Peng Li","Yangjing Long"],"reviews":0,"subject":"math.CO","summary":"Let $d_r(n)$ be the maximum, over all binary phylogenetic trees with $n$ leaves, of the minimum number of $r$-state characters required to define the tree. Semple and Steel proved that $d_r(n)\\geq\\lceil(n-3)/(r-1)\\rceil$, and Bordewich and Semple proved that equality holds for each fixed $r$ and all sufficiently large $n$. We study the corresponding threshold $n_r$, the least $N$ for which equality holds for every $n\\geq N$. The Bordewich--Semple construction yields an explicit polynomial upper bound of order $O(r^5)$ for this threshold. We prove the near-linear estimate \\[ 3r+1\\leq n_r\\leq…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-05","reactions":{}}