Summary: A \(k\)-dissimilarity map on a finite set \(X\) is a function \(D:{X \choose k} \to \mathbb R\) assigning a real value to each subset of \(X\) with cardinality \(k, k\geq 2\). Such functions, also sometimes known as \(k\)-way dissimilarities, \(k\)-way distances, or \(k\)-semimetrics, are of interest in many areas of mathematics, computer science and classification theory, especially 2-dissimilarity maps (or distances) which are a generalisation of metrics.
In this paper, we show how regular subdivisions of the \(k\)th hypersimplex can be used to obtain a canonical decomposition of a \(k\)-dissimilarity map into the sum of simpler \(k\)-dissimilarity maps arising from bipartitions or splits of \(X\).
In the special case \(k=2\), this is nothing other than the well-known split decomposition of a distance due to H.-J. Bandelt and A. W. M. Dress [“A canonical decomposition theory for metrics on a finite set”, Adv. Math. 92, No. 1, 47–105 (1992; Zbl 0789.54036)], a decomposition that is commonly to construct phylogenetic trees and networks.
Furthermore, we characterise those sets of splits that may occur in the resulting decompositions of \(k\)-dissimilarity maps. As a corollary, we also give a new proof of a theorem of L. Pachter and D. E. Speyer [“Reconstructing trees from subtree weights”, Appl. Math. Lett. 17, No. 6, 615–621 (2004; Zbl 1055.05033)] for recovering \(k\)-dissimilarity maps from trees.