On metric Ramsey-type phenomena
From MaRDI portal
Publication:2496968
DOI10.1145/780542.780610zbMath1114.46007arXivmath/0406353OpenAlexW2571257893WikidataQ29392377 ScholiaQ29392377MaRDI QIDQ2496968
Assaf Naor, Nathan Linial, Manor Mendel, Yair Bartal
Publication date: 26 July 2006
Published in: Annals of Mathematics. Second Series, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)
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-epsilon} which is embeddable in Hilbert space with O(frac{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.
Full work available at URL: https://arxiv.org/abs/math/0406353
Analysis of algorithms and problem complexity (68Q25) Metric spaces, metrizability (54E35) Local theory of Banach spaces (46B07) Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10)
Related Items (57)
On quantitative sphere equivalence and extrapolation phenomenon ⋮ Dvoretzky-type theorem for Ahlfors regular spaces ⋮ Limitations to Fréchet's metric embedding method ⋮ METRIC INEQUALITIES ⋮ Markov type and threshold embeddings ⋮ Markov type constants, flat tori and Wasserstein spaces ⋮ Covering metric spaces by few trees ⋮ Lossless Prioritized Embeddings ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem ⋮ Reliable Spanners for Metric Spaces ⋮ An introduction to the Ribe program ⋮ Maximum gradient embeddings and monotone clustering ⋮ Unnamed Item ⋮ Ultrametric subsets with large Hausdorff dimension ⋮ Low dimensional embeddings of ultrametrics. ⋮ The \(k\)-server problem ⋮ Advances in metric embedding theory ⋮ On the quantitative quasi-isometry problem: transport of Poincaré inequalities and different types of quasi-isometric distortion growth ⋮ Comparison of Metric Spectral Gaps ⋮ COMPUTING THE DISTANCE DISTRIBUTION OF SYSTEMATIC NONLINEAR CODES ⋮ Parametrized Metrical Task Systems ⋮ Fréchet embeddings of negative type metrics ⋮ Nonlinear spectral calculus and super-expanders ⋮ The \(k\)-resource problem in uniform metric spaces ⋮ \(L_p\) compression, traveling salesmen, and stable walks. ⋮ Quantitative geometry ⋮ Ultrametric skeletons ⋮ Euclidean quotients of finite metric spaces ⋮ Online computation with advice ⋮ Nonembeddability theorems via Fourier analysis ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ Snowflake universality of Wasserstein spaces ⋮ Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces ⋮ The wreath product of $\mathbb {Z}$ with $\mathbb {Z}$ has Hilbert compression exponent $\frac {2}{3}$ ⋮ Approximate Moore graphs are good expanders ⋮ Ramsey partitions and proximity data structures ⋮ Banach space actions and \(L^2\)-spectral gap ⋮ SPACES OF SMALL METRIC COTYPE ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ Chasing convex bodies optimally ⋮ Low-distortion embeddings of infinite metric spaces into the real line ⋮ An average John theorem ⋮ Some recollections on early work with Jan Pelant ⋮ Local embeddings of metric spaces ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Covering Metric Spaces by Few Trees ⋮ Poincaré inequalities, embeddings, and wild groups ⋮ FINITE FLAT SPACES ⋮ Markov Type of Alexandrov Spaces of Non‐Negative Curvature Shin‐Ichi Ohta ⋮ Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ The legacy of Jean Bourgain in geometric functional analysis ⋮ Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ The black-box complexity of nearest-neighbor search ⋮ Relative expanders
This page was built for publication: On metric Ramsey-type phenomena
