If $X$ is a metric space with cardinality $n$, there is an isometric embedding of $X$ into $(\mathbb R^n,\|\cdot\|_\infty)$. I take this result from here. I would like to ask if the following related statement is correct.
Let $X$ be a metric space with cardinality $n$. There is $d \in \mathbb N$ such that $X$ can be embedded isometrically into $\mathbb R^d$ equipped with the standard Euclidean metric $|\cdot|$.
Best Answer
The short answer is no and the long answer is also no.
What I mean is that if we want a strict isometry then we can't do this. However, suppose we relax strict isometry to requiring only say a constant (independent of $n$) distortion. Then the answer is still no!
However, there is some hope, we can exactly characterize which metrics can be embedded. If you take a look at Section 2 of https://openreview.net/pdf?id=0jHeZ7-ehGr there are three different characterization of metrics that can be isometrically embedded into Euclidean space.
In terms of relaxing the isometry condition. Theorem 3.5.3 in https://kam.mff.cuni.cz/~matousek/ba-a4.pdf shows that there are certain family of metrics (on $n$ points) whose embedding requires $\Omega(\log n)$ distortion.
Here is a simple counter example for the isometry part. Consider star graph with $W$ in the center and connected to $X,Y,Z$ so that the distance from $W$ to $X,Y,Z$ is $1$ and the distances between any distinct two from $X,Y,Z$ is $2$.
Now $Y,W,Z$ must lie on a line (equality for the triangle inequality). Similarly $X,W,Y$ and $X,W,Z$ have to also be co-linear. Hence all 4 points must be co-linear. Hence we can't get an isometric embedding ($X,Y,Z$ can't be co-linear).