On metric Ramsey-type phenomena

• Autores: Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
• Localización: Annals of mathematics, ISSN 0003-486X, Vol. 162, Nº 2, 2005, págs. 643-709
• Idioma: inglés
• DOI: 10.4007/annals.2005.162.643
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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 n1-
    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.