# L1 - embeddability of metrics supported on the Hypercube

I am quite new to the area of metric embeddings so this question might turn out to be extremely easy.

Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge of the boolean hypercube has a non negative distance associated with it and the metric is defined by the length of the shortest path according to the distance function between any two vertices. Can we put upper bounds/lower bounds on the distortion when we embed such a metric into $l_1$ ?

Any references would be highly appreciated.

Think of the hypercube as a graph $G$. Allowing arbitrary edge lengths implies that you can use edge lengths $0$ and $\infty$ to get a minor of $G$ on which you can put edge lengths. The hypercube has sufficiently large expansion that it contains, as a minor, a clique of size about $\sqrt{N}$ (ignoring polylog factors) where $N$ is the number of nodes of the hypercube. This implies you can basically have any finite metric on a set of size about $\sqrt{N}$ supported on the hyper cube. Thus the worst-case lower bounds will apply so you will get an $\Omega(\log N)$ lower bound.
In general there are all kinds of lower bounds for embedding an arbitrary metric on the hypercube into $\ell_1$. For example, the edit distance cannot be embedded with better than $\log n$ distortion. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over all metrics on the hypercube.
• I am sorry but I couldnt get your above comment. So when I say edges I mean the standard edges of the Hypercube, the ones that go between pairs of vertices that are at Hamming Distance 1. Now if we want to 'support' the edit distance then for any pair that is at Hamming Distance 1 since the edit distance is also 1. the edge between them will have to be given a weight $\geq 1$. Now all edges have weight $\geq 1$ therefore distance between any pair has to be greater than the Hamming distance and hence Edit distance cannot be supported. Could you please point out the flaw in my reasoning? – NAg Apr 10 '14 at 14:13
• I am sorry when I made the previous comment I didnt realize that you were saying that we can support an edit distance metric on $\sim \sqrt{N}$ vertices(as Chandra clarified) on the a cube of $n$ vertices, i thought you had suggested supporting an edit distance on $n$ points. That was naive of me. Thanks for the answers – NAg Apr 10 '14 at 17:42