Expected Number of Induced Subtrees Shared by Two Independent Copies of a Random Tree
Boris Pittel
Source abstract
Abstract. Consider a rooted tree [Formula: see text] with leaf-set [Formula: see text] and with all nonleaf vertices having out-degree 2, at least. A rooted tree [Formula: see text] with leaf-set [Formula: see text] is induced by [Formula: see text] in [Formula: see text] if [Formula: see text] is the lowest common ancestor subtree for [Formula: see text], with all its degree-2 vertices suppressed. A “maximum agreement subtree” (MAST) for a pair of two trees [Formula: see text] and [Formula: see text] is a tree [Formula: see text] with a largest leaf-set [Formula: see text] such that [Formula: see text] is induced by [Formula: see text] both in [Formula: see text] and [Formula: see text]. Bryant, McKenzie, and Steel [ BioConsensus, AMS, Providence, RI, 2003, pp. 55–65] and Bernstein et al. [ SIAM J. Discrete Math., 29 (2015), pp. 2065–2074] proved, among other results, that for [Formula: see text] and [Formula: see text] being two independent copies of a random binary (uniform or Yule–Harding distributed) tree [Formula: see text], the likely magnitude order of [Formula: see text] is [Formula: see text]. We prove this bound for a wide class of random rooted trees: [Formula: see text] is a terminal tree of a branching, Galton–Watson, process with an ordered-offspring distribution of mean 1, conditioned on “total number of leaves is [Formula: see text].”
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.