The split decomposition of a k-dissimilarity map

DOI10.1016/J.AAM.2012.01.003zbMATH Open1244.05057arXiv1008.1703OpenAlexW2030506407MaRDI QIDQ432491FDOQ432491

Authors: Sven Herrmann, Vincent Moulton 

Publication date: 4 July 2012

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: A k-dissimilarity map on a finite set X is a function D : X choose k ightarrow 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 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.

Full work available at URL: https://arxiv.org/abs/1008.1703

Recommendations

• Recognizing treelike \(k\)-dissimilarities
• On graphlike \(k\)-dissimilarity vectors
• A geometric study of the split decomposition
• A tropical interpretation of \(m\)-dissimilarity maps
• The Buneman index via polyhedral split decomposition

zbMATH Keywords

distancemetric spacepolytopesplit decompositiondissimilarity map

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) (n)-dimensional polytopes (52B11)

Cites Work

• Title not available (Why is that?)
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Lectures on Polytopes
• Triangulations. Structures for algorithms and applications
• A tropical interpretation of \(m\)-dissimilarity maps
• A canonical decomposition theory for metrics on a finite set
• Two dimensional quantification based on the measure of dissimilarity among three elements
• Triadic distance models: axiomatization and least squares representation
• \(n\)-semimetrics
• Reconstructing trees from subtree weights.
• Three-way distances
• Six theorems about injective metric spaces
• \(n\)-way metrics
• Recognizing treelike \(k\)-dissimilarities
• Geometry of cuts and metrics
• Splitting Polytopes
• The tropical Grassmannian
• Dissimilarity vectors of trees are contained in the tropical Grassmannian
• How to draw tropical planes
• Tropical Linear Spaces
• On the relation between weighted trees and tropical Grassmannians
• Combinatorial calculation of characteristic classes

Cited In (4)

• Recognizing treelike \(k\)-dissimilarities
• Parity splits by triple point distances in \(X\)-trees
• The 22 minimal dichotomy decompositions of the \(K_5\)-distance
• Trees, tight-spans and point configurations

This page was built for publication: The split decomposition of a \(k\)-dissimilarity map

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q432491)