Embeddings of 3 point metric spaces into ultra-metric spaces with distortion 2

Question

I need to show that every 3 point metric space has an embedding into an ultra-metric space with distortion 2.

And then to show such an example.

How would I go about it?

Thank you.

Edit:
Distortion is defined as following:
An embedding $f:(X,d_X)\rightarrow(Y,d_Y)$ has distortion $\alpha$ if there is a constant $c>0$ such that $\forall u,v\in X:d_X(u,v)\leq c \cdot d_Y(f(x),f(y))\leq \alpha \cdot d_X(u,v)$

score 2 · Accepted Answer · answered Jul 01 '13 at 12:17

2

Let the three-point metric space be $\langle X,d_X\rangle$, where $X=\{x_0,x_1,x_2\}$. We can label the three points in such a way that $d_X(x_0,x_1)\le d_X(x_1,x_2)\le d_X(x_0,x_2)$, and the triangle inequality ensures that $d_X(x_0,x_2)\le d_X(x_0,x_1)+d_X(x_1,x_2)\le 2d_X(x_1,x_2)$.

Let $\langle Y,d_Y\rangle$ be the ultrametric space, and let $Y=\{y_0,y_1,y_2\}$, where $y_k=f(x_k)$ for $k=0,1,2$. Let $d_Y(y_0,y_1)=d_X(x_0,x_1)$ and $d_Y(y_1,y_2)=d_X(x_1,x_2)$.

Bearing in mind that $d_Y$ is an ultrametric, what must $d_Y(y_0,y_2)$ be?
Check that the embedding $f:X\to Y:x_k\mapsto y_k$ has distortion $2$.

answered Jul 01 '13 at 12:17

Brian M. Scott

616,228

Thank you, much clearer now! – user83155 Jul 01 '13 at 13:49
@user83155: You’re welcome! – Brian M. Scott Jul 01 '13 at 19:18
@BrianM.Scott -I still can't figure out how to show that $$d_X \left( x_0 , x_2 \right) \leqslant 2 \cdot d_Y \left( y_0 , y_2 \right)$$ (Assuming that our constant $c$ equals 2). – Amihai Zivan Jul 03 '13 at 20:55
@Amihai: $d_Y(y_0,y_2)$ has to be the same as $d_Y(y_1,y_2)$, so $$d_X(x_0,x_2)\le2d_X(x_1,x_2)=2d_Y(y_0,y_2);.$$ – Brian M. Scott Jul 03 '13 at 20:58
And that's because it's an ultra-metric space? - many thanks! – Amihai Zivan Jul 03 '13 at 21:04
@Amihai: Yes, that’s why the two longer distances have to be equal. It’s not hard to prove that in an ultrametric space every triangle is isosceles, with two longer sides and a shorter one, or equilateral. – Brian M. Scott Jul 03 '13 at 21:06
Isn't it for an ultra metric space $X$: $$\forall x, y, z \in X:\text{ }d(x,y)\leqslant \max{d(x,z),d(z,y)}$$ and not equality?? – Amihai Zivan Jul 03 '13 at 21:08
@Amihai: Yes, it is. And that’s enough to give the result about triangles. Suppose that the sides are $a\le b\le c$. Then we have $b\le c\le\max{a,b}=b$, so $b=c$. – Brian M. Scott Jul 03 '13 at 21:14
Yes, now I see (the obvious)... Thanks again! – Amihai Zivan Jul 03 '13 at 21:14
@Amihai: You’re welcome! – Brian M. Scott Jul 03 '13 at 21:21

Embeddings of 3 point metric spaces into ultra-metric spaces with distortion 2

1 Answers1