When I discovered hypermetric inequalities (an attempt to characterize -embeddable metrics), there turned out to be applications in the geometry of numbers. I studied the generalization to quasi-metrics, hoping for similar applications.
1. Definition and examples
A quasi-metric is a nonnegative function on such that
- , , , .
Example 1 Minkowski gauge of a compact convex set containing the origin.
Example 2 Sorgenfrei quasi-metric on is if , otherwise.
Example 3 Path quasi-metric of a directed graph.
Variant: [Chartrand, Erwin, Raines, Zhang 1999] define the strong quasi-metric in a digraph.
Example 4 Thurston quasi-metric between Riemannian manifolds.
1.1. Weightable quasi-semi-metrics
Say is weightable if there exists function such that
A quasi-semi-metric is weightable iff its satisfies a cyclic inequality…
Any finite quasi-semi-metric is the shortest path quasi-semi-metric of a digraph. It is weighted iff the graph is na bidirectional tree.
Example 5 The hitting time quasi-metric is the expected number if step of random walk needed to go from to .
It is weightable. It is proportional to the effective resistance metric.
Example 6 Oriented multicut metrics.
An oriented multicut of a set is a partition with an ordering of the pieces. There is a corresponding quasi-semi-metric. It is weightable iff there are only two pieces.
1.2. Semantics of computation
Say a poset , having a smallest element, is dspo if each directed subset has a supremum. A Scott domain is a dspo where all sets are directed with supremum equal to , and each consistent has a supremum in .
Example 7 . All words over a finite alphabet, with prefix order. All vague real numbers (i.e. closed intervals with reverse inclusion order).
All weighted quasi-semi-metrics on points form a polyhedral cone of dimension .
-derivation is Gromov product with vertex , i.e.
[Makarychev, Makarychev]: Most weightable quasi-semi-metrics arise as Gromov product of some semi-metric.
Example 8 The -derivation of the -distance is called -quasi-metric and denoted by .
1.5. Generalization of -metrics
Theorem 1 A quasi-semi-metric embeds into iff it belongs to the cone generated by oriented cuts.
Note that an oriented cut quasi-semi-metric is the -derivation of the corresponding cut metric. It is weightable.
Example 9 embeds in if .
is the square of a -quasi-semi-metric.
Theorem 2 A quasi-semi-metric embeds into iff it is the quasi-semi-metric of subsets of some measure space.
What does not work: Hypercube does not have a natural quasi-semi-metric. Indeed, there are a lot of possible orientations on the hypercube. This is a whole subject in itself.
1.6. Hypermetric inequalities
Hypermetric inequalities describe certain facets of the cut cone.
Given integers which sum up to , metric satisfies
Say a metric is a hypermetric if it satisfies all these inequalities.
Given a lattice, and a maximum ball which contains no nonzero vectors of the lattice. It may contain lattice points on its boundary. Such a set is called a constellation. The square of Euclidean metric restricted to a constellation satisfies all hypermetric inequality. Conversely, every hypermetric is isometric to some constellation [Assouad-Deza].
This has a partial generalization to quasi-metrics. As yet, it looks rather ugly.