{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:26:05Z","timestamp":1787325965536,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/130924469","type":"journal-article","created":{"date-parts":[[2015,4,21]],"date-time":"2015-04-21T12:07:06Z","timestamp":1429618026000},"page":"835-853","source":"Crossref","is-referenced-by-count":0,"title":["Defining a Phylogenetic Tree with the Minimum Number of $r$-State Characters"],"prefix":"10.1137","volume":"29","author":[{"given":"Magnus","family":"Bordewich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charles","family":"Semple","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,4,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.015"},{"key":"atypb2","first-page":"387","author":"Buneman P.","year":"1971","journal-title":"Edinburgh"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90002-8"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"atypb5","first-page":"52","author":"Gysel R.","year":"2010","journal-title":"Berlin"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102416696"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/090776305"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2001.0772"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00174-1"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"C. Semple and M. Steel,\n                      Phylogenetics\n                      , Oxford University Press, Oxford, 2003.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020311"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130924469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:24:55Z","timestamp":1787322295000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130924469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130924469"],"URL":"https:\/\/doi.org\/10.1137\/130924469","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}