Mapping Edge Sets to Splits in Trees: the Path Index and Parsimony

摘要

Associated to any finite tree, there are simple vector spaces over $$ {user2{mathbb{Z}}}_{2} $$ and linear transformations between them that relate collections of edge-disjoint paths, sets of leaves of even cardinality, and bipartitions of the leaf set. In this paper, we use this connection to introduce and study an apparently new integer-valued invariant, the ‘path index’ of a tree. In the case of trivalent (or ‘binary’) trees, this index has an interesting recursive description that allows its easy calculation implying in particular that the path index of such a tree never exceeds one quarter of the number of its leaves and coincides with that number exclusively for the (unique!) trivalent tree with four leaves. We then show how our algebraic perspective has some other uses—for example, it relates to Hadamard conjugation first described by Mike Hendy, and it provides a way to study a combinatorial optimization problem considered in phylogenetics called the small maximum parsimony problem.