# Can a cycle be represented by L1 metric?

Let G be a graph that forms a cycle on $n$ vertices, with non-negative weights on the edges. Can you give each vertex v a vector $\mathbb{R}^m$ (for some $m\in \mathbb N^+$) such that the L1 distance (taxicab distance) between two vectors is the same as the distance between them in $G$?

Prove for a general circular graph or give a counter example with proof.

(I was told it is true so I have a good reason to think it is but I can't prove it.)

• Try a 3-vertex example with two zero-weight edges, of course. Of course this counterexample works for any metric, of course. – j_random_hacker Jun 13 '18 at 14:36

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.

Now, for a finite set $$V$$ and a subset $$S\subseteq V$$, we define the metric $$\mu_S$$ on $$V$$ by $$\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$$. 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.

• Does your proof work for the graph with weights, $AB\to 1$, $BC\to 1$ and $CA\to3$? – Apass.Jack Nov 10 '18 at 1:46
• The metric on the graph is the shortest distance metric. Hence $CA \to 2$ in your example. – Yuval Filmus Nov 10 '18 at 18:38
• Thanks Yuval. Yes, In a weighted graph, the distance between two vertices is the shortest path in terms of weights, not edges. – munchhausen Nov 11 '18 at 14:37