Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

RECOVERING A TREE FROM THE LENGTHS OF SUBTREES SPANNED BY A RANDOMLY CHOSEN SEQUENCE OF LEAVES.

  • Author(s): Evans, Steven N;
  • Lanoue, Daniel
  • et al.
Abstract

Given an edge-weighted tree T with n leaves, sample the leaves uniformly at random without replacement and let Wk , 2 ≤ kn, 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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View