A universal threshold for geometric embeddings of trees Thanks: 2020 Mathematics Subject Classification : 05C05. Thanks: Key words : geometrical embeddings, geometric graphs, metric embeddings, trees. Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov and Konstantinos Tyros Abstract . A graph G = ( V , E ) G=(V,E) is geometrically embeddable into a normed space X X when there is a mapping ζ : V → X \zeta\colon V\to X such that ‖ ζ ⁡ ( v ) − ζ ⁡ ( w ) ‖ X ⩽ 1 \|\zeta(v)-\zeta(w)\|_{X}\leqslant 1 if and only if { v , w } ∈ E \{v,w\}\in E , for all distinct v , w ∈ V v,w\in V . Our result is the following universal threshold for the embeddability of trees. Let Δ ⩾ 3 \Delta\geqslant 3 , and let N N be sufficiently large in terms of Δ \Delta . Every N N –vertex tree of maximal degree at most Δ \Delta is embeddable into any normed space of dimension at least 64 ​ log ⁡ N log ⁡ log ⁡ N 64\,\frac{\log N}{\log\log N} , and complete trees are non-embeddable into any normed space of dimension less than 1 2 ​ log ⁡ N log ⁡ log ⁡ N \frac{1}{2}\,\frac{\log N}{\log\log N} . In striking contrast, spectral expanders and random graphs are known to be non-embeddable in sublogarithmic dimension. Our result is based on a randomized embedding whose analysis utilizes the recent breakthroughs on Bourgain’s slicing problem. 1. Introduction Given a normed space X and a graph G=(V,E) , a map \zeta\colon V\to X is a geometrical embedding of G into X if E=\big\{\{v,w\}\subseteq V\colon\|\zeta(v)-\zeta(w)\|_{X}\leqslant 1\big\}. Say that G is non-embeddable into X if no such embedding exists. Note that the mapping \zeta exists if and only if G is isomorphic to an intersection graph in X generated by parallel translates of the unit ball B_{X} . The problem of identifying geometrically embeddable graphs has attracted significant attention, especially in the Euclidean setting. It was proved in [ FM88 ] (see, also, [ RRS89 ] and [ RRS92 ] ) that every N –vertex graph of maximal degree at most \Delta admits a geometrical embedding into a Euclidean space of dimension C\Delta^{2}\log N , where C>0 is a universal constant. On the other hand, the Poincaré inequality implies that any spectral expander graph is non-embeddable into Euclidean space of sublogarithmic dimension [ AT25 ] . More generally, spectral expanders also do not embed into any spaces of sublogarithmic dimension satisfying a so-called nonlinear Poincaré inequality (see, for example, [ Na14 , MN14 , Esk22 , ADTT24 ] for a discussion of such inequalities). The smallest m such that a graph G can be embedded into an m –dimensional Euclidean space is called the sphericity of G , and denoted by {\rm Sph}(G) . The aforementioned results then imply that, suppressing dependence on \Delta , the sphericity of every N –vertex expander graph is of order \Theta(\log N) . We refer to [ MP93 , Section 2] and [ BL05 , Section 3] for a review of results on sphericity of various families of graphs. In the non-Euclidean setting, it was recently shown in [ AT25 ] that with high probability, a random \Delta –regular graph on N vertices cannot be geometrically embedded into any normed space of dimension o(\log N) . It remains an interesting open question whether this dimension bound is asymptotically optimal across all normed spaces. The purpose of this note is to study geometrical embeddings of trees into arbitrary normed spaces. The setting of trees is fundamentally different from embedding random graphs despite the fact that sparse random graphs are locally tree-like, i.e., have few short cycles. As an illustration, in [ FM86 ] it is shown that the complete rooted binary tree T on N vertices admits a geometrical embedding into \ell_{2} of dimension at most C\frac{\log N}{\log\log N} . (Recall that, in contrast, a random 3 –regular graph on N vertices does not embed geometrically into a Euclidean space of dimension o(\log N) .) On the other hand, a slight adaptation of a volumetric argument from the same paper [ FM86 ] (which we reproduce in Section 4 for the reader’s convenience) yields that T is not geometrically embeddable into any normed space of dimension less than c\frac{\log N}{\log\log N} , for a universal constant c>0 . It is therefore natural to ask if the “transition window” \Theta\big(\frac{\log N}{\log\log N}\big) for complete binary N\text{--vertex} trees is universal across all norms. We completely resolve this problem and, moreover, provide embedding results for arbitrary bounded degree trees. Theorem 1.1 (Universal threshold for embedding of trees) . There exist absolute positive constants \alpha_{0}<\alpha_{1} , and for every integer \Delta\geqslant 3 a positive integer N_{0}=N_{0}(\Delta) depending only on \Delta with the following property. Let X be a finite-dimensional normed space, and let N\geqslant N_{0} be an integer. (A) If \dim(X)\leqslant\alpha_{0}\,\frac{\log N}{\log\log N} , then there exists a tree T on N vertices with maximum degree at most \Delta that is not geometrically embeddable into X . (B) On the other hand, if \dim(X)\geqslant\alpha_{1}\,\frac{\log N}{\log\log N} , then every tree T on N vertices with maximum degree at most \Delta is geometrically embeddable into X . Remark 1.2 . The proof of Theorem 1.1 yields the estimate \frac{1}{2}\leqslant\alpha_{0}<\alpha_{1}\leqslant 64 . Let us discuss the result in the context of intersection graphs. Given a collection of parallel translates \{x_{i}+K\colon i\in I\} of a convex body K in \mathbb{R}^{m} , the intersection graph is formed by placing an edge between i and j for all pairs of translates x_{i}+K and x_{j}+K that have a nonempty intersection. Our result implies that for any centrally-symmetric convex body K , every bounded degree N –vertex tree can be realized as an intersection graph in an \big\lceil\alpha_{1}\,\frac{\log N}{\log\log N}\big\rceil –dimensional vector space, using translates of K . Corollary 1.3 . Let \Delta\geqslant 3 be a positive integer, and let \alpha_{1} and N_{0} be as in Theorem 1.1 . Also let N\geqslant N_{0} be an integer, let T be a tree on N vertices with maximum degree at most \Delta , and let K be any centrally-symmetric convex body in a Euclidean space of dimension \big\lceil\alpha_{1}\,\frac{\log N}{\log\log N}\big\rceil . Then there exists an intersection graph for translates of K which is isometric to T . Remark 1.4 . The geometric embedding \zeta\colon V(T)\to X obtained in the proof of part (B) of Theorem 1.1 is 2 -Lipschitz when the tree T is equipped with the shortest-part distance {\rm dist}_{T}(\cdot,\cdot) , and it satisfies \|\zeta(u)-\zeta(v)\|_{X}\gtrsim\sqrt[10]{{\rm dist}_{T}(u,v)} for all u,v\in V(T) . That is, the inverse of \zeta is \frac{1}{10}\text{-H\"{o}lder} . This should be compared with a well-known result of Bourgain [ Bou86 ] (see, also, [ Ma99 ] ) asserting that any embedding of the complete rooted binary tree on N vertices into a Hilbert space 1 1 1 In fact, binary trees do not embed with bounded bi-Lipschitz distortion into any super-reflexive spaces (e.g., all \ell_{p} spaces for 10 and C>0 with the following property. If \mathbf{U} is an isotropic random vector in \mathbb{R}^{m} with a log-concave 2 2 2 A function f\colon\mathbb{R}^{m}\to[0,\infty) is log-concave if the set K:=\{x\in\mathbb{R}^{m}\colon f(x)>0\} is convex and, additionally, the function \log f\colon K\to\mathbb{R} is concave. distribution, then (2.1) \mathbb{P}\Big(\big|\|\mathbf{U}\|_{2}-\sqrt{m}\big|\geqslant m^{\frac{1}{2}-\kappa}\Big)\leqslant C\exp\big(-m^{\kappa}\big). We will also need the following very recent result of Klartag and Lehec [ KL24b ] that yields an affirmative solution to the celebrated Bourgain’s slicing conjecture. Theorem 2.3 (Anticoncentration for log-concave measures via slicing) . There exists an absolute constant L>0 with the following property. If \mathbf{U} is an isotropic random vector in \mathbb{R}^{m} with a log-concave density f , then for any x\in\mathbb{R}^{m} , (2.2) f(x)\leqslant L^{m}. Remark 2.4 . Thin-shell estimates for log-concave distributions have been actively studied in the asymptotic geometric analysis literature, leading to strengthening of the result in [ Kl07 ] , as a consequence of the tremendous recent progress on the KLS conjecture and the aforementioned resolution of the slicing conjecture. We do not attempt to give here a thorough overview of the history of these problems, and refer instead to recent works [ Ch21 , KL24a , Gu24 , KL24b ] for further references. Our proof of the main result is not sensitive to the value of the constant \kappa in Theorem 2.2 . 2.4. Gaussian concentration We will need the following simple consequence of gaussian concentration for Lipschitz functions. Fact 2.5 . If \mathbf{G} is a random vector in \mathbb{R}^{m} with i.i.d. standard normal entries, then for any t>\sqrt{m} , (2.3) \mathbb{P}\big(\|\mathbf{G}\|_{2}>t\big)\leqslant 2\exp\Big(-\frac{(t-\sqrt{m})^{2}}{2}\Big). Proof. Notice that the map f\colon\mathbb{R}^{m}\to\mathbb{R} defined by f(x)=\|x\|_{2} , is 1 -Lipschitz, and it satisfies \mathbb{E}\big[f(\mathbf{G})\big]\leqslant\sqrt{m} . Using these observations, the result follows from the standard gaussian concentration for Lipschitz functions (see, e.g., [ Le01 ] ). ∎ 2.5. John’s theorem Recall that if X and Y are two normed spaces of the same dimension, then their Banach–Mazur distance is defined by d_{\mathrm{BM}}(X,Y):=\inf\big\{\|T\|\cdot\|T^{-1}\|\colon T\colon X\to Y\text{ is an isomorphism}\big\}. Also recall that, by a classical result due to John (see, e.g., [ JL01 ] ), we have d_{\mathrm{BM}}(X,\ell_{2}^{m})\leqslant\sqrt{m} for any m -dimensional normed space X . We will use this estimate in the following form. Fact 2.6 . Let X=(\mathbb{R}^{m},\|\cdot\|_{X}) be an m -dimensional normed space. Then there exist vectors x_{1},\dots,x_{m}\in\mathbb{R}^{m} such that for any a_{1},\dots,a_{m}\in\mathbb{R} , (2.4) \Big(\sum_{i=1}^{m}a_{i}^{2}\Big)^{\frac{1}{2}}\leqslant\Big\|\sum_{i=1}^{m}a_{i}x_{i}\Big\|_{X}\leqslant\sqrt{m}\Big(\sum_{i=1}^{m}a_{i}^{2}\Big)^{\frac{1}{2}}. 2.6. Lovász local lemma The last result we will need is the so-called asymmetric version of Lovász local lemma (see, e.g., [ AS16 ] ). Lemma 2.7 (Asymmetric Lovász local lemma) . Let G be a graph, and let (A_{v})_{v\in V(G)} be a collection of measurable events in some probability space such that for every v\in V(G) , the event A_{v} is independent of the algebra generated by the events \big\{A_{u}\colon u\not\in N_{G}(v)\cup\{v\}\big\} . Assume that there exists h\colon V\to[0,1) such that for any v\in V(G) , (2.5) \mathbb{P}(A_{v})\leqslant h(v)\prod_{u\in N_{G}(v)}\big(1-h(u)\big). Then, (2.6) \mathbb{P}\Bigg(\bigcap_{v\in V(G)}A_{v}^{\complement}\Bigg)\geqslant\prod_{v\in V(G)}\big(1-h(v)\big). 3. Preparatory lemmas In this section we shall present three preparatory lemmas that are used in the proof of Theorem 1.1 . We start with the following volumetric estimate. Lemma 3.1 . There exists an absolute constant C_{B}>0 such that for any m -dimensional normed space X=(\mathbb{R}^{m},\|\cdot\|_{X}) in isotropic position, we have \lambda(B_{X})\leqslant C_{B}^{m} , where \lambda denotes the Lebesgue measure in \mathbb{R}^{m} . Proof. Let \mathbf{U} be a random vector uniformly distributed in B_{X} . Then \mathbf{U} is an isotropic, log-concave, random vector in \mathbb{R}^{m} with density function f:=\lambda(B_{X})^{-1}\mathbbm{1}_{B_{X}} . By Theorem 2.2 , there exists an absolute constant c>0 such that \frac{1}{2}\leqslant\mathbb{P}\big(\|\mathbf{U}\|_{2}\leqslant c\sqrt{m}\big)=\frac{\lambda\big(B_{X}\cap c\sqrt{m}\,B_{\ell^{m}_{2}}\big)}{\lambda(B_{X})}. Therefore, \lambda(B_{X})\leqslant 2\lambda\big(B_{X}\cap c\sqrt{m}\,B_{\ell^{m}_{2}}\big)\leqslant 2\,c^{m}\,\lambda\big(\sqrt{m}\,B_{\ell^{m}_{2}}\big)\leqslant 2\big(\sqrt{2c^{2}\pi e}\big)^{m}.\qed Lemma 3.2 . Let X=(\mathbb{R}^{m},\|\cdot\|_{X}) be a normed space in isotropic position, let k be a positive integer, and let 01 . Hence, by Theorem 2.2 and assuming that m_{1} is sufficiently large, we get that \lambda(\Gamma)\leqslant C\exp\big(-m^{\kappa}\big)\,\lambda(B_{X}). It follows immediately that, conditioned on any realization of \mathbf{Y}_{1},\dots,\mathbf{Y}_{k-1} , the probability that \sum_{i=1}^{k}\mathbf{Y}_{i} belongs to (1+\varepsilon)\Gamma , is bounded above by \frac{\lambda\big((1+\varepsilon)\Gamma\big)}{\lambda(B_{X})}\leqslant C(1+\varepsilon)^{m}\exp\big(-m^{\kappa}\big)\leqslant\frac{1}{2}\exp\big(-m^{\frac{\kappa}{2}}\big), where we have used again the fact that m_{1} can be taken sufficiently large. Combining the last estimate with ( 3.5 )–( 3.6 ), we get the result. ∎ 4. Proof of Theorem 1.1 As mentioned, part (A) of Theorem 1.1 is due to Frankl and Maehara [ FM86 ] . For the convenience of the reader, we recall their argument. We set (4.1) \alpha_{0}:=\frac{1}{2}. Fix an integer \Delta\geqslant 3 , and let N be an arbitrary positive integer that is sufficiently large in terms of \Delta . We define a tree T on N vertices with maximum degree \Delta as follows. There exists a root r_{T}\in V(T) such that, setting h_{0}:=\big\lceil\log\big((N-1)\frac{\Delta-2}{\Delta}+1\big)/\log(\Delta-1)\big\rceil , the following hold. \bullet For every v\in V(T) , we have \mathrm{dist}_{T}(r_{T},v)\leqslant h_{0} . \bullet For every v\in V(T) with \mathrm{dist}_{T}(r_{T},v)\leqslant h_{0}-2 , we have |N_{T}(v)|=\Delta . Notice, in particular, that if N=\frac{\Delta^{n+1}-1}{\Delta-1} , then T is just the \Delta -regular tree of height n . Let X=(\mathbb{R}^{m},\|\cdot\|_{X}) be a normed space for which there exists a geometric embedding \zeta\colon V(T)\to X . Since T is a bipartite graph (being a tree), there exists an independent set V_{0}\subseteq V(T) with |V_{0}|\geqslant\frac{N}{2} . Using the fact that every node of T has distance from r_{T} at most h_{0} , we see that (4.2) \bigcup_{v\in V_{0}}B_{X}\big(\zeta(v),1/2\big)\subseteq B_{X}\big(\zeta(r_{T}),h_{0}+1/2\big). On the other hand, since \zeta is a geometric embedding, for every u,v\in V_{0} with u\neq v we have that B_{X}\big(\zeta(u),1/2\big)\cap B_{X}\big(\zeta(v),1/2\big)=\emptyset . Thus, denoting by \lambda the Lebesgue measure in \mathbb{R}^{m} , by ( 4.2 ), \frac{N}{2}\lambda\big(B_{X}(0,1/2)\big)\leqslant\lambda\big(B_{X}(0,h_{0}+1/2)\big), which is easily seen to imply, if N is sufficiently large, that \dim(X)=m>\alpha_{0}\frac{\log N}{\log\log N} , as desired. We proceed to the proof of part (B) . We shall construct a random embedding of a given tree T on N vertices with maximum degree \Delta in the normed space X=(\mathbb{R}^{m},\|\cdot\|_{X}) , and we shall show that with positive probability this is a geometric embedding. To that end we start by setting (4.3) \alpha_{1}:=64,\ \ \ \ c_{1}:=\frac{1}{4},\ \ \ \ c_{2}:=\min\Big\{\frac{1}{4},\frac{\kappa}{4}\Big\}, where \kappa is as in Theorem 2.2 . The parameter N_{0} will be determined in the course of the proof. For notational convenience, we shall denote by V the vertex set of T , and by E its edge set. Clearly, we may assume that \dim(X)=m=\big\lceil\alpha_{1}\log N/\log\log N\big\rceil and that X is in isotropic position. 4.1. Construction of the random embedding Let (\mathbf{Y}_{e})_{e\in E} be a collection of i.i.d. random vectors uniformly distributed in B_{X} . Also let (\mathbf{g}_{i}^{e})_{i\in[m],e\in E} be a collection of i.i.d. scalar standard normal random variables that are independent of (\mathbf{Y}_{e})_{e\in E} . (As usual, [m]:=\{1,\dots,m\} denotes the discrete interval of length m .) Let x_{1},\ldots,x_{m}\in\mathbb{R}^{m} be as in Fact 2.6 , and define for every e\in E , (4.4) \mathbf{G}_{e}:=\sum_{i=1}^{m}\mathbf{g}_{i}^{e}\,x_{i}. Fix a distinguished vertex r_{T}\in V that we view as the root of T , and set (4.5) \delta:=\exp\Big(-\Big(\frac{1}{2}-\frac{c_{1}}{2}\Big)\log^{c_{2}}N\Big). We define the random embedding \boldsymbol{\zeta}\colon V\to X by \boldsymbol{\zeta}(v):=\Big(1-\frac{1}{\log N}\Big)\sum_{e\in P(r_{T},v)}\mathbf{Y}_{e}+\delta\sum_{e\in P(r_{T},v)}\mathbf{G}_{e} with the convention that the sum over the empty set is equal to the zero vector. (Here, P(r_{T},v) is as in Definition 2.1 .) For every u,v\in V with u\neq v , define the “good” event \mathcal{A}_{u,v}:=\begin{cases}\big[\|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{X}\leqslant 1\big]&\text{if }\,\{u,v\}\in E,\\ \big[\|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{X}>1\big]&\text{if }\,\{u,v\}\not\in E.\end{cases} Part (B) of Theorem 1.1 will follow once we show that (4.6) \mathbb{P}\Bigg(\bigcap_{\begin{subarray}{c}u,v\in V\\ u\neq v\end{subarray}}\mathcal{A}_{u,v}\Bigg)>0. 4.2. Auxiliary events Set (4.7) \ell_{0}:=\exp\big(\log^{c_{2}}N\big)\ \ \ \text{ and }\ \ \ k_{0}:=\max\Big\{3,\big\lceil(C_{B}L)^{4/(1-2c_{1})}\big\rceil,\big\lceil 4^{1/c_{1}}\big\rceil\Big\}, where C_{B} is as in Lemma 3.1 , and L is as in Theorem 2.3 . Taking N_{0} sufficiently large, we may assume that k_{0}\leqslant\ell_{0} . Next, for every u,v\in V with 2\leqslant\mathrm{dist}_{T}(u,v)\leqslant\ell_{0} , define the event \mathcal{L}_{u,v}:=\begin{cases}\Big[\big\|\underset{e\in P(r_{T},u)}{\sum}\mathbf{Y}_{e}-\underset{e\in P(r_{T},v)}{\sum}\mathbf{Y}_{e}\big\|_{X}\leqslant 1+\frac{1}{2\,m^{1-\kappa}}\Big]&\text{if }\,2\leqslant\mathrm{dist}_{T}(u,v)\leqslant k_{0},\\ \Big[\big\|\underset{e\in P(r_{T},u)}{\sum}\mathbf{Y}_{e}-\underset{e\in P(r_{T},v)}{\sum}\mathbf{Y}_{e}\big\|_{X}\leqslant\mathrm{dist}_{T}(u,v)^{c_{1}}\Big]&\text{if }\,k_{0}<\mathrm{dist}_{T}(u,v)\leqslant\ell_{0},\end{cases} where \kappa is as in Theorem 2.2 . Our goal in this subsection is to show that (4.8) \mathbb{P}\Bigg(\bigcap_{\begin{subarray}{c}u,v\in V\\ 2\leqslant\mathrm{dist}_{T}(u,v)\leqslant\ell_{0}\end{subarray}}\mathcal{L}_{u,v}^{\complement}\Bigg)>0. 4.2.1. The “path” graph Define the “path” graph \mathcal{G}=(\mathcal{V},\mathcal{E}) , which will act as the dependency graph in our application of the Lovász local lemma, by setting \mathcal{V}:=\big\{\{u,v\}\colon u,v\in V\text{ and }2\leqslant\mathrm{dist}_{T}(u,v)\leqslant\ell_{0}\big\}, \mathcal{E}:=\Big\{\big\{\{u,v\},\{u^{\prime},v^{\prime}\}\big\}\colon\{u,v\},\{u^{\prime},v^{\prime}\}\in\mathcal{V}\text{ and }P(u,v)\cap P(u^{\prime},v^{\prime})\neq\emptyset\Big\}. Moreover, for every k\in\{2,\dots,\ell_{0}\} set \mathcal{V}_{k}:=\big\{\{u,v\}\in\mathcal{V}\colon\mathrm{dist}_{T}(u,v)=k\big\} . Claim 4.1 . Let k,\ell\in\{2,\dots,\ell_{0}\} , and let \{u,v\}\in\mathcal{V_{\ell}} . Then, |N_{\mathcal{G}}(\{u,v\})\cap\mathcal{V}_{k}|\leqslant\min\big\{N^{2},5\ell k(\Delta-1)^{k-1}\big\}. Proof. Clearly, |N_{\mathcal{G}}(\{u,v\})\cap\mathcal{V}_{k}| is upper bounded by N^{2} . Thus, it suffices to show that (4.9) |N_{\mathcal{G}}(\{u,v\})\cap\mathcal{V}_{k}|\leqslant 5\ell k(\Delta-1)^{k-1}. Let s\in[k] be arbitrary, and set a_{s}:=\big|\big\{\{u^{\prime},v^{\prime}\}\in N_{\mathcal{G}}(\{u,v\})\cap\mathcal{V}_{k}\colon|P(u,v)\cap P(u,v)|=s\big\}\big| . We shall consider various cases. First, assume that s>\min\{\ell,k\} ; then, clearly, (4.10) a_{s}=0. Next, assume that s=\ell\leqslant k ; then, since \ell,k\geqslant 2 , we have (4.11) a_{\ell}\leqslant\sum_{x=0}^{k-\ell}(\Delta-1)^{x}(\Delta-1)^{k-\ell-x}=(\Delta-1)^{k-\ell}(k-\ell+1)\leqslant\frac{\ell k}{4}(\Delta-1)^{k-1}. If s=\ell-1\leqslant k , then (4.12) a_{s}\leqslant 2\big((\Delta-1)^{k-\ell+1}+(\Delta-2)(\Delta-1)^{k-\ell}(k-\ell+1)\big)\leqslant\ell k(\Delta-1)^{k-1}. Finally, if s\leqslant\min\{\ell-2,k\} , then (4.13) \displaystyle a_{s} \displaystyle\leqslant 2\big((\Delta-1)^{k-s}+(\Delta-2)(\Delta-1)^{k-s-1}(k-s)\big)+ \displaystyle\ \ \ \ \ \ \ \ \ \ \ +(\ell-s-1)\big(2(\Delta-2)(\Delta-1)^{k-s-1}+(\Delta-2)^{2}(\Delta-1)^{k-s-2}(k-s-1)\big) \displaystyle\leqslant 3\ell k(\Delta-2)(\Delta-1)^{k-s-1}. By ( 4.10 ) and ( 4.13 ), we have (4.14) \sum_{s=1}^{\ell-2}a_{s}\leqslant 3\ell k(\Delta-1)^{k-1}. The desired estimate ( 4.9 ) follows from ( 4.10 )–( 4.12 ) and ( 4.14 ). ∎ 4.2.2. Application of asymmetric Lovász local lemma Set k_{1}:=\Big\lfloor\frac{\log N}{\log(\Delta-1)}\Big\rfloor; since N_{0} can be taken sufficiently large, we may assume that for every k\in\{2,\dots,k_{1}\} we have (4.15) 6k\ell_{0}(\Delta-1)^{k}\leqslant N^{2}. For every k\in\{2,\dots,\ell_{0}\} set b_{k}:=\begin{cases}\frac{1}{2^{k+1}6\ell_{0}k(\Delta-1)^{k}}&\text{if }\,2\leqslant k\leqslant k_{1},\\ \frac{3}{2\pi^{2}k^{2}N^{2}}&\text{if }\,k_{1}k_{0}\geqslant 3 , we see that \displaystyle\frac{h(\{u,v\})}{2} \displaystyle=\exp\big(-\log 24-k\log(2\Delta-2)-\log k-\log^{c_{2}}N\big) \displaystyle=\exp\Big(-\Big(\frac{\log 24}{\log k}+\frac{k}{\log k}\log(2\Delta-2)+1+\frac{\log^{c_{2}}N}{\log k}\Big)\log k\Big) \displaystyle\geqslant\exp\Big(-\Big(\frac{\log 24}{\log 3}+\frac{k_{1}}{\log k_{1}}\log(2\Delta-2)+1+\frac{\log^{c_{2}}N}{\log k}\Big)\log k\Big) \displaystyle\geqslant\exp\Big(-\Big(4+\frac{\log N}{\log\log N-\log\log(\Delta-1)}\cdot\frac{\log(2(\Delta-1))}{\log(\Delta-1)}+\frac{\log^{c_{2}}N}{\log k}\Big)\log k\Big). Taking N_{0} sufficiently large and observing that \frac{\log(2(\Delta-1))}{\log(\Delta-1)}\leqslant 2 and \frac{\alpha_{1}}{8}>4 , we conclude that (4.20) \frac{h(\{u,v\})}{2}\geqslant\exp\Big(-\Big(4+4\frac{\log N}{\log\log N}+\log^{c_{2}}N\Big)\log k\Big)\stackrel{{\scriptstyle\eqref{eq:021}}}{{\geqslant}}\mathbb{P}(\mathcal{L}_{u,v}). Finally, assume that k\in\{k_{1}+1,\dots,\ell_{0}\} . As before, since \sum_{e\in P(r_{T},u)}\mathbf{Y}_{e}-\sum_{e\in P(r_{T},v)}\mathbf{Y}_{e} and \sum_{e\in P(u,v)}\mathbf{Y}_{e} have the same distribution, by Lemma 3.2 , the choice of k_{0} in ( 4.7 ) and the fact that k>k_{0} and c_{1}\leqslant\frac{1}{4} , we have (4.21) \mathbb{P}(\mathcal{L}_{u,v})\leqslant\exp\Big(-\frac{1}{2}\Big(\frac{1}{2}-c_{1}\Big)m\log k\Big)\leqslant\exp\Big(-\frac{\alpha_{1}}{8}\cdot\frac{\log N}{\log\log N}\log k\Big). Taking N_{0} sufficiently large, we may assume that \log k\geqslant\log\log N-\log\log(\Delta-1)\geqslant\frac{1}{2}\log\log N . Thus, by ( 4.21 ) and the choice of \alpha_{1} in ( 4.3 ), we have that (4.22) \mathbb{P}(\mathcal{L}_{u,v})\leqslant\exp(-4\log N). Since k_{1}\sqrt{m} , (4.25) \mathbb{P}\Bigg(\Big\|\frac{1}{\sqrt{|E^{\prime}|}}\sum_{e\in E^{\prime}}\mathbf{G}_{e}\Big\|_{2}^{*}>t\Bigg)\leqslant 2\exp\Big(-\frac{(t-\sqrt{m})^{2}}{2}\Big). Now, set \mathcal{L}:=\bigcap_{\begin{subarray}{c}u,v\in V\\ 2\leqslant\mathrm{dist}_{T}(u,v)\leqslant\ell_{0}\end{subarray}}\mathcal{L}_{u,v}^{\complement}. Note that in order to show ( 4.6 ), it suffices to prove that for every u,v\in V with u\neq v , (4.26) \mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big)\leqslant\frac{1}{N^{2}}. To that end, let u,v\in V with u\neq v and set k:=\mathrm{dist}_{T}(u,v) . Notice that (4.27) \boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)=\Big(1-\frac{1}{\log N}\Big)\Big(\sum_{e\in P(r_{T},u)}\mathbf{Y}_{e}-\sum_{e\in P(r_{T},v)}\mathbf{Y}_{e}\Big)+\delta\Big(\sum_{e\in P(r_{T},u)}\mathbf{G}_{e}-\sum_{e\in P(r_{T},v)}\mathbf{G}_{e}\Big); moreover, due to the independence of (\mathbf{Y}_{e})_{e\in E} and (\mathbf{G}_{e})_{e\in E} , for every measurable A\subseteq\mathbb{R}^{m} , (4.28) \mathbb{P}\Big(\sum_{e\in P(r_{T},u)}\mathbf{G}_{e}-\sum_{e\in P(r_{T},v)}\mathbf{G}_{e}\in A\;\Big|\,\mathcal{L}\Big)=\mathbb{P}\Big(\sum_{e\in P(u,v)}\mathbf{G}_{e}\in A\Big). We consider four cases according to the value of k . Case 1: k=1 In this case, we have e:=\{u,v\}\in E . Since \mathbf{Y}_{e} is uniformly chosen from the unit ball of X , by the definition of \mathcal{A}_{u,v} and ( 4.27 ) and ( 4.28 ), we have (4.29) \mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big)\leqslant\mathbb{P}\big(\|\mathbf{G}_{e}\|_{X}>\delta^{-1}\log^{-1}N\big)\stackrel{{\scriptstyle\eqref{eq:026}}}{{\leqslant}}\mathbb{P}\big(\|\mathbf{G}_{e}\|_{2}^{*}>m^{-\frac{1}{2}}\delta^{-1}\log^{-1}N\big). Since N_{0} can be taken sufficiently large, we see that \displaystyle\frac{\big(m^{-\frac{1}{2}}\delta^{-1}\log^{-1}N-\sqrt{m}\big)^{2}}{2} \displaystyle\ \ \ \ \ \ =\frac{1}{2}\Big(\exp\Big(\Big(\frac{1}{2}-\frac{c_{1}}{2}\Big)\log^{c_{2}}N-\frac{1}{2}\log m-\log\log N\Big)-\exp\Big(-\frac{1}{2}\log m\Big)\Big)^{2} \displaystyle\ \ \ \ \ \ \geqslant\exp\big((1-2c_{1})\log^{c_{2}}N\big)>2\log N+\log 2. By ( 4.25 ) and ( 4.29 ), we conclude that \mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big)\leqslant 2\exp\big(-2\log N-\log 2\big)=\frac{1}{N^{2}}. Case 2: k\in\{2,\dots,k_{0}\} By the definitions of \mathcal{L} and \mathcal{A}_{u,v} and ( 4.27 ), ( 4.28 ) and ( 4.24 ), (4.30) \displaystyle\mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big) \displaystyle\leqslant\mathbb{P}\Bigg(\delta\Big\|\sum_{e\in P(u,v)}\mathbf{G}_{e}\Big\|_{X}\geqslant\Big(1-\frac{1}{\log N}\Big)\Big(1+\frac{1}{2\,m^{1-\kappa}}\Big)-1\Bigg) \displaystyle\leqslant\mathbb{P}\Bigg(\Big\|\frac{1}{\sqrt{k}}\sum_{e\in P(u,v)}\mathbf{G}_{e}\Big\|_{2}^{*}\geqslant\frac{1}{\sqrt{k_{0}}\sqrt{m}\delta}\Big(\Big(1-\frac{1}{\log N}\Big)\Big(1+\frac{1}{2\,m^{1-\kappa}}\Big)-1\Big)\Bigg). Taking N_{0} sufficiently large and invoking the definitions of m , \ell_{0},k_{0} and \delta , we see that \displaystyle\frac{1}{2} \displaystyle\Big(\frac{1}{\sqrt{k_{0}}\sqrt{m}\delta}\Big(\Big(1-\frac{1}{\log N}\Big)\Big(1+\frac{1}{2\,m^{1-\kappa}}\Big)-1\Big)-\sqrt{m}\Big)^{2}\geqslant\frac{1}{2}\,\Big(\frac{1}{\sqrt{k_{0}}\sqrt{m}\delta}\cdot\frac{1}{4\,m^{1-\kappa}}-\sqrt{m}\Big)^{2} \displaystyle\geqslant\frac{1}{2}\Big(\exp\Big(\Big(\frac{1}{2}-\frac{c_{1}}{2}\Big)\log^{c_{2}}N-\Big(\frac{3}{2}-\kappa\Big)\log m+\log\Big(\frac{1}{4\sqrt{k_{0}}}\Big)\Big)-\exp\Big(-\frac{1}{2}\log m\Big)\Big)^{2} \displaystyle\geqslant\exp\big((1-2c_{1})\log^{c_{2}}N\big)>2\log N+\log 2. Hence, by ( 4.25 ) and ( 4.30 ), we obtain that \mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big)\leqslant 2\exp(-2\log N-\log 2)=\frac{1}{N^{2}}. Case 3: k\in\{k_{0}+1,\dots,\ell_{0}\} Using ( 4.24 ), the fact that 1-\frac{1}{\log N}\geqslant\frac{1}{2} and that in this case we have that k>k_{0}\geqslant 4^{\frac{1}{c_{1}}} , we see that (4.31) \displaystyle\mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big) \displaystyle\leqslant\mathbb{P}\Bigg(\delta\Big\|\sum_{e\in P(u,v)}\mathbf{G}_{e}\Big\|_{X}\geqslant\left(1-\frac{1}{\log N}\right)k^{c_{1}}-1\Bigg) \displaystyle\leqslant\mathbb{P}\Bigg(\Big\|\frac{1}{\sqrt{k}}\sum_{e\in P(u,v)}\mathbf{G}_{e}\Big\|_{X}\geqslant\frac{k^{c_{1}-\frac{1}{2}}}{4\delta}\Bigg)\leqslant\mathbb{P}\Bigg(\Big\|\frac{1}{\sqrt{k}}\sum_{e\in P(u,v)}\mathbf{G}_{e}\Big\|_{2}^{*}\geqslant\frac{\ell_{0}^{c_{1}-\frac{1}{2}}}{4\delta\sqrt{m}}\Bigg). On the other hand, by the definitions of \ell_{0} and \delta , \frac{1}{\delta}\,\ell_{0}^{c_{1}-\frac{1}{2}}=\exp\Big(\Big(\frac{1}{2}-\frac{c_{1}}{2}\Big)\log^{c_{2}}N+\Big(c_{1}-\frac{1}{2}\Big)\log^{c_{2}}N\Big)=\exp\Big(\frac{c_{1}}{2}\log^{c_{2}}N\Big), and so, taking N_{0} sufficiently large and using our starting assumption on the dimension m , \displaystyle\frac{1}{2}\,\Big(\frac{\ell_{0}^{c_{1}-\frac{1}{2}}}{4\delta\sqrt{m}}-\sqrt{m}\Big)^{2} \displaystyle=\frac{1}{2}\,\Big(\exp\Big(\frac{c_{1}}{2}\log^{c_{2}}N-\frac{1}{2}\log m+\log\frac{1}{4}\Big)-\exp\Big(-\frac{1}{2}\log m\Big)\Big)^{2} \displaystyle\geqslant\exp\Big(\frac{c_{1}}{2}\log^{c_{2}}N\Big)>2\log N+\log 2. By ( 4.25 ) and ( 4.31 ), we obtain that \mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big)\leqslant 2\exp\big(-2\log N-\log 2\big)=\frac{1}{N^{2}}. Case 4: k>\ell_{0} By ( 4.27 ), ( 4.28 ) and ( 4.24 ) and the fact that \mathbf{G}_{e} is symmetric for every e\in E , we have (4.32) \displaystyle\mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big) \displaystyle=\mathbb{P}\big(\|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{X}\leqslant 1\,\big|\,\mathcal{L}\big)\leqslant\mathbb{P}\big(\|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{2}^{*}\leqslant 1\,\big|\,\mathcal{L}\big) \displaystyle=\mathbb{P}\Big(\delta\sum_{e\in P(u,v)}\mathbf{G}_{e}\in-\Big(1-\frac{1}{\log N}\Big)\Big(\sum_{e\in P(r_{T},u)}\mathbf{Y}_{e}-\sum_{e\in P(r_{T},v)}\mathbf{Y}_{e}\Big)+B_{\|\cdot\|_{2}^{*}}\,\Big|\,\mathcal{L}\Big) \displaystyle\leqslant\mathbb{P}\Big(\delta\sum_{e\in P(u,v)}\mathbf{G}_{e}\in B_{\|\cdot\|_{2}^{*}}\,\Big|\,\mathcal{L}\Big)\leqslant\mathbb{P}\Bigg(\Big\|\frac{1}{\sqrt{k}}\sum_{e\in P(u,v)}\mathbf{G}_{e}\Big\|_{2}^{*}\leqslant\frac{1}{\delta\sqrt{\ell_{0}}}\Bigg). Next observe that, by the choices of \ell_{0} and \delta , (4.33) \frac{1}{\delta\sqrt{\ell_{0}}}=\exp\Big(-\frac{c_{1}}{2}\log^{c_{2}}N\Big). Moreover, the random variable \big\|\frac{1}{\sqrt{k}}\sum_{e\in P(u,v)}\mathbf{G}_{e}\big\|_{2}^{*} has the same distribution with \|\mathbf{G}\|_{2} , where \mathbf{G} denotes a random vector in \mathbb{R}^{m} with i.i.d. standard normal entries. Thus, by ( 4.32 ), (4.34) \mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big)\leqslant\mathbb{P}\left(\|\mathbf{G}\|_{2}\leqslant\frac{1}{\delta\sqrt{\ell_{0}}}\right). Since the density function of \mathbf{G} is pointwise bounded by 1 , this implies (4.35) \mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big)\leqslant\Big(\frac{C_{B}}{\delta\sqrt{\ell_{0}}}\Big)^{m}, where C_{B} is as in Lemma 3.1 . Finally, taking N_{0} sufficiently large, we conclude that \displaystyle\mathbb{P}\big(\mathcal{A}_{u,v}^{\complement}\,\big|\,\mathcal{L}\big) \displaystyle\leqslant\exp\Big(m\Big(-\frac{c_{1}}{2}\log^{c_{2}}N+\log C_{B}\Big)\Big)\leqslant\exp\Big(-m\frac{c_{1}}{4}\log^{c_{2}}N\Big) \displaystyle\leqslant\exp\Big(-\frac{\alpha_{1}c_{1}}{4}\cdot\frac{\log^{1+c_{2}}N}{\log\log N}\Big)\leqslant\exp\big(-2\log N\big)=\frac{1}{N^{2}}. The above cases are exhaustive, and so the entire proof of Theorem 1.1 is completed. Remark 4.3 . By slightly modifying the argument, it is not hard to see that, with positive probability, the random embedding \boldsymbol{\zeta} constructed in the proof of part (A) of Theorem 1.1 satisfies \bullet \|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{X}\leqslant 2{\rm dist}_{T}(u,v) for all u,v\in T , and \bullet \|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{X}\gtrsim\sqrt[10]{{\rm dist}_{T}(u,v)} for all u,v\in T with {\rm dist}_{T}(u,v)>k_{0} , where k_{0} is as ( 4.7 ).