Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders

Embeddings of finite metric spaces into Euclidean space have been studied i n several contexts: The local theory of Banach spaces, the design of approx imation algorithms, and graph theory. The emphasis is usually on embeddings with the least possible distortion. That is, one seeks an embedding that m inimizes the bi-Lipschitz constant of the mapping. This question has also b een asked for embeddings into other normed spaces. However, when the host s pace is l(2), more can be said: The problem of finding an optimal embedding into l(2) can be formulated as a semidefinite program (and call therefore be solved in polynomial time). So far, this elegant statement of the proble m has not been applied to any interesting explicit instances. Here we emplo y this method and examine two families of graphs: (i) products of cycles, a nd (ii) constant-degree expander graphs. Our results in (i) extend a 30-yea r-old result of P. Enflo (1969, Ark. Mat. 8, 103-105) on the cube. Our resu lts in (ii) provide an alternative proof to the fact that there are n-point metric spaces whose Euclidean distortion is Omega(log n). Furthermore, we show that metrics in the class (ii) are Omega(log n) far from the class l(2 )(2),namely, the square of the metrics realizable in l(2). This is a well s tudied class which containss all l(1) metrics (and therefore also all l(2) metrics). Some of our methods may well apply to more general instances wher e semidefinite programming is used to estimate Euclidean distortions. Speci fically, we develop a method for proving the optimality of an embedding. Th is idea is useful in those cases where it is possible to guess an optimal e mbedding. (C) 2000 Academic Press.