Expected number of induced subtrees shared by two independent copies of a random tree

DOI10.1137/21M1416771MaRDI QIDQ6360370arXivFDO

Authors Boris Pittel

Publication date 11 February 2021

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Enumeration in graph theory (05C30) Asymptotic expansions of solutions to ordinary differential equations (34E05)

Abstract: Consider a rooted tree $T$ with leaf-set $[n]$, and with all non-leaf vertices having out-degree $2$, at least. A rooted tree $mathcalT$ with leaf-set $Ssubset[n]$ is induced by $S$ in $T$ if $mathcalT$ is the lowest common ancestor subtree for $S$, with all its degree-2 vertices suppressed. A "maximum agreement subtree" (MAST) for a pair of two trees $T^{\prime }$ and $$ is a tree $mathcalT$ with a largest leaf-set $Ssubset[n]$ such that $mathcalT$ is induced by $S$ both in $T^{\prime }$ and $$. Bryant et al. cite{BryMcKSte} and Bernstein et al. cite{Ber} proved, among other results, that for $T^{\prime }$ and $$ being two independent copies of a random binary (uniform or Yule-Harding distributed) tree $T$, the likely magnitude order of $$ is $O(n^{1/2})$. We prove this bound for a wide class of random rooted trees : $T$ 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 $n$".

This page was built for publication: Expected number of induced subtrees shared by two independent copies of a random tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360370)