|M.Sc Student||Alon Dmitriyuk|
|Subject||Volume Respecting Embeddings of Finite Metric Spaces|
|Department||Department of Mathematics||Supervisors||Professor Emeritus Gordon Yehoram|
|Professor Emeritus Benyamini Yoav|
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.