M.Sc Student M.Sc Thesis Dmitriyuk Alon Volume Respecting Embeddings of Finite Metric Spaces Department of Mathematics PROFESSOR EMERITUS Yehoram Gordon (Deceased) PROFESSOR EMERITUS Yoav Benyamini

Abstract

Feige introduced in 1998 the concept of volume for finite metric spaces (for k=2 this concept coincides with the metric). He also introduced the class of k-volume respecting embeddings into Euclidean space (which generalizes the metric distortion for k=2).

In this thesis we give a systematic presentation of the known results on volumes and volume respecting embeddings.

In his paper, Feige gave the upper estimate O((logn(logn+klogk))1/2)  on the optimal k-volume distortion of an embedding of a metric space with n points. We present the details of his proof as well as the upper bound of O(logn(logD)1/2) where D is the quotient of the diameter of the metric space and the minimal distance in the metric space (This is a generalization of a theorem by Gupta who proved it for ordinary graphs). We also show (following Krauthgamer, Linial and Magen) that there are metric spaces (expander graphs) for which the k-volume distortion is at least of the order of magnitude logn (Recently, Krauthgamer, Lee, Mendel and Naor showed that logn is, indeed, the correct order of magnitude for the k-volume distortion).

Another aspect of the problem is the dimension of the target space. Magen proved in 2002 that for every n-point subset A of Euclidean space and k between 2 and n, there is an embedding into O(klogn)-dimensional Euclidean space which almost preserves the (k-1)-dimensional volume of the convex hull of every subset B of A with k elements. We present a different proof which also gives the slightly better dimension estimate of O(klog(n/k)). This generalizes the well known result by Johnson and Lindenstrauss on the reduction of dimension which almost preserves distances.