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.)

  • $\begingroup$ Try a 3-vertex example with two zero-weight edges, of course. Of course this counterexample works for any metric, of course. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.