Hyperconvexity and tight-span theory for diversities (Q1759374): Difference between revisions

The authors define a diversity to be a pair \((X,\delta)\) where \(X\) is a set and \(\delta\) is a function from the finite subsets of \(X\) to \(\mathbb R\) satisfying the two axioms: (D1) \(\delta(A)\geq 0\) and \(\delta(A)=0\) if and only if \(| A | \leq 1.\) (D2) If \(B\not=\emptyset\) then \(\delta(A\cup C)\leq \delta(A\cup B)+\delta(B\cup C)\) for all finite \(A,B,C\subseteq X.\) Diversities are related to (symmetric) metric spaces: Given such a standard metric space \((X,d),\) the function \(\delta=\text{diam}_d\) defined by \(\delta(A)=\text{diam}_d(A)=\max\{d(a,a'):a,a'\in A\}\) for finite \(A\subseteq X\), and with \(\text{diam}_d(\emptyset)=0,\) determines the diameter diversity for \((X,d).\) On the other hand, given a diversity \((X,\delta),\) then \(d(x,y)=\delta(\{x,y\})\) yields the metric \(d\) induced on \(X\) by \((X,\delta).\) By looking at diversities instead of metrics, additional information may be incorporated into some data analysis. The authors develop the basic theory of tight spans and hyperconvexity on diversities. For instance it is shown that diversity tight spans, like metric tight spans, are injective, and yield the injective envelope in the category of diversities. It is also verified that when the diversity equals the diameter diversity of a metric space, the diversity tight span is isomorphic to the diameter diversity of the metric tight span. As an application the authors study the tight span of a so-called phylogenetic diversity, and prove that the tight span of a phylogenetic diversity recovers the underlying tree in the same way that the tight span of an additive metric recovers its underlying tree. (That theory is developed for metric-trees.) They also apply their theory to the classical Steiner tree problem. Results due to Dress and Krüger are extended to Steiner trees based on diversities, leading to tighter bounds for the classical Steiner tree problem. In general the paper demonstrates that the fruitful theory associated with metric tight spans and metric hyperconvexity extends to a possibly even more versatile theory of tight spans and hyperconvexity on diversities.