Combinatorial invariants of finite metric spaces and the Wasserstein arrangement

2024/08/28 by Emanuele Delucchi, Delucchi, Emanuele, Lukas Kühne +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2408.15584

openalex publication_date 2024/08/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In 2010, Vershik proposed a new combinatorial invariant of metric spaces given by a class of polytopes that arise in the theory of optimal transport and are called ``Wasserstein polytopes'' or ``Kantorovich-Rubinstein polytopes'' in the literature. Answering a question posed by Vershik, we describe the stratification of the metric cone induced by the combinatorial type of these polytopes through a hyperplane arrangement. Moreover, we study its relationships with the stratification by combinatorial type of the injective hull (i.e., the tight span) and, in particular, with certain types of metrics arising in phylogenetic analysis. We also compute enumerative invariants in the case of metrics on up to six points.

Related

• Hausdorff and Wasserstein metrics on graphs and other structured data
• The polytopal structure of the tight-span of a totally split-decomposable metric
• Metrics on Permutation Families Defined by a Restriction Graph
• Balls, Segments, Convex Sets in Metric Spaces and Structures with Heredity
• Finite metric spaces--combinatorics, geometry and algorithms