On metric Ramsey-type phenomena.

*(English)*Zbl 1114.46007This 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.

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.

Reviewer: Vania Mascioni (Muncie)