Trees, Taxonomy, and Strongly Compatible Multi-state Characters

Dress A, Moulton V, Steel M. Trees, Taxonomy, and Strongly Compatible Multi-state Characters. Advances in Applied Mathematics. 1997;19(1):1-30.Given a family of binary characters defined on a set X, a problem arising in biological and linguistic classification is to decide whether there is a tree structure on X which is ''compatible'' with this family. A fundamental result from hierarchical clustering theory states that there exists a tree structure on X for such a family if and only if any two of the characters are compatible. In this paper, we prove a generalization of this result. Namely, we show that given a family of multi-state characters on X which we denote by chi, there exists a tree structure on X, called an (X,chi)-tree, which is ''compatible'' with chi if and only if any two of the characters are strongly compatible. To prove this result, we introduce the concept of block systems, set theoretical structures which arise naturally from, amongst other things, block graphs, and the related concepts of block interval systems and Delta-systems. (C) 1997 Academic Press