On metric Ramsey-type phenomena

• 成果类型: Article
• 署名作者: Bartal, Y; Linial, N; Mendel, M; Naor, A
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2005.162.643
• 发表日期: 2005
• 页码: 643-709
• 关键词: banach-spaces; hilbert-space; THEOREM; bounds; EMBEDDINGS; distortion; expanders; dimension; server; graph

摘要

The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space on n points, we seek its subspace of largest cardinality which can be embedded with a given distortion in Hilbert space. We provide nearly tight upper and lower bounds on the cardinality of this subspace in terms of n and the desired distortion. Our main theorem states that for any epsilon > 0, every n point metric space contains a subset of size at least n(1-epsilon) which is embeddable in Hilbert space with O (log(1/epsilon)/epsilon) distortion. The bound on the distortion is tight up to the log(1/epsilon) factor. We further include a comprehensive study of various other aspects of this problem.