On metric Ramsey-type phenomena (Q2496968): Difference between revisions

This paper deals with extremely interesting nonlinear analogues of Dvoretzky's Theorem (originally for finite-dimensional Banach spaces) in the context of metric spaces, with a point of view that may also let us see the results as part of combinatorial Ramsey theory: given a finite metric space on \(n\) points, the problem is to identify the subspace of largest cardinality which can be embedded with a given (metric) distortion in Hilbert space. Hilbert space plays either the central role it has in Banach space theory, or can be seen as a ``highly-structured'' substructure in the spirit of Ramsey theory, the latter being, as the authors put it, the study of how ``large systems necessarily contain large, highly structured sub-systems''. This paper is long, deep and highly technical, so let us merely state here what the authors themselves announce in their introduction: they provide nearly tight upper and lower bounds on the cardinality of the ``Hilbertian'' subspaces in terms of \(n\) and the desired distortion. The main theorem states that for any \(\varepsilon>0\), every \(n\) point metric space contains a subset of size at least \(n^{1-\varepsilon}\) which is embeddable in Hilbert space with \(O(\log(1/\varepsilon)/\varepsilon)\) distortion. The bound on the distortion is tight up to the \(\log(1/\varepsilon)\) factor.