L1 embedding of a cycle

Question

During a lecture I've been in the following questions was thrown in to the air:

Let $G=C_n$ be the cycle graph over $n$ vertices, with positive weights on the edges.

find a function $f:G\rightarrow \mathbb{R}^m$ (for some $m\in \mathbb N^+$) such that $\text{dis}_G(v_1,v_2) = \text{dis}_{L_1}(f(v_1),f(v_2))$

where $\text{dis}_G$ is the shortest path metric over G

and $\text{dis}_{L_1}$ is the $L_1$ metric over $ \mathbb{R}^m$

I've tried to prove it for some time but failed to do so. I have reasons to believe this is possible but if someone could give a counterexample I would enjoy seeing that too

Answer 1

EDIT: There are errors in the following argument. See my second post for an actual proof of this fact. I think it's worthwhile to leave this answer up, though, since it has some useful ideas.

Okay, so unless I've made a mistake, I think I can prove this. Before looking at cycles, I want to consider another class of metrics. In particular, given a set $V$ (which we will always think of as our universe) and a subset $S$, define the metric $\mu_S(x,y)=\mathbf{1}[|S\cap\{x,y\}|=1]$ if $x\neq y$ and $\mu_S(x,x)=0$. It is not difficult to see that $\mu_S$ embeds into $L_1^1$ (I'm abusing notation and using $L_1^n$ to denote $\mathbb{R}^n$ equipped with the $L_1$ metric) by defining $f:V\to L_1^1$ by $f(x)=0$ if $x\notin S$ and $f(x)=1$ if $x\in S$. Furthermore, given any set $\mathcal{S}\subseteq 2^V$, the metric $\mu=\sum_{S\in\mathcal{S}}c_S\mu_S$ embeds into $L_1^{|\mathcal{S}|}$ for any positive $c_S$'s.

Now, fix any weights on the edges of $C_n$ (with vertex set $V$) and let $\mu$ be the metric induced by these weights. I claim that $\mu=\sum_{S\in\mathcal{S}}c_S\mu_{S}$ for some $\mathcal{S}\subseteq 2^V$ and some positive $c_S$'s. We will do this by induction on $n$. Firstly, given a $2$-cycle with edge weights $w_{12}$ and $w_{21}$, we have $\mu=\min\{w_{12},w_{21}\}\mu_{\{1\}}$, so we're good there. We want to consider $C_n$ as directed, so let $d(x,y)$ denote the clockwise distance; hence $\mu(x,y)=\min\{d(x,y),d(y,x)\}$.

Now, we will build a cyclic interval $S$ of $V$ by first saying that $k\in S'$ if $d(1,k)\leq d(k,1)$. Let $k=\max S'$ and build $S$ by saying $j\in S$ if $d(j,k)\leq d(k,j)$. Now, fix any $x,y\in V$; I claim that either $d(x,y)=d(y,x)$ or the shortest path between $x$ and $y$ crosses between $S$ and $V\setminus S$ at most once. Indeed, if not, then either $x<y\in S$, in which case we know that $d(x,y)\leq d(y,x)$ and this shortest path lies fully inside of $S$, or $x,y\in V\setminus S$, in which case if $x<y$ (cyclically) then $d(y,\max S)>d(\max S,y)$ and $d(\min S,x)>d(x,\min S)$ (where $\max$ and $\min$ are taken cyclically), but this means that $d(x,y)<d(y,x)$, so the shortest path between $x$ and $y$ lies in $V\setminus S$.

Hang in there, we're almost done!

Without loss, we may suppose that $S=\{1,\dots,k\}$ for some $k< n$ and also suppose that $w:=w_{n,1}\leq w_{k,k+1}$ and consider the metric $\mu- w\cdot\mu_S$. We proved above that every shortest path crosses between $S$ and $V\setminus S$ at most once, so $\mu- w\cdot\mu_S$ is precisely the metric for the weighted cycle $C_n'$ where $w_{x,x+1}'=w_{x,x+1}$ if $x\notin\{k,n\}$ and $w_{x,x+1}'=w_{x,x+1}-w$ if $x\in\{k,n\}$. However, notice that $w'_{n,1}=0$ by the definition of $w$, so we may identify the vertices $n$ and $1$. Thus, really we have a metric for $C_{n-1}$ or $C_{n-2}$. Thus, by induction, there is some $\mathcal{T}\subseteq 2^V$ and $c_T>0$ with $\mu-w\cdot\mu_{S}=\sum_{T\in\mathcal{T}}c_T\mu_T$, so $\mu=\sum_{T\in\mathcal{T}}c_T\mu_T+w\cdot\mu_{S}$. Done!

In particular, this shows that for any weighting on $C_n$, we can always embed the corresponding metric into $L_1^{2^n}$.

Please let me know if I've made any mistakes. This is a really nice problem!

Also, I was curious if all metrics coming from graphs+weightings are embeddable into $L_1^k$ for some $k$, but this is not true. For instance, it is not hard to convince yourself that $K_{2,3}$ with all unit weights cannot be embedded into any $L_1^k$. I'm curious if there is a nice classification of all graphs $G$ for which any weighting gives rise to a metric which can be embedded in $L_1^k$ for some $k$.

Answer 2

Ignore my previous answer. There are flaws, but I think it's worthwhile leaving it up as it has some valuable ideas. I can now prove that you can embed the metric from a weighted cycle into $L_1$. We will do this in multiple parts.

Firstly for a fixed $n$, consider a path around the hypercube which is $$P_n=(0,0,\dots,0)\to(1,0,\dots,0)\to(1,1,0,\dots,0)\to\dots\to(1,1,\dots,1)\to(0,1,\dots,1)\to\dots\to(0,0,\dots,0,1)\to(0,0,\dots,0).$$ Notice that if I give you two points $p,q\in P_n$, then the $L_1$-distance between $p$ and $q$ is exactly the distance between $p$ and $q$ in $P_n$ (the shortest distance, not necessarily following the arrows in $P_n$). Now, suppose we're given a cycle $C_n$ with all edge weights $w_e\in\mathbb{Z}^+$ and $w=\sum_e w_e$ is even. We will do the following: Let $p_1=0$ and $p_i=p_{i-1}+w_{i-1,i}$, so $p_i$ is the weight of the path in $C_n$ from vertex $1$ to vertex $i$ going clockwise. Label the vectors on $P_{w/2}$ starting with $(0,0,\dots,0)$ having label $0$ and going around and map vertex $i$ of $C_n$ to the $p_i$'th vector in $P_{w/2}$. By the previous comment, this is an $L_1$-embedding.

Now, if each $w_e$ is rational, we can find some $M$ for which $Mw_e\in\mathbb{Z}$ for all $e$ and $M\sum_e w_e$ is even, so we can use the previous embedding and then scale.

Now for the irrationals.

For this, we need a compactness argument using the metrics $\mu_S$ from my previous post. Recall that if $V$ is a finite set and $S\subseteq V$, then $\mu_S(x,x)=0$ and $\mu_S(x,y)=\mathbf{1}[|S\cap\{x,y\}|=1]$ if $x\neq y$. It is not difficult to prove that any metric of the form $\mu=\sum_{S\subseteq V}c_S\mu_S$ is $L_1$-embeddable for any $c_S\geq 0$. I claim that, in fact, if $V$ is any finite subset of $L_1^n$, then there are constants $c_S\geq 0$ for which $\Vert x-y\Vert_1=\sum_{S\subseteq V}c_s\mu_S(x,y)$ for every $x,y\in V$. @OferMagen has pointed out that this is known, but I can't find a reference, so I'll provide a proof. First, if $V\subseteq L_1^1$, then write the points $V=\{v_1\leq v_2\leq\dots\leq v_k\}$. Then we have $$ \Vert x-y\Vert_1=\sum_{r=1}^k\Vert v_{r+1}-v_r\Vert_1\mu_{\{v_1,\dots,v_r\}}(x,y),$$ for any $x,y\in V$. For a general $V\subseteq L_1^n$, we can do this construction in each coordinate direction $e_i$ for $i\in[n]$ since the $L_1$ metric is additive over the coordinates. Thus, if $\mu$ is a metric on a finite set $V$, then $\mu$ is $L_1$-embeddable if and only if $\mu=\sum_{S\subseteq V}c_S\mu_S$ for some constants $c_S\geq 0$.

Now, suppose that some edge-weights are irrational, so suppose $w_e^{(k)}$ are rational numbers with $w_e^{(k)}\to w_e$. Let $\mu^{(k)}$ be the metric induced by the weights $w_e^{(k)}$. By above, we know that each $\mu^{(k)}$ is $L_1$-embeddable, so we can write $\mu^{(k)}=\sum_{S\subseteq V}c_S^{(k)}\mu_S$. By compactness, without loss, we may suppose $c_S^{(k)}\to c_S$. Finally, since $\mu^{(k)}\to\mu$, we must have $\mu=\sum_{S\subseteq V}c_S\mu_S$, so $\mu$ must be $L_1$-embeddable.

Answer 3

What do you mean by: "Now, suppose that some edge-weights are irrational, so suppose w_e^{(k)} are rational numbers with w_e^{(k)}\to w_e. "?