Combinatorial Structure of Finite Metric Spaces




Journal Title

Journal ISSN

Volume Title



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.



Metric spaces, Polytopes, Polyhedra, Combinatorial analysis


©2018 The Author. Digital access to this material is made possible by the Eugene McDermott Library. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.