Diversities and the Geometry of Hypergraphs

Abstract

The embedding of finite metrics in ${\ell }_1$ has become a fundamental tool for both combinatorial optimization and large-scale data analysis. One important application is to network flow problems in which there is close relation between max-flow min-cut theorems and the minimal distortion embeddings of metrics into ${\ell }_1$. Here we show that this theory can be generalized considerably to encompass Steiner tree packing problems in both graphs and hypergraphs. Instead of the theory of ${\ell }_1$ metrics and minimal distortion embeddings, the parallel is the theory of diversities recently introduced by Bryant and Tupper, and the corresponding theory of ${\ell }_1$ diversities and embeddings which we develop here.

19 pages, no figures. This version: further small corrections

References in corpus (2)

• Hyperconvexity and Tight Span Theory for Diversities
• Diversities and Conformities