2004/06/30 by Yair Bartal, Nathan Linial, Manor Mendel +1 · 2 citations
Computer Science · Mathematics · #Advanced Topology and Set Theory #Banach space #Cardinality (data modeling) #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Distortion (music) #Hilbert space #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Metric (unit) #Metric space #Pure mathematics #Ramsey theory #Space (punctuation) #Subspace topology #Type (biology) #Upper and lower bounds #cs.DS #math.MG #msc:05C12 #msc:05C55 #msc:52C45 #msc:54E40
paper · pdf · doi:10.4007/annals.2005.162.643
published as Ann. of Math. (2) 162 (2005), no. 2, 643--709 · 67 pages, published version
openalex publication_date 2005/09/01 · arxiv created 2007/06/21 · arxiv updated 2012/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 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.