## Notes of Michel Deza’s talk

Quasi-metrics

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.