Skip to main content
1 of 2
Matt Noonan
  • 4k
  • 3
  • 33
  • 28

Representability of finite metric spaces

There have been a couple questions recently regarding metric spaces, which got me thinking a bit about representation theorems for finite metric spaces.

Suppose $X$ is a set equipped with a metric $d$. I had initially assumed there must be an $n$ such that $X$ embeds isometrically into $\mathbb{R}^n$, but the following example shows that this doesn't quite work:

Take for $X$ the vertex set of any graph, and let $d(x,y)$ be the length (in steps) of the shortest path connecting $x$ to $y$. Then for a minimal path connecting $x$ to $y$, the path must map to a straight line in $\mathbb{R}^n$. This is because $\mathbb{R}^n$ has the property that equality in the triangle inequality implies colinearity.

So take a graph such that $x$ and $y$ have $d(x,y) \geq 2$ and two minimal paths between them; a plain old square will do the trick. The two minimal paths must each get mapped to the same line in $\mathbb{R}^n$, so the map cannot be an isometry (nor even an embedding, for that matter).

This gives us one obstruction to representability: a finite metric space cannot be representable unless it satisfies the property $d(x,y) = d(x,z) + d(z,y) \wedge d(x,y) = d(x,z') + d(z',y) \wedge d(x,z) = d(x,z') \implies z = z'$.

Question #1: Is this the only obstruction to representability?

In a slightly different direction, you could get around the problem above by trying to represent the finite metric spaces on some surface instead of $\mathbb{R}^n$. This at least works in the graph case by replacing the points with little discs and the edges with very fat ribbons of length 1. Then compactifying the whole thing should give a surface into which the graph embeds isometrically. This suggests the answer to

Question #2a: Does every finite metric space have a representation on a surface?

is yes, as long as the answer to

Question #2b: Does every finite metric space have a global scaling which embeds $\epsilon$-isometrically into a graph?

is also yes. The $\epsilon$ is to take care of finite metric spaces with irrational distances.

Of course, there is also the important

Question #0: Is there some standard place I should have looked for all this?

Matt Noonan
  • 4k
  • 3
  • 33
  • 28