Tree-tree matrices and other combinatorial problems from taxonomy (Q1911840)

Much of the literature on mathematical taxonomy and clustering has focused on the question of `abstracting' from a given dissimilarity a suitable (classification) tree. A central question is ``given a metric on a space \(X\), which is the metric corresponding to a hierarchical classification scheme, which best approximates the given one?'' It may be that trees are not really as appropriate for classification and information-finding purposes as their dominance in the literature implies. It may be that trees are a relic of the use of hard copy: they are just about the only classification scheme which can be more or less decently printed. A bipartite graph \(A\) between two sets \(D\) and \(T\) may be used to transfer (classification) information from one of the two sets to the other. \(A\) defines, via Hamming distance, metrics on both \(T\) and \(D\). It is shown that if both spaces are trivial \(A\) comes from an Hadamard matrix or a BIBD.