Teasing Apart Two Trees (2007)
AuthorsSteel, M., Szekely, L.show all
A widely-studied model for generating binary sequences is to 'evolve' them on a tree according to a symmetric Markov process. We show that under this model distinguishing the true (model) tree from a false one is substantially "easier" (in terms of the sequence length needed) than determining the true tree. The key tool is a new and tight Ramsey-type result for binary trees.
CitationSteel, M., Szekely, L. (2007) Teasing Apart Two Trees. Combinatorics, Probability and Computing, 16(6), pp. 903-922.
This citation is automatically generated and may be unreliable. Use as a guide only.