Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves

preprint2015arXivOpen access

Abstract

Given an edge-weighted tree TT with nn leaves, sample the leaves uniformly at random without replacement and let WkW_k, 2≤k≤n2 \le k \le n, be the length of the subtree spanned by the first kk leaves. We consider the question, "Can TT be identified (up to isomorphism) by the joint probability distribution of the random vector (W2,…,Wn)(W_2, \ldots, W_n)?" We show that if TT is known {\em 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)(k+1)-valent and rooted kk-ary trees for k≥2k \ge 2 and caterpillars.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.