pith. sign in

arxiv: 1506.01091 · v1 · pith:Q4TMKDCFnew · submitted 2015-06-03 · 🧮 math.CO · math.PR

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

classification 🧮 math.CO math.PR
keywords edge-weightedleavestreesfamiliesrandomspannedtreeanswer
0
0 comments X
read the original abstract

Given an edge-weighted tree $T$ with $n$ leaves, sample the leaves uniformly at random without replacement and let $W_k$, $2 \le k \le 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 $(W_2, \ldots, W_n)$?" We show that if $T$ 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)$-valent and rooted $k$-ary trees for $k \ge 2$ and caterpillars.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.