Bryant, David; McKenzie, Andy; Steel, Mike The size of a maximum agreement subtree for random binary trees. (English) Zbl 1026.92030 Janowitz, M. F. (ed.) et al., Bioconsensus. DIMACS working group meetings on bioconsensus, October 25-26, 2000 and October 2-5, 2001, DIMACS Center. Providence, RI: American Mathematical Society (AMS). DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 61, 55-65 (2003). Summary: In computational biology, a comrnon way to compare two rooted trees that classify the same set \(L\) of labelled leaves is to determine the largest subset of \(L\) on which the two trees agree. We consider the size of this quantity if one or both trees are generated randomly, according to two simple null models. We obtain analytical bounds, as well as providing some simulation results that suggest a power law similar to the related problem of determining the length of the longest increasing sequence in a random permutation.For the entire collection see [Zbl 1012.00048]. Cited in 1 ReviewCited in 9 Documents MSC: 92D15 Problems related to evolution 05C90 Applications of graph theory 05C05 Trees 60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) 68R10 Graph theory (including graph drawing) in computer science Keywords:phylogeny; maximum agreement subtree; distributions on trees; Yule-Harding model; uniform model PDFBibTeX XMLCite \textit{D. Bryant} et al., DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 61, 55--65 (2003; Zbl 1026.92030)