Notes of Michel Deza’s talk


When I discovered hypermetric inequalities (an attempt to characterize {L_1}-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 {X\times} such that

  1. {q(x,y)=0 \Leftrightarrow x=y};
  2. {\forall\,x}, {y}, {z}, {q(x,z)\leq q(x,y)+q(y,z)}.

Example 1 Minkowski gauge of a compact convex set containing the origin.

Example 2 Sorgenfrei quasi-metric on {{\mathbb R}} is {q(,y)=y-x} if {y\geq x}, {1} 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 {q} is weightable if there exists function {w} such that

\displaystyle  \begin{array}{rcl}  q(x,y)-q(y,x)=w(y)-w(x). \end{array}

A quasi-semi-metric {q} 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 {x} to {y}.

It is weightable. It is proportional to the effective resistance metric.

Example 6 Oriented multicut metrics.

An oriented multicut of a set {X} 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 {X}, having a smallest element, is dspo if each directed subset has a supremum. A Scott domain is a dspo where all sets {\{a\in X^C \,;\, a\leq x\}} are directed with supremum equal to {x}, and each consistent {A\subset X} has a supremum in {X}.

Example 7 {2^{{\mathbb N}}}. All words over a finite alphabet, with prefix order. All vague real numbers (i.e. closed intervals with reverse inclusion order).

1.3. Cones

All weighted quasi-semi-metrics on {n} points form a polyhedral cone {WQSMET_n} of dimension {\frac{n(n+1)}{2}}.

1.4. Derivation

{z}-derivation is Gromov product with vertex {z}, i.e.

\displaystyle  \begin{array}{rcl}  q_{z}(x,y)=\frac{1}{2}(d(x,z)+d(y,z)-d(x,y)). \end{array}

[Makarychev, Makarychev]: Most weightable quasi-semi-metrics arise as Gromov product of some semi-metric.

Example 8 The {0}-derivation of the {\ell_p^n}-distance is called {\ell_p}-quasi-metric and denoted by {\ell_p^{or}}.

1.5. Generalization of {L_1}-metrics

Theorem 1 A quasi-semi-metric embeds into {\ell_1^{or}} iff it belongs to the cone {OCUT_n} generated by oriented cuts.

Note that an oriented cut quasi-semi-metric is the {z}-derivation of the corresponding cut metric. It is weightable.

Example 9 {\ell_p^{or}} embeds in {\ell_1^{or}} if {p<2}.

{\ell_1^{or}} is the square of a {\ell_2^{or}}-quasi-semi-metric.

Theorem 2 A quasi-semi-metric embeds into {\ell_1^{or}} 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 {b_i} which sum up to {1}, {L_1} metric satisfies

\displaystyle  \begin{array}{rcl}  \sum_{ij}d_{ij}b_i b_j \leq 0. \end{array}

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.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s