2010/08/31 by Sven Herrmann, Vincent Moulton · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Cardinality (data modeling) #Combinatorics #Computer science #Corollary #Decomposition #Discrete mathematics #Mathematics #Polynomial and algebraic computation #Set (abstract data type) #Topological and Geometric Data Analysis #math.CO #math.MG #msc:05C05 #msc:51K05 #msc:52B11 #msc:92D15 #q-bio.QM
paper · pdf · doi:10.1016/j.aam.2012.01.003
published in Advances in Applied Mathematics 49(1), 39-56 (Elsevier BV) · 22 pages, 4 figures
openalex publication_date 2012/03/17 · arxiv created 2012/06/06 · arxiv updated 2014/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A k-dissimilarity map on a finite set X is a function D : X \choose k → R assigning a real value to each subset of X with cardinality k, k ≥ 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 kth 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 Bandelt and Dress [Adv. Math. 92 (1992), 47-105], 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 Pachter and Speyer [Appl. Math. Lett. 17 (2004), 615-621] for recovering k-dissimilarity maps from trees.