Embedding the cycle metric into a real vector space with metric $l_{p}$

47 Views Asked by At

Why is it impossible to embed the cycle metric over $n$ points $x_{1}, x_{2},...,x_{n}$ where the distance is defined as the shortest path ($d(x_{i}, x_{j}) = min(|j-i|; n + i - j; n + j - i) $) into any real vector space equipped with the $l_{p}$ metric without incurring any nontrivial distortion?

1

There are 1 best solutions below

0
On

For $n=3$ this is still possible, we can map the cycle points as vertices of a equilateral triangle with side $1$. But for $n>3$ the situation changes dramatically. In this case for any embedding of the cycle into real normed space for any its three consecutive vertices the middle should be embedded as a midpoint of a segment between the other two embedded points. This imply that all embedded points are collinear, a distance between each two conecutive points is $1$, and each embedded point has exactly two neighbors at distance one. But the last property fails for the points which are embedded at the brinks.