Topological k-metrics
share
Metric spaces (X, d) are ubiquitous objects in mathematics and computer science that allow for capturing (pairwise) distance relationships d(x, y) between points x, y ∈ X. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "k-wise distance relationships" d(x_1, …, x_k) among points x_1, …, x_k ∈ X for k > 2. To that end, Gähler (Math. Nachr., 1963) (and perhaps others even earlier) defined k-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality d(x_1, x_2) ≤ d(x_1, y) + d(y, x_2) to the "simplex inequality" d(x_1, …, x_k) ≤∑_i=1^k d(x_1, …, x_i-1, y, x_i+1, …, x_k). (The definition holds for any fixed k ≥ 2, and a 2-metric space is just a (standard) metric space.) In this work, we introduce strong k-metric spaces, k-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary k-metrics, which generalize ℓ_p metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain k-metrics, which generalize shortest path metrics (and capture all strong k-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fréchet embedding (isometric embedding into ℓ_∞) and isometric embedding of all tree metrics into ℓ_1. We also study relationships between families of (strong) k-metrics, and show that natural quantities, like simplex volume, are strong k-metrics.
READ FULL TEXT