Combinatorial Structure of Finite Metric Spaces

Each metric space is associated to its fundamental polytope, also called Kantorovich-Rubinstein polytope. The combinatorics of a metric space is defined in terms of combinatorial properties of its fundamental polytope. We introduce this topic and present several recently obtained results.

We examine the case of metric spaces induced by weighted graphs. In particular, we show that metric space induced by weighted trees can have only one type of combinatorial structure, namely that of the cross-polytope ◇_{[n]}.

Our main focus is on the class of generic metric spaces. In particular, we show that the cyclohedron, i.e., Bott-Taubes polytope, W_n arises as the polar dual of a Kantorovich-Rubinstein polytope KR(ρ), where ρ is an explicitly described quasi-metric satisfying strict triangle inequality. From a broader perspective, this phenomenon illustrates the relationship between a nestohedron Δ_{^F} associated to a building set {^F}, and its non-simple deformation Δ_F, where F is an irredundant or tight basis of {^F}. Among the consequences are a new proof of a recent result of Gordon and Petrov about f-vectors of generic Kantorovich-Rubinstein polytopes, and an extension of a theorem of Gelfand, Graev, and Postnikov, about triangulations of the type-A, positive root polytopes.