Given a finite metric space $(X, d)$ and a positive integer $n$, what is the ‘best’ way to test whether $X$ embeds isometrically in $\mathbb R^{n - 1}$? Note that this is more general than the question in the title, which is what first occurred to me. (Although I haven't thought about it very much, this is probably automatically possible for $n$ at least the cardinality of $X$, and there are examples (like the indiscrete metric, or, I think, any ultrametric space) where the bound is sharp.)

The meaning of ‘best’ is intentionally ambiguous. For $n = 2$, here’s a solution that may not be optimal: find the maximal distance between two points, and check that it is achieved for a unique pair of points. Call these $x_0$ and $x_1$. There is a unique map $X \to \mathbb R$ sending each $x \in X$ to $d(x_0, x)$, and an isometric embedding exists if and only if this particular map is one.

EDIT: A related question about deducing planarity from 5-point embeddings is a beautiful result, but not quite what I want; it just reduces the question to: how do I run this test if $n = \lvert X\rvert + 4$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.