A universal threshold for geometric embeddings of trees

Abstract.

A graph $G=(V,E)$ is geometrically embeddable into a normed space $X$ when there is a mapping $\zeta\colon V\to X$ such that $\|\zeta(v)-\zeta(w)\|_{X}\leqslant 1$ if and only if $\{v,w\}\in E$, for all distinct $v,w\in V$. Our result is the following universal threshold for the embeddability of trees. Let $\Delta\geqslant 3$, and let $N$ be sufficiently large in terms of $\Delta$. Every $N$–vertex tree of maximal degree at most $\Delta$ is embeddable into any normed space of dimension at least $64\,\frac{\log N}{\log\log N}$, and complete trees are non-embeddable into any normed space of dimension less than $\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.

1. 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$.

2. 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 necessarily has bi-Lipschitz distortion at least $\Omega\big{(}\sqrt{\log\log N}\big{)}$.​

We conclude with some open research questions, followed by a proof overview.

Problem 1.5(Optimal constants in Theorem 1.1).

Determine optimal values of the constants $\alpha_{0}$ and $\alpha_{1}$ in Theorem 1.1. Are they equal up to $\mathrm{o}(1)$ additive term?

Problem 1.6(Trees of growing maximal degree).

Determine an explicit function $m:=m(N,\Delta)$ and some universal constants $\alpha_{0}$ and $\alpha_{1}$ so that the following holds. Any tree on $N$ vertices with maximum degree $\Delta$ embeds into any normed space $X$ of dimension at least $\alpha_{1}\,m$. And, no complete tree of degree $\Delta$ embeds into any space of dimension less than $\alpha_{0}\,m$.

Proof overview

As already mentioned, part $(A)$ of Theorem 1.1 is known, and it appears (in a slightly different form) in the work of Frankl and Maehara [FM86]. We also note that a tree $T$ certifying the first part of the theorem can be constructed explicitly: if $N=\frac{\Delta^{n+1}-1}{\Delta-1}$ for an integer $n$, then $T$ can be taken to be the complete rooted $\Delta$-regular tree of height $n$.

Part $(B)$ is the bulk of the proof of Theorem 1.1. Given a normed space $X=(\mathbb{R}^{m},\|\cdot\|_{X})$ and a tree $T$, we attach to each edge of $T$ an independent vector drawn uniformly from the unit ball $B_{X}$. After arbitrarily choosing a root $\mathrm{o}$, each vertex $v$ is embedded by summing the vectors on the edges along the path from $\mathrm{o}$ to $v$, plus an independent “regularizing” Gaussian. Our goal is to show that this embedding is geometric with positive probability.

The main challenge is to verify that, with a non-zero probability, all pairs of non-adjacent vertices are at distance greater than one under the embedding. Note that the spatial distance between the images of two vertices with graph distance $\ell$ is given by a sum of $\ell$ independent vectors, plus some Gaussian regularization. To control the distance, we utilize small ball probability estimates for log-concave distributions; in particular, we apply thin-shell estimates (for small $\ell$), or density bounds on isotropic log-concave vectors that arise in the context of the recent resolution of the slicing conjecture [KL24b]. In either case, these probability estimates are not strong enough to survive the trivial union bound for arbitrary $N$–vertex trees. To deal with this problem, we apply a combination of a conditioning argument (using the aforementioned Gaussian regularization) and the asymmetric Lovász local lemma.

2. Background material

2.1. Notation

All graphs in this paper have no multiple edges and no self-loops. Given a graph $G$, we denote its vertex set by $V(G)$ and its edge set by $E(G)$. For every $v\in V(G)$, the neighbourhood of $v$ in $G$ is denoted by $N_{G}(v):=\big{\{}u\in V(G)\colon\{u,v\}\in E(G)\big{\}}$, and $\mathrm{dist}_{G}(\cdot,\cdot)$ denotes the shortest-path graph distance on $V(G)$. Recall that a tree is a connected graph with no cycles. For a normed space $X$, $B_{X}$ denotes the closed unit ball.

Definition 2.1.

Let $T$ be a tree, and let $u,v\in V(T)$. We say that a set $P\subseteq E(T)$connects $u$ and $v$ if there exist $u_{0},\ldots,u_{p}\in V$, where $p=|P|$, such that $u_{0}=u$, $u_{p}=v$ and $P=\big{\{}\{u_{i-1},u_{i}\}\colon i\in[p]\big{\}}$.

If $u\neq v$, then $P(u,v)$ denotes the smallest, under inclusion, set of edges that connects $u$ and $v$; by convention, we set $P(u,v)=\emptyset$ if $u=v$. We shall refer to sets of the form $P(u,v)$ as paths.

2.2. Isotropic random vectors, and normed spaces in isotropic position

Recall that a random vector $\mathbf{U}$ in $\mathbb{R}^{m}$ is isotropic if its components are mean-zero random variables, and its covariance matrix is the identity.

Now, let $X=(\mathbb{R}^{m},\|\cdot\|_{X})$ be an $m$-dimensional normed space, and let $\mathbf{X}$ be a random vector in $\mathbb{R}^{m}$ uniformly distributed in $B_{X}$. We say that $X$ is in isotropic position if the random vector $\mathbf{X}$ is isotropic; we emphasize that in asymptotic geometric analysis literature, an alternative definition involving normalization of the Lebesgue volume of $B_{X}$ is used occasionally. It is a standard fact that any finite-dimensional normed space can be placed in isotropic position by applying an invertible linear transformation (see, e.g., [KL24a]).

2.3. Asymptotic geometric analysis

We will need two deep results from asymptotic geometric analysis. The first one the following thin-shell estimate due to Klartag [Kl07].

Theorem 2.2(Thin-shell concentration for log-concave measures).

There exist absolute constants $\kappa>0$ and $C>0$ with the following property. If  $\mathbf{U}$ is an isotropic random vector in $\mathbb{R}^{m}$ with a log-concave distribution, then

(2.1)$$\mathbb{P}\Big{(}\big{|}\|\mathbf{U}\|_{2}-\sqrt{m}\big{|}\geqslant m^{\frac{1$$

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-$$

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$$

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}$$

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$$

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$$

Therefore,

$$\lambda(B_{X})\leqslant 2\lambda\big{(}B_{X}\cap c\sqrt{m}\,B_{\ell^{m}_{2}}$$

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 $0<c_{1}<\frac{1}{2}$ such that

(3.1)$$k\geqslant\big{(}C_{B}\,L\big{)}^{\frac{4}{1-2c_{1}}},$$

where $C_{B}$ is as in Lemma 3.1, and $L$ is as in Theorem 2.3. Finally, let $(\mathbf{Y}_{1},\dots,\mathbf{Y}_{k})$ be i.i.d. random vectors uniformly distributed in $B_{X}$. Then,

(3.2)$$\mathbb{P}\Bigg{(}\Big{\|}\sum_{i=1}^{k}\mathbf{Y}_{i}\Big{\|}_{X}\leqslant k^$$

Proof.

Let $g$ denote the density function of the random vector $\mathbf{Y}=\frac{1}{\sqrt{k}}\sum_{i=1}^{k}\mathbf{Y}_{i}$. Notice that $\mathbf{Y}$ is isotropic and log-concave; consequently, by Theorem 2.3, the function $g$ is pointwise bounded by $L^{m}$. Hence, by Lemma 3.1, we have

(3.3)$$\mathbb{P}\Bigg{(}\Big{\|}\sum_{i=1}^{k}\mathbf{Y}_{i}\Big{\|}_{X=\mathbb{P}\Bigg{(}\Big{\|}\frac{1}{\sqrt{k}}\sum_{i=1}^{k}$$

$$=\int g(x)\mathbbm{1}_{k^{c_{1}-\frac{1}{2}}B_{X}}(x)\,dx$$

$$\leqslant\Big{(}\frac{C_{B}L}{k^{\frac{1}{2}-c_{1}}}\Big{)}^{m}$$

The next lemma complements Lemma 3.2, and it will used when $k$ is smaller than the threshold appearing in the right-hand-side of (3.1).

Lemma 3.3.

There exists a positive integer $m_{1}$ with the following property. Let $m\geqslant m_{1}$ be an integer, let $X=(\mathbb{R}^{m},\|\cdot\|_{X})$ be a normed space in isotropic position, let $k\geqslant 2$ be an integer, and let $(\mathbf{Y}_{1},\dots,\mathbf{Y}_{k})$ be i.i.d. random vectors uniformly distributed in $B_{X}$. Then,

(3.4)$$\mathbb{P}\Bigg{(}\Big{\|}\sum_{i=1}^{k}\mathbf{Y}_{i}\Big{\|}_{X}\leqslant 1+$$

where $\kappa$ is as in Theorem 2.2.

Proof.

Set $\gamma:=\frac{2-\sqrt{2}}{4}$, $\varepsilon:=\frac{1}{2\,m^{1-\kappa}}$, and $\Gamma:=B_{X}\setminus\Big{(}(1+\varepsilon)^{-1}(1-\gamma)\sqrt{k}\sqrt{m}\,B$. Notice that

(3.5)$$\mathbb{P}\Bigg{(}\Big{\|}\sum_{i=1}^{k}\mathbf{Y}_{i}\Big{\|}_{X}\leqslant 1+$$

As in the proof of Lemma 3.2, we observe that the random vector $\frac{1}{\sqrt{k}}\sum_{i=1}^{k}\mathbf{Y}_{i}$ is isotropic and log-concave. Therefore, by Theorem 2.2, if $m_{1}$ is sufficiently large, we have

(3.6)$$\mathbb{P}\Bigg{(}\sum_{i=1}^{k}\mathbf{Y}_{i}\in(1-\gamma)\sqrt{k}\sqrt{m}\,B$$

Notice that $(1-\gamma)\sqrt{2}=\frac{\sqrt{2}+1}{2}>1$. 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$$

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($, the following hold.

1. For every $v\in V(T)$, we have $\mathrm{dist}_{T}(r_{T},v)\leqslant h_{0}$.

2. 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$$

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_{$$

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}{$$

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)}$$

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{$$

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$$

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$$

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$$

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}$$

$$\mathcal{E}:=\Big{\{}\big{\{}\{u,v\},\{u^{\prime},v^{\prime}\}\big{\}}\colon\{$$

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$.

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$$

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\})$.

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}=($$

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-$$

Finally, if $s\leqslant\min\{\ell-2,k\}$, then

(4.13)$$a_{s} \leqslant 2\big{(}(\Delta-1)^{k-s}+(\Delta-2)(\Delta-1)^{k-s-1}(k$$

$$\ \ \ \ \ \ \ \ \ \ \ +(\ell-s-1)\big{(}2(\Delta-2)(\Delta-1)^{k-$$

$$\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$$

and define $h\colon\mathcal{V}\to[0,1)$ by $h(\{u,v\})=b_{\mathrm{dist}_{T}(u,v)}$. By the choice of $(b_{k})_{k=2}^{\ell_{0}}$ and (4.15), we see that $\sum_{k=2}^{\ell_{0}}b_{k}\cdot\min\{N^{2},6\ell_{0}k(\Delta-1)^{k}\}\leqslant$. Hence, by Claim 4.1, for every $\{u,v\}\in\mathcal{V}$,

(4.16)$$\prod_{\{u^{\prime},v^{\prime}\}\in N_{\mathcal{G}}(\{u,v\})}\big{(}1-h(\{u^{$$

Claim 4.2.

For every $\{u,v\}\in\mathcal{V}$, we have $\mathbb{P}(\mathcal{L}_{u,v})\leqslant\frac{1}{2}h(\{u,v\})$.

Proof.

Fix $\{u,v\}\in\mathcal{V}$, and set $k:=\mathrm{dist}_{T}(u,v)$. We distinguish three cases.

First, assume that $k\in\{2,\dots,k_{0}\}$. Since the random vectors $\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, then provided that $N_{0}$ is sufficiently large, by Lemma 3.3,

(4.17)$$\mathbb{P}(\mathcal{L}_{u,v})\leqslant\exp\big{(}-m^{\frac{\kappa}{2}}\big{)}$$

On the other hand, by the choice of $\ell_{0}$ in (4.7),

(4.18)$$\frac{h(\{u,v\})}{2}\geqslant b_{k_{0}}\geqslant\exp\big{(}-\log 24-k_{0}\log($$

Since $c_{2}<\frac{\kappa}{2}$ and using the fact that $N_{0}$ can be taken sufficiently large, the claim follows in this case by (4.17) and (4.18).

Next, assume that $k\in\{k_{0}+1,\dots,k_{1}\}$. Using again the fact that $\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 $c_{1}\leqslant\frac{1}{4}$, we obtain that

(4.19)$$\mathbb{P}(\mathcal{L}_{u,v})\leqslant\exp\Big{(}-\frac{1}{2}\Big{(}\frac{1}{2$$

Since the function $f(x)=\frac{x}{\log x}$ is increasing for $x\geqslant 3$ and $k>k_{0}\geqslant 3$, we see that

$$\frac{h(\{u,v\})}{2} =\exp\big{(}-\log 24-k\log(2\Delta-2)-\log k-\log^{c_{2}}N\big{)}$$

$$=\exp\Big{(}-\Big{(}\frac{\log 24}{\log k}+\frac{k}{\log k}\log(2$$

$$\geqslant\exp\Big{(}-\Big{(}\frac{\log 24}{\log 3}+\frac{k_{1}}{$$

$$\geqslant\exp\Big{(}-\Big{(}4+\frac{\log N}{\log\log N-\log\log($$

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}+$$

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$$

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}<k\leqslant\ell_{0}$, taking $N_{0}$ sufficiently large, we see that

(4.23)$$\frac{h(\{u,v\})}{2} =\exp\Big{(}-\log\Big{(}\frac{4\pi^{2}}{3}\Big{)}-2\log k-2\log N$$

$$\geqslant\exp\Big{(}-3\log N\Big{)}.$$

Thus, this final case the claim follows from (4.22) and (4.23). ∎

By Claim 4.2 and inequality (4.16), for every $\{u,v\}\in\mathcal{V}$,

$$\mathbb{P}(\mathcal{L}_{u,v})\leqslant h(\{u,v\})\prod_{\{u^{\prime},v^{\prime$$

Therefore, inequality (4.8) follows from Lemma 2.7.

4.3. Completion of the proof of part $(B)$ of Theorem 1.1

Let $x_{1},\dots,x_{m}\in\mathbb{R}^{m}$ be the vectors selected in Subsection 4.1. It is convenient to introduce an auxiliary norm $\|\cdot\|_{2}^{*}$ in $\mathbb{R}^{m}$ as follows. Given $x\in\mathbb{R}^{m}$ written as $x=\sum_{i=1}^{m}a_{i}x_{i}$, we set $\|x\|_{2}^{*}=(a_{1}^{2}+\dots+a_{m}^{2})^{1/2}$. By (2.4), we see that for every $x\in\mathbb{R}^{m}$,

(4.24)$$\|x\|_{2}^{*}\leqslant\|x\|_{X}\leqslant\sqrt{m}\|x\|_{2}^{*}.$$

Moreover, recalling (4.4) and Fact 2.5, for every subset $E^{\prime}$ of the edge-set $E$ of $T$ and every $t>\sqrt{m}$,

(4.25)$$\mathbb{P}\Bigg{(}\Big{\|}\frac{1}{\sqrt{|E^{\prime}|}}\sum_{e\in E^{\prime}}$$

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$$

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{)}$$

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{)}$$

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)}$$

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{)}$$

Since $N_{0}$ can be taken sufficiently large, we see that

$$\frac{\big{(}m^{-\frac{1}{2}}\delta^{-1}\log^{-1}N-\sqrt{m}\big{)$$

$$\ \ \ \ \ \ =\frac{1}{2}\Big{(}\exp\Big{(}\Big{(}\frac{1}{2}-$$

$$\ \ \ \ \ \ \geqslant\exp\big{(}(1-2c_{1})\log^{c_{2}}N\big{)}>2$$

By (4.25) and (4.29), we conclude that

$$\mathbb{P}\big{(}\mathcal{A}_{u,v}^{\complement}\,\big{|}\,\mathcal{L}\big{)}$$

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)$$\mathbb{P}\big{(}\mathcal{A}_{u,v}^{\complement}\,\big{|}\,\leqslant\mathbb{P}\Bigg{(}\delta\Big{\|}\sum_{e\in P(u,v)}$$

$$\leqslant\mathbb{P}\Bigg{(}\Big{\|}\frac{1}{\sqrt{k}}\sum_{e\in P$$

Taking $N_{0}$ sufficiently large and invoking the definitions of $m$, $\ell_{0},k_{0}$ and $\delta$, we see that

$$\frac{1}{2} \Big{(}\frac{1}{\sqrt{k_{0}}\sqrt{m}\delta}\Big{(}\Big{(}1-\frac{$$

$$\geqslant\frac{1}{2}\Big{(}\exp\Big{(}\Big{(}\frac{1}{2}-\frac{c_$$

$$\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{)}$$

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)$$\mathbb{P}\big{(}\mathcal{A}_{u,v}^{\complement}\,\big{|}\,\leqslant\mathbb{P}\Bigg{(}\delta\Big{\|}\sum_{e\in P(u,v)}$$

$$\leqslant\mathbb{P}\Bigg{(}\Big{\|}\frac{1}{\sqrt{k}}\sum_{e\in P$$

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}-$$

and so, taking $N_{0}$ sufficiently large and using our starting assumption on the dimension $m$,

$$\frac{1}{2}\,\Big{(}\frac{\ell_{0}^{c_{1}-\frac{1}{2}}}{4\delta=\frac{1}{2}\,\Big{(}\exp\Big{(}\frac{c_{1}}{2}\log^{c_{2}}N-$$

$$\geqslant\exp\Big{(}\frac{c_{1}}{2}\log^{c_{2}}N\Big{)}>2\log N+$$

By (4.25) and (4.31), we obtain that

$$\mathbb{P}\big{(}\mathcal{A}_{u,v}^{\complement}\,\big{|}\,\mathcal{L}\big{)}$$

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)$$\mathbb{P}\big{(}\mathcal{A}_{u,v}^{\complement}\,\big{|}\,=\mathbb{P}\big{(}\|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|$$

$$=\mathbb{P}\Big{(}\delta\sum_{e\in P(u,v)}\mathbf{G}_{e}\in-\Big{$$

$$\leqslant\mathbb{P}\Big{(}\delta\sum_{e\in P(u,v)}\mathbf{G}_{e}$$

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{)}$$

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{)}$$

where $C_{B}$ is as in Lemma 3.1. Finally, taking $N_{0}$ sufficiently large, we conclude that

$$\mathbb{P}\big{(}\mathcal{A}_{u,v}^{\complement}\,\big{|}\,\leqslant\exp\Big{(}m\Big{(}-\frac{c_{1}}{2}\log^{c_{2}}N+\log C_$$

$$\leqslant\exp\Big{(}-\frac{\alpha_{1}c_{1}}{4}\cdot\frac{\log^{1+$$

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

1. $\|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{X}\leqslant 2{\rm dist}_{T}(u$ for all $u,v\in T$, and

2. $\|\boldsymbol{\zeta}(u)-\boldsymbol{\zeta}(v)\|_{X}\gtrsim\sqrt[10]{{\rm dist}$ for all $u,v\in T$ with ${\rm dist}_{T}(u,v)>k_{0}$,

where $k_{0}$ is as (4.7).

Acknowledgments

The research was supported in the framework of H.F.R.I call “Basic research Financing (Horizontal support of all Sciences)” under the National Recovery and Resilience Plan “Greece 2.0” funded by the European Union–NextGenerationEU (H.F.R.I. Project Number: 15866). The third named author (K.T.) is partially supported by the NSF grant DMS 2331037.