- Main
Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves
Published Web Location
https://doi.org/10.1016/j.aam.2018.01.001Abstract
Given an edge-weighted tree T with n leaves, sample the leaves uniformly at random without replacement and let Wk , 2 ≤ k ≤ n, be the length of the subtree spanned by the first k leaves. We consider the question, "Can T be identified (up to isomorphism) by the joint probability distribution of the random vector (W2, …, Wn )?" We show that if T is known a priori to belong to one of various families of edge-weighted trees, then the answer is, "Yes." These families include the edge-weighted trees with edge-weights in general position, the ultrametric edge-weighted trees, and certain families with equal weights on all edges such as (k + 1)-valent and rooted k-ary trees for k ≥ 2 and caterpillars.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.