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.