On scale embeddings of graphs into hypercubes (Q1209728)

Suppose \(G_ 1=(V_ 1,E_ 1)\) and \(G_ 2=(V_ 2,E_ 2)\) are finite graphs. A mapping \(\varphi:G_ 1\to G_ 2\) is a scale embedding if there is an integer \(\lambda\) with \(d_ 2(\varphi(v)\), \(\varphi(v'))\leq\lambda d_ 1(v,v')\) for any pair \(v\), \(v'\) in \(V_ 1\), where \(d_ 1\) is the path metric in \(V_ 1\), and \(d_ 2\) is the path metric in \(V_ 2\). A scale embedding with \(\lambda=1\) is an isometric embedding. The paper provides three main results. (1) If \(G\) has a scale embedding into the \(n\)-cube with odd \(\lambda\), then it has an isometric embedding into the \([n/\lambda]\)-cube. For the next two results, we define the graph \(H\) to be a product of graphs \(H_ 1\), \(H_ 2,\dots,H_ r\), where each \(H_ j\) is isomorphic either to a complete graph, a cocktail party graph or a half cube. (2) If \(G\) has a scale embedding into a hypercube, there is a graph \(H\) as above and an isometric embedding \(\varphi\) of \(G\) into \(H\). (3) If \(\psi\) is a scale embedding of \(G\) into a hypercube, then there is a scale embedding \(T:G\to H\) such that \(\psi=T\varphi\), where \(\varphi\) and \(H\) are as in (2). A graph is scale embeddable in a hypercube if and only if it can be isometrically embedded in the metric space \(l_ 1\). Thus, the author is able to draw a number of corollaries concerning \(l_ 1\) embeddability from the main result.