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
1
0
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
).