Euclidean quotients of finite metric spaces

被引：42

作者：

Mendel, M

Naor, A

机构：

[1] Microsoft Res, Redmond, WA 98052 USA

[2] Hebrew Univ Jerusalem, Sch Engn & Comp Sci, Jerusalem, Israel

来源：

ADVANCES IN MATHEMATICS | 2004年 / 189卷 / 02期

关键词：

D O I：

10.1016/j.aim.2003.12.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M and alpha greater than or equal to 1, what is the largest quotient of (a subset of) M which well embeds into Hilbert space. We obtain asymptotically tight bounds for these questions, and prove that they exhibit phase transitions. We also study the analogous problem for embeddings into l(p), and the particular case of the hypercube. (C) 2004 Elsevier Inc. All rights reserved.

引用

页码：451 / 494

页数：44

共 25 条

[1] UNIFORM EMBEDDINGS OF METRIC-SPACES AND OF BANACH-SPACES INTO HILBERT-SPACES [J].