Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem (Q1932671)

Given \(n\in\mathbb{N}\) and \(1<D<\infty\), to estimate the largest integer \(k=k(n,D)\) such that each \(n\)-element metric space contains a \(k\)-element subspace which is embeddable into a Hilbert space with distortion \(\leq D\), is called the nonlinear Dvoretzky problem. The first results on this problem were obtained by \textit{J. Bourgain, T. Figiel} and \textit{V. Milman} [Isr. J. Math. 55, 147-152 (1986; Zbl 0634.46008)] who proved that \(k(n,D)\geq C(D)\log n\) and showed that \(k(n,D)=O(\log n)\) if \(D\) is sufficiently close to \(1\). \textit{Y. Bartal} et al. [Ann. Math. (2) 162, No. 2, 643--709 (2005; Zbl 1114.46007)] discovered that for \(D>2\) one can find much larger ``Hilbertian'' subsets, namely there exist \(b(D),B(D)\in(0,1)\) such that \(n^{1-b(D)}\leq k(n,D)\leq n^{1-B(D)}\). \textit{M. Mendel} and \textit{A. Naor} [J. Eur. Math. Soc. (JEMS) 9, No. 2, 253--275 (2007; Zbl 1122.68043)] found a substantially simpler proof of the lower bound \(k(n,D) \geq n^{1-b(D)}\). However, their approach, which is based on ``Ramsey partitions'', works only for sufficiently large \(D\). The authors of the present paper describe the reasons (on p.~493) why Ramsey partitions cannot give the result for \(D<3\). The main purpose of the authors is to introduce a different technique which is called ``a randomized iterative fragmentation procedure'' and to use it for an elegant proof of \(k(n,D) \geq n^{1-b(D)}\) with the best known estimate for \(b(D)\) for all \(D\in (2,\infty)\).