Representing Partitions on Trees

摘要: In evolutionary biology, biologists often face the problem of constructing a phylogenetic tree on set $X$ species from multiset $\Pi$ partitions corresponding to various attributes these species. One approach that is used solve this try instead associate (or even network) $\Sigma_{\Pi}$ consisting all those bipartitions $\{A,X-A\}$ with $A$ part some partition in $\Pi$. The rational behind leaf can be uniquely represented by induced its edges. Motivated considerations, given $\Sigma$ $X$, paper we introduce and study $P(\Sigma)$ multisets $\Sigma_{\Pi}=\Sigma$. More specifically, characterize when non-empty, also identify are maximum minimum size. We show it NP-complete decide non-empty case an arbitrary $X$. Ultimately, hope gaining better understanding mapping takes system $\Sigma_{\Pi}$, will obtain new insights into use median networks and, more generally, split-networks visualize sets partitions.