On metric Ramsey-type phenomena

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 epsilon>0, every n point metric space contains a subset of size at least n^{1-ε} which is embeddable in Hilbert space with O(\frac{\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.

67 pages, published version

References in corpus (2)

• On some low distortion metric Ramsey problems
• Finite metric spaces--combinatorics, geometry and algorithms

Cited by in corpus (39)

• Fast Construction of Nets in Low Dimensional Metrics, and Their Applications
• Metric Cotype
• Nonlinear spectral calculus and super-expanders
• Ramsey partitions and proximity data structures
• Ramsey-type theorems for metric spaces with applications to online problems
• On some low distortion metric Ramsey problems
• Poincaré inequalities, embeddings, and wild groups
• Euclidean quotients of finite metric spaces
• $L_p$ compression, traveling salesmen, and stable walks
• Expanders with respect to Hadamard spaces and random graphs
• The wreath product of Z with Z has Hilbert compression exponent 2/3
• Relative expanders
• Ultrametric subsets with large Hausdorff dimension
• Ultrametric skeletons
• Banach space actions and $L^2$-spectral gap
• Pure entropic regularization for metrical task systems
• Maximum gradient embeddings and monotone clustering
• Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces
• Markov type of Alexandrov spaces of nonnegative curvature
• Limitations to Frechet's Metric Embedding Method
• Prioritized Metric Structures and Embedding
• An introduction to the Ribe program
• An average John theorem
• Advances in Metric Ramsey Theory and its Applications
• Snowflake universality of Wasserstein spaces
• Sphere equivalence, Banach expanders, and extrapolation
• Embedding proper ultrametric spaces into ${\ell }_p$ and its application to nonlinear Dvoretzky's theorem
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• A note on dichotomies for metric transforms
• Metric $X_p$ inequalities
• Metric spaces admitting low-distortion embeddings into all $n$-dimensional Banach spaces
• A Competitive Ratio Approximation Scheme for the k-Server Problem in Fixed Finite Metrics
• Dvoretzky-type theorem for Ahlfors regular spaces
• Reliable Spanners for Metric Spaces
• Markov type and threshold embeddings
• Two infinite versions of nonlinear Dvoretzky's theorem
• On Clusters that are Separated but Large
• Nonembeddability theorems via Fourier analysis
• Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion