Diversities and the Geometry of Hypergraphs

The embedding of finite metrics in ℓ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 ℓ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 ℓ1 metrics and minimal distortion embeddings, the parallel is the theory of diversities recently introduced by Bryant and Tupper, and the corresponding theory of ℓ1 diversities and embeddings which we develop here.