Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders

✍ Scribed by Nathan Linial; Avner Magen

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 139 KB
• Volume: 79
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2000.1953

✦ Synopsis

Embeddings of finite metric spaces into Euclidean space have been studied in several contexts: The local theory of Banach spaces, the design of approximation algorithms, and graph theory. The emphasis is usually on embeddings with the least possible distortion. That is, one seeks an embedding that minimizes the bi-Lipschitz constant of the mapping. This question has also been asked for embeddings into other normed spaces. However, when the host space 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 can therefore be solved in polynomial time). So far, this elegant statement of the problem has not been applied to any interesting explicit instances. Here we employ this method and examine two families of graphs: (i) products of cycles, and (ii) constant-degree expander graphs. Our results in (i) extend a 30-year-old result of P. Enflo (1969, Ark. Mat. 8, 103 105) on the cube. Our results in (ii) provide an alternative proof to the fact that there are n-point metric spaces whose Euclidean distortion is 0(log n). Furthermore, we show that metrics in the class (ii) are 0(log n) far from the class l 2 2 , namely, the square of the metrics realizable in l 2 . This is a well studied class which contains all l 1 metrics (and therefore also all l 2 metrics). Some of our methods may well apply to more general instances where semidefinite programming is used to estimate Euclidean distortions. Specifically, we develop a method for proving the optimality of an embedding. This idea is useful in those cases where it is possible to guess an optimal embedding.