Ultrametric subsets with large Hausdorff dimension (Q1949226)

The famous theorem by \textit{A. Dvoretzky} [Proc. Int. Symp. linear Spaces, Jerusalem 1960, 123--160 (1961; Zbl 0119.31803)] states that each large-dimensional normed space contains a nontrivially-large-dimensional linear subspace which is close to Euclidean. The study of nonlinear versions of the Dvoretzky theorem was initiated by \textit{J.~Bourgain, T. Figiel} and \textit{V. Milman} [Isr. J. Math. 55, 147--152 (1986; Zbl 0634.46008)], who started to study the following problem: given \(n\in\mathbb{N}\) and \(1<D<\infty\), 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\). Terence Tao (unpublished, 2006) suggested to seek metric versions of the Dvoretzky theorem in which normed spaces are replaced by metric spaces, the dimension by the Hausdorff dimension, and Euclidean (linear) subspaces by metric subspaces admitting a low-distortion embedding into a Euclidean space. The paper contains two nonlinear versions of the Dvoretzky theorem of this type, and even stronger in the following sense: in the positive parts of the theorems low-distortion embeddability into a Hilbert space is replaced by low-distortion embeddability into ultrametric spaces. Recall that an ultrametric space is a metric space in which every triple \(x,y,z\) satisfies \(\rho(x,y)\leq \max\{\rho(x,z),\rho(z,y)\}\). It is known [\textit{I. A. Vestfrid} and \textit{A. F. Timan}, Sov. Math., Dokl. 20, 485--486 (1979); translation from Dokl. Akad. Nauk SSSR 246, 528--530 (1979; Zbl 0423.54007)] that any separable ultrametric space admits an isometric embedding into a Hilbert space. We state only one of the nonlinear versions of the Dvoretzky theorem proved in the paper (the other is devoted to the case of ``small distortions''). In the statement below \(\dim_H\) denotes the Hausdorff dimension. Theorem 1.4. There exists a universal constant \(C\in (0,\infty)\) such that for every \(\varepsilon\in (0,1)\) and \(\alpha\in (0,\infty)\), every compact metric space \(X\) with \(\dim_H(X)\geq \alpha\) has a closed subset \(S\subseteq X\) with \(\dim_H(S)\geq (1-\varepsilon)\alpha\) that embeds with distortion \(C/\varepsilon\) into an ultrametric space. In the reverse direction, there is a universal constant \(c>0\) such that for every \(\alpha>0\) there exists a compact metric space \(X_\alpha\) with \(\dim_H(X_\alpha)= \alpha\) such that if \(S\subseteq X\) satisfies \(\dim_H(S)\geq (1-\varepsilon)\alpha\), then \(S\) incurs distortion at least \(c/\varepsilon\) in any embedding into a Hilbert space. The spaces \(X_\alpha\) of Theorem 1.4 are constructed using expander graphs. The first statement of Theorem 1.4 is derived from the following result which also implies nonlinear versions of the Dvoretzky theorem for finite metric spaces. Theorem 1.5. For every \(\varepsilon\in (0,1)\) there exists \(c_\varepsilon\in (0,\infty)\) with the following property. Every metric measure space \((X,d,\mu)\) has a closed subset \(S\subseteq X\) such that \((S,d)\) embeds into an ultrametric space with distortion \(9/\varepsilon\), and for every \(\{x_i\}_{i\in I}\subseteq X\) and \(\{r_i\}_{i\in I}\subseteq [0,\infty)\) such that the balls \(\{B(x_i,r_i)\}_{i\in I}\) cover \(S\), i.e., \[ \bigcup_{i\in I} B(x_i,r_i)\supseteq S, \] we have \[ \sum_{i\in I} \mu(B(x_i,c_\varepsilon r_i))^{1-\varepsilon}\geq \mu(X)^{1-\varepsilon}. \] The paper contains also a discussion of applications of Theorems 1.4 and 1.5 which were discovered after the first version of the present paper was posted on \texttt{arXiv}. These include applications to Urbański's problem by \textit{T. Keleti, A. Máthé,} and \textit{O. Zindulka} [Int. Math. Res. Not. 2014, No. 2, 289--302 (2014; Zbl 1296.28008)] and to Talagrand's majorizing measures theorem by \textit{M. Mendel} and \textit{A. Naor} [Proc. Natl. Acad. Sci. USA 110, No. 48, 19256--19262 (2013; Zbl 1307.46013)].