Subtree distances, tight spans and diversities

We characterize when a set of distances d(x, y) between elements in a set X have a subtree representation, a real tree T and a collection {S_x}_x∈X of subtrees of T such that d(x, y) equals the length of the shortest path in T from a point in S_x to a point in S_y for all x, y ∈ X. The characterization was first established for finite X by Hirai (2006) using a tight span construction defined for distance spaces, metric spaces without the triangle inequality. To extend Hirai’s result beyond finite X we establish fundamental results of tight span theory for general distance spaces, including the surprising observation that the tight span of a distance space is hyperconvex. We apply the results to obtain the first characterization of when a diversity – a generalization of a metric space which assigns values to all finite subsets of X, not just to pairs – has a tight span which is tree-like