On metric Ramsey-type phenomena

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Research output: Contribution to journalReview article

65 Scopus citations

Abstract

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 ε > 0, every n point metric space contains a subset of size at least n 1-ε which is embeddable in Hilbert space with O ( log(1/ε)/ε) distortion. The bound on the distortion is tight up to the log(1/ε) factor. We further include a comprehensive study of various other aspects of this problem.

Original languageEnglish (US)
Pages (from-to)643-709
Number of pages67
JournalAnnals of Mathematics
Volume162
Issue number2
DOIs
StatePublished - Sep 1 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'On metric Ramsey-type phenomena'. Together they form a unique fingerprint.

  • Cite this