Trees, tight-spans and point configurations

DOI10.1016/J.DISC.2012.05.003zbMATH Open1301.54042arXiv1104.1538OpenAlexW1971754301MaRDI QIDQ442355FDOQ442355

Authors: Sven Herrmann, Vincent Moulton 

Publication date: 10 August 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Tight-spans of metrics were first introduced by Isbell in 1964 and rediscovered and studied by others, most notably by Dress, who gave them this name. Subsequently, it was found that tight-spans could be defined for more general maps, such as directed metrics and distances, and more recently for diversities. In this paper, we show that all of these tight-spans as well as some related constructions can be defined in terms of point configurations. This provides a useful way in which to study these objects in a unified and systematic way. We also show that by using point configurations we can recover results concerning one-dimensional tight-spans for all of the maps we consider, as well as extend these and other results to more general maps such as symmetric and unsymmetric maps.

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

Recommendations

• Dimensions of tight spans
• On tight spans for directed distances
• Hyperconvexity and tight-span theory for diversities
• Metric stability of trees and tight spans
• Characterization of the distance between subtrees of a tree by the associated tight span

zbMATH Keywords

metricinjective hulldiversitydirected distancepoint configurationpolytopal subdivisiontight-span

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) (n)-dimensional polytopes (52B11) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Metric spaces, metrizability (54E35)

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
• Tropical convexity
• Triangulations. Structures for algorithms and applications
• A canonical decomposition theory for metrics on a finite set
• Six theorems about injective metric spaces
• An algorithm for computing cutpoints in finite metric spaces
• Basic phylogenetic combinatorics.
• Splitting Polytopes
• A New Approach to the Server Problem
• Classification of six-point metrics
• The distance matrix of a graph and its tree realization
• \(T\)-theory: An overview
• Hereditarily optimal realizations of consistent metrics
• The split decomposition of a \(k\)-dissimilarity map
• Hyperconvexity and tight-span theory for diversities
• On tight spans for directed distances
• Tree representations of non-symmetric group-valued proximities
• Characterization of the distance between subtrees of a tree by the associated tight span
• A geometric study of the split decomposition
• Title not available (Why is that?)
• Generosity Helps or an 11-Competitive Algorithm for Three Servers
• Splits and tight spans of convex polytopes
• On the facets of the secondary polytope

Cited In (9)

• Quasi-metric trees and \(q\)-hyperconvex hulls
• The tight span of an antipodal metric space. II: Geometrical properties
• Fixed topology Steiner trees and spanning forests
• Geometric tree graphs of points in convex position
• The Buneman index via polyhedral split decomposition
• On tight spans for directed distances
• Dimensions of tight spans
• Metric stability of trees and tight spans
• Quasi-metric tree in \(T_0\)-quasi-metric spaces

This page was built for publication: Trees, tight-spans and point configurations

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