# Spanning trees in sparse expanders

Jie Han  School of Mathematics and Statistics, Beijing Institute of
Technology, Beijing, China. Email<EMAIL_ADDRESS>and  Donglei Yang  Data
Science Institute, Shandong University, Shandong, China. Email:
<EMAIL_ADDRESS>
###### Abstract.

Given integers $n\geq\Delta\geq 2$, let $\mathcal{T}(n,\Delta)$ be the
collection of all $n$-vertex trees with maximum degree at most $\Delta$. A
question of Alon, Krivelevich and Sudakov in 2007 asks for determining the
best possible spectral gap condition forcing an $(n,d,\lambda)$-graph to be
$\mathcal{T}(n,\Delta)$-universal, namely, it contains all members of
$\mathcal{T}(n,\Delta)$ as a subgraph simultaneously. In this paper we show
that for sufficiently large integer $n$ and all $\Delta\in\mathbb{N}$, every
$(n,d,\lambda)$-graph with

$\lambda\leq\frac{d}{2\Delta^{5\sqrt{\log n}}}$

is $\mathcal{T}(n,\Delta)$-universal. As an immediate corollary, this implies
that Alon’s ingenious construction of triangle-free sparse expander is
$\mathcal{T}(n,\Delta)$-universal, which provides an explicit construction of
such graphs and thus solves a question of Johannsen, Krivelevich and Samotij.
Our main result is formulated under a much more general context, namely, the
$(n,d)$-expanders. More precisely, we show that there exist absolute constants
$C,c>0$ such that the following statement holds for sufficiently large integer
$n$.

  1. (1)

For all $\Delta\in\mathbb{N}$, every $(n,\Delta^{5\sqrt{\log n}})$-expander is
$\mathcal{T}(n,\Delta)$-universal.

  2. (2)

For all $\Delta\in\mathbb{N}$ with $\Delta\leq c\sqrt{n}$, every $(n,C\Delta
n^{1/2})$-expander is $\mathcal{T}(n,\Delta)$-universal.

Both results significantly improve a result of Johannsen, Krivelevich and
Samotij, and have further implications in locally sparse expanders and Maker-
Breaker games that also improve previously known results drastically.

##  1\. Introduction

A graph $G$ is called _universal_ for a family of graphs $\mathcal{F}$ for
every $F\in\mathcal{F}$, $F$ is a subgraph of $G$. There has been a rich body
of research on explicit or randomized constructions of universal graphs [3, 4,
5, 8, 11, 14, 15, 16, 17]. In this paper, we focus on the case when
$\mathcal{F}$ is a family of _spanning trees_ with bounded maximum degree. The
problem of existence of large trees in graphs and random graphs has a long and
profound history.

For integers $n,\Delta\in\mathbb{N}$, we define $\mathcal{T}(n,\Delta)$ as the
family of all $n$-vertex trees with maximum degree at most $\Delta$. The
binomial random graphs $G(n,p)$ are $n$-vertex graphs where every pair of
vertices is connected with probability $p$, independent of other pairs.
Regarding the containment of a single bounded degree tree in random graphs,
Kahn [28] conjectured that for any $\Delta>0$, there exists a constant
$C:=C(\Delta)$ such that $C(\Delta)\log(n)/n$ is the threshold111Given a non-
trivial monotone graph property $\mathcal{P}$, a function $q(n)$ is called a
threshold function for $\mathcal{P}$ if when $p(n)/q(n)\to 0$ the probability
that $G(n,p)$ satisfies $\mathcal{P}$ tends to 0, and when
$p(n)/q(n)\to\infty$ the probability that $G(n,p)$ satisfies $\mathcal{P}$
tends to 1. for a spanning tree with maximum degree $\Delta$ in $G(n,p)$. In
particular, this would imply that the threshold for constant maximum degree
spanning trees is $\log(n)/n$. The conjecture of Kahn is resolved by a
breakthrough of Montgomery [38], who actually showed that at the conjectured
threshold one actually gets the universality for the family
$\mathcal{T}(n,\Delta)$.

######  Theorem 1.1.

[38] There exists $C=C(\Delta)$ such that $G(n,\frac{C\log n}{n})$ is a.a.s
$\mathcal{T}(n,\Delta)$-universal.

Montgomery’s result for single tree containment is further obtained recently
by Frankston, Kahn, Narayanan and Park [21] and by Park and Pham [39] in their
resolutions of the fractional expectation-threshold conjecture of Talagrand
[40], and the expectation-threshold conjecture itself due to Kahn and Kalai
[27].

These recent celebrated developments extend drastically our knowledge on
_thresholds_ , the optimal probability for the emergence of subgraphs in
random graphs. It also raises naturally the question of constructions of
sparse universal graphs for spanning trees and other natural graph classes.

###  1.1. Universality in sparse graphs

Another natural graph class is $\mathcal{H}(n,\Delta)$, the class of all
$n$-vertex graphs with maximum degree at most $\Delta$. For dense random
graphs $G(n,p)$ where $p$ is a constant, the celebrated blow-up lemma of
Komlós, Sárközy and Szemerédi [31] shows that $G(n,p)$ is universal for
$\mathcal{H}(n,\Delta)$ when $\Delta$ is a constant. Unlike the dense case,
the study of universality in sparse random graphs is proven to be a
challenging task. Following some initial progress by Krivelevich [32] and Kim
[29], Johansson, Kahn and Vu [26] showed (among other things) that the
threshold for the existence of a $K_{\Delta+1}$-factor is
$n^{-\frac{2}{\Delta+1}}(\log n)^{1/\binom{\Delta+1}{2}}$. For universality,
Dellamonica, Kohayakawa, Rödl and Ruciński [18] (for $\Delta\geq 3$) and Kim
and Lee [30] (for $\Delta=2$) showed that $G(n,p)$ are
$\mathcal{H}(n,\Delta)$-universal for $p=\tilde{\Omega}(n^{-1/\Delta})$. The
case $\Delta\geq 3$ has been subsequently improved by Ferber and Nenadov [20],
and the case $\Delta=2$, namely, for the 2-universality, the optimal threshold
$p=C\left(\frac{\log n}{n^{2}}\right)^{1/3}$ was established in an excellent
work of Ferber, Kronenberg and Luh [19].

Now let us switch to another fruitful area, the study of sparse pseudorandom
graphs. One prominent class of such graphs are expander graphs. Given a graph
$G$ on $n$ vertices, let $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$
be the eigenvalues of its adjacency matrix. Then $\lambda(G)=\max_{2\leq i\leq
n}|\lambda_{i}|$ is called _the second eigenvalue_ of $G$. An
$(n,d,\lambda)$-_graph_ $G$ is a $d$-regular graph on $n$ vertices and the
second eigenvalue of $G$ is at most $\lambda$ (its first eigenvalue is equal
to $d$). The well-known Expander Mixing Lemma gives a good estimate on the
edge distribution of an $(n,d,\lambda)$-graph, which suggests that if
$\lambda$ is much smaller than the degree $d$, then $G$ has strong expansion
properties. Therefore, many typical embedding problems asks for the best
possible condition on _spectral gap_ $\frac{\lambda}{d}$ to ensure certain
structures. For instance, a celebrated conjecture of Krivelevich and Sudakov
[34] states that there exists $c>0$ such that for large enough $n$, every
$(n,d,\lambda)$-graph with $\frac{\lambda}{d}<c$ is Hamiltonian. Similar to
sparse random graphs, embedding (and universality) problems appear to be very
hard in $(n,d,\lambda)$-graphs. The sparse blow-up lemma developed in [1]
shows that $(n,d,\lambda)$-graphs with
$\lambda=o((d/n)^{\max\\{4,(3\Delta+1)/2\\}}n)$ are
$\mathcal{H}(n,\Delta)$-universal.

In this paper, we shall focus on the following problem on tree-universality
proposed by Alon, Krivelevich and Sudakov [7] in 2007.

######  Question 1.2.

[7] Is it true that for every $\Delta\in\mathbb{N}$, there exists
$c=c(\Delta)>0$ such that every $(n,d,\lambda)$-graph with
$\frac{\lambda}{d}<c$ is $\mathcal{T}(n,\Delta)$-universal?

Alon, Krivelevich and Sudakov [7] obtained the following result on embedding
almost spanning trees (subsequent improvement on the spectral gap was obtained
by Balogh, Csaba, Pei and Samotij [9]).

######  Theorem 1.3.

[7, 9] For all $\Delta\in\mathbb{N}$ and constant $0<\varepsilon<1/2$, every
$(n,d,\lambda)$-graph with

$\frac{\lambda}{d}\leq\frac{\varepsilon}{\sqrt{8\Delta}}$

is $\mathcal{T}(n-\varepsilon n,\Delta)$-universal.

Our first main result is as follows.

######  Theorem 1.4.

For sufficiently large integer $n$ and all $\Delta\in\mathbb{N}$, every
$(n,d,\lambda)$-graph with

$\lambda\leq\frac{d}{2\Delta^{5\sqrt{\log n}}}$

is $\mathcal{T}(n,\Delta)$-universal.

Note that when $\Delta=2^{o(\sqrt{\log n})}$, it holds that
$\Delta^{5\sqrt{\log n}}=n^{o(1)}$, namely, Theorem 1.4 narrows the spectral
gap which bypasses any polynomial function of $n$. We also remark that our
proof also works under a slightly more general context, namely, the
$(p,\beta)$-bijumbled graphs with a minimum degree condition. Indeed, a graph
$G=(V,E)$ is $(p,\beta)$-bijumbled if for every vertex sets $X,Y\subseteq V$,
we have

$|e_{G}(X,Y)-p|X||Y||\leq\beta\sqrt{|X||Y|},$

where $e_{G}(X,Y):=|\\{xy\in E(G)\mid(x,y)\in X\times Y\\}|$ (so edges in
$X\cap Y$ are counted twice). It is well-known that $(n,d,\lambda)$-graphs are
$(d/n,\lambda)$-bijumbled.

######  Theorem 1.5.

For sufficiently large $n$ and all $\Delta\in\mathbb{N}$, every $n$-vertex
$(p,\beta)$-bijumbled with

${\beta}\leq\frac{pn}{4\Delta^{5\sqrt{\log n}}}$

and minimum degree at least $4\sqrt{\beta pn}$ is
$\mathcal{T}(n,\Delta)$-universal.

Note that the minimum degree condition we enforce in Theorem 1.5 is
significantly weaker than that in Theorem 1.4, which considers $d$-regular
(namely, $pn$-regular) graphs.

###  1.2. Universality for $(n,d)$-expanders

Our next result is on the universality problem in a broader class of graphs,
namely, the $(n,d)$-expander graphs, defined as follows. The notion of
$(n,d)$-expander is first formulated by Johannsen, Krivelevich and Samotij,
which is an adaptation of the expansion properties investigated by Hefetz,
Krivelevich and Szabó [24] for the Hamiltonicity of highly connected graphs.

######  Definition 1.6.

[25] Given $n\in\mathbb{N}$ and $d>0$, an $n$-vertex graph $G$ is an
$(n,d)$-_expander_ if $G$ satisfies the following two conditions:

  1. (i)

$|N_{G}(X)|\geq d|X|$ for all $X\subseteq V(G)$ with $1\leq|X|<\frac{n}{2d}$;

  2. (ii)

$e_{G}(X,Y)>0$ for all disjoint $X,Y\subseteq V(G)$ with
$|X|=|Y|\geq\frac{n}{2d}$.

Montgomery [37] proposed a slightly stronger version of expansion property as
follows.

######  Definition 1.7.

For a graph $G$ and a set $W\subseteq V(G)$, we say $G$ _$d$ -expands_ into
$W$ if

  1. (i)

$|N_{G}(X,W)|\geq d|X|$ for all $X\subseteq V(G)$ with
$1\leq|X|<\lceil\frac{|W|}{2d}\rceil$, and,

  2. (ii)

$e_{G}(X,Y)>0$ for all disjoint $X,Y\subseteq V(G)$ with
$|X|=|Y|=\lceil\frac{|W|}{2d}\rceil$.

Clearly, if $G$ $d$-expands into $W$, then by definition $G[W]$ itself is a
$(|W|,d)$-expander. More often, we call a graph $G$ $m$-_joined_ if there is
an edge in $G$ between every two disjoint sets of at least $m$ vertices.

Johanssen, Krivelevich and Samotij [25] were the first to show that expander
graphs are tree-universal, and thus provide explicit constructions of sparse
tree-universal graphs, e.g. by the celebrated construction of Ramanujan graphs
by Lubotzky-Phillips-Sarnak [36]. Since expanders are locally sparse (e.g.
with small clique number), this complements previous constructions of Bhatt,
Chung, Leighton and Rosenberg [11] that are locally dense, namely, their
constructions contain a large number of cliques of size $\Omega(\Delta)$. Now
we present the results of Johanssen, Krivelevich and Samotij [25] on spanning
tree universality.

######  Theorem 1.8.

[25] There exists an absolute constant $c>0$ such that the following statement
holds. For all $n,\Delta\in\mathbb{N}$ with $\Delta\leq cn^{1/3}$, every
$(n,7\Delta n^{2/3})$-expander is $\mathcal{T}(n,\Delta)$-universal.

They also proved the following result on the containment of almost spanning
trees.

######  Theorem 1.9.

[25] Let $n,\Delta\in\mathbb{N}$ and $d\geq 2\Delta$. Then every
$(n,d)$-expander is
$\mathcal{T}\left(n-4\Delta\lceil\frac{n}{2d}\rceil,\Delta\right)$-universal.

Our second main result improves Theorem 1.8.

######  Theorem 1.10.

There exist absolute constants $C,c>0$ such that the following statement holds
for sufficiently large integer $n$. For all $\Delta\in\mathbb{N}$ with
$\Delta\leq c\sqrt{n}$, every $(n,C\Delta\sqrt{n})$-expander is
$\mathcal{T}(n,\Delta)$-universal.

For smaller values of $\Delta$, we further improve the result as follows.

######  Theorem 1.11.

There exists $n_{0}\in\mathbb{N}$ such that for all integers $n,\Delta$ with
$n\geq n_{0}$ and $\Delta\geq 2$, every $(n,d)$-expander with

$d\geq\Delta^{5\sqrt{\log n}}$

is $\mathcal{T}(n,\Delta)$-universal.

In fact, Theorem 1.11 implies Theorem 1.4 and Theorem 1.5 by the following
observations.

######  Proposition 1.12.

Given $n,p,\beta$ with $0<\beta\leq\frac{pn}{400}$, every $n$-vertex
$(p,\beta)$-bijumbled graph with minimum degree at least $4\sqrt{p\beta n}$ is
an $(n,d_{1})$-expander for $d_{1}=\frac{pn}{4\beta}$. Moreover, every
$(n,d,\lambda)$-graph with $\lambda<\frac{d}{8}$ is an
$(n,\frac{d}{2\lambda})$-expander.

We include a short proof of Proposition 1.12 in Appendix B. At last, we remark
that $(n,\frac{d}{2\lambda})$-expander graphs have a minimum degree
$\frac{d}{2\lambda}$, which is also considerably weaker than that of
$(n,d,\lambda)$-graphs (which are $d$-regular).

###  1.3. Further implications

Our main result also allows us to improve several other interesting results of
Johanssen, Krivelevich and Samotij [25].

####  1.3.1. Locally sparse expanders

Johanssen, Krivelevich and Samotij [25] studied constructions of tree-
universal graphs which are locally sparse. Using probabilistic arguments
(Lemma 6.2 in [25]) together with Theorem 1.8, they were able to prove the
existence of a tree-universal graph with small clique number.

######  Theorem 1.13.

[25, Theorem 2.4] There exists an absolute constant $c>0$ such that the
following statement holds. Let $n\in\mathbb{N}$ and let $r\in\mathbb{N}$ with
$r\geq 5$. Then there exists a graph with clique number at most $r$ that is
$T(n,cn^{1/3-2/(r+2)}/\log n)$-universal.

Moreover, they [25] posed the question of finding constructions that are
triangle-free or even have large girth whilst keeping tree-universality. A
promising candidate is the celebrated triangle-free construction of an
$(n,d,\lambda)$-graph due to Alon [2] with $d=\Theta(n^{2/3})$ and
$\lambda=\Theta(n^{1/3})$ or its generalizations to sparse expanders without
short odd cycles [6, 35]. Theorem 1.4 implies that these graphs are tree-
universal.

######  Theorem 1.14.

For $\Delta,r\in\mathbb{N}$ with $r\geq 1$ and sufficiently large
$n\in\mathbb{N}$, there exists an $n$-vertex graph $G$ that is
$T(n,\Delta)$-universal and contains no odd cycle of length at most $2r+1$.
Moreover, $G$ can be explicitly constructed.

Comparing with Theorem 1.13, we also observe that using the same probabilistic
arguments, Theorem 1.10 (in place of Theorem 1.8) implies the existence of a
graph with clique number at most $r$ that is $T(n,cn^{1/2-2/(r+2)}/\log
n)$-universal, where $r\geq 3$.

####  1.3.2. Maker-Breaker Game

An $(a:b)$ Maker-Breaker game is played on a finite hypergraph
$H=(V,\mathcal{F})$ between two players, Maker and Breaker. The game is played
in turns, starting with Maker’s turn. In each of their turns, Maker claims $a$
and Breaker claims $b$ previously unclaimed vertices, respectively. Maker’s
objective is to claim all vertices of a hyperedge by the end of the game. In
this case, Maker wins the game. Breaker’s objective is to claim at least one
vertex in each hyperedge by the end of the game. In this case, Breaker wins
the game. The game ends when all vertices have been claimed, by which time
either Maker or Breaker have won. The numbers $a$ and $b$ are called the
_biases_ of Maker and Breaker, respectively. We say that an $(a:b)$ Maker-
Breaker game is Maker’s win if Maker has a strategy that allows him to win the
game regardless of Breaker’s strategy, otherwise the game is Breaker’s win.
For a more detailed discussion, we refer the reader to [10].

Johanssen, Krivelevich and Samotij [25] formulated a Maker-Breaker Expander
Game.

######  Definition 1.15.

[25, Maker-Breaker Expander Game] For $n,\Delta\in\mathbb{N}$, the _Maker-
Breaker $(n,d)$-expander game_ on a graph $G$ is the Maker-Breaker game on the
hypergraph $H=(E(G),\mathcal{F})$, where $\mathcal{F}$ consists of all edge
sets $F\subseteq E(G)$ such that the subgraph $(V(G),F)$ is an
$(n,d)$-expander.

They showed that if the $(1:b)$ Maker-Breaker expander game is played on an
$(n,15bd\log n)$-expander, then Maker can always secure all edges of an
$(n,d)$-expander.

######  Theorem 1.16.

[25] There exists an absolute constant $n_{0}\in\mathbb{N}$ such that the
following statement holds. Let $n,b\in\mathbb{N}$ and $d\in\mathbb{R}$ satisfy
$n\geq n_{0}$ and $d\geq 3$. Then the $(1:b)$ Maker-Breaker $(n,d)$-expander
game is Maker’s win on every $(n,15bd\log n)$-expander.

Similarly they formulated a _Maker-Breaker Tree-Universality Game_ in which
Maker tries to claim a subset of the edges $F\subseteq E(G)$ such that the
subgraph $(V(G),F)$ is $\mathcal{T}(n,\Delta)$-universal. Using the tree-
universality result in Theorem 1.8, they obtained the following corollary.

######  Corollary 1.17.

[25] There exists an absolute constant $C>0$ such that the following statement
holds. Let $n,\Delta,b\in\mathbb{N}$ satisfy $\Delta\geq\log n$. Then the
$(1:b)$ Maker-Breaker $\mathcal{T}(n,\Delta)$-universality game is Maker’s win
on every $(n,d)$-expander with $d\geq Cb\Delta n^{2/3}\log n$.

Combining Theorems 1.10, 1.11 and 1.16, we improve the bound on the expansion
as follows.

######  Corollary 1.18.

There exists an absolute constant $C>0$ such that the following statement
holds. Let $n,\Delta,b\in\mathbb{N}$ satisfy $\Delta\geq\log n$. Then the
$(1:b)$ Maker-Breaker $\mathcal{T}(n,\Delta)$-universality game is Maker’s win
on every $(n,d)$-expander with $d\geq\min\\{\Delta n^{1/2},\Delta^{5\sqrt{\log
n}}\\}Cb\log n$.

###  1.4. Technical Contribution

Our approach builds on previously known ones but also introduces new twists. A
crucial new idea is the _reconstruction of tree array_ (see Definition 3.7 and
Lemma 3.8), which allows us to reconstruct local parts of the almost spanning
tree so that we can embed a specific set of vertices of the tree to a (small)
vertex set with good expansion property. In particular, this is also the
bottle-neck of the current proof, that is, the expansion property required in
our proof comes from the need of reconstruction of paths of length $\sqrt{\log
n}$, which can be understood as our requirement on the radius of the host
graph. Although the idea is natural, we are not aware of similar treatments in
the literature. Finally, we expect that the techniques developed here will
find other applications in related problems, in particular, in embedding
(connected) spanning substructures.

###  1.5. Basic notation

Given a graph $G$ and two vertex sets $A,B\subseteq V(G)$, we define
$\Gamma_{G}(A):=\bigcup_{v\in A}N_{G}(v)$ and $N_{G}(A):=\Gamma(A)\setminus
A$. We write $N_{G}(A,B)=N_{G}(A)\cap B$ and for a vertex $v$, let
$d_{G}(v,B)=|N_{G}(v)\cap B|$. Throughout the paper, we will often omit the
subscript term $G$ to ease the notation, unless otherwise stated.

For $d,h\in\mathbb{N}$, a $d$_-ary_ tree _of height_ $h$ is a rooted tree in
which every non-leaf vertex has $d$ children and every leaf is of distance
exactly $h$ from the root. Given a tree $T$, let $T^{\prime}$ be a subtree
obtained by removing all leaves in $T$. A _pendant star_ in $T$ is a maximal
star centered at a leaf vertex of $T^{\prime}$, and the unique neighbour of
the center in $T^{\prime}$ is the _root_ of the pendant star (see Figure 1). A
path $P$ in $T$ is a _bare_ path if all internal vertices of $P$ have degree
exactly two in $T$. A _caterpillar_ in $T$ consists of a bare path in
$T^{\prime}$ as the _central_ path and a (possibly empty) set of leaves in $T$
attached to internal vertices of the central path, where _branching_ vertices
are the internal vertices attached with at least one leaf and we call each
such leaf a _leg_. Moreover, the _length_ and _ends_ of a caterpillar refer to
the length and ends of the corresponding central path, respectively. Given a
path $P$ and two distinct vertices $a,b\in V(P)$, denote by $P(a,b)$ the
subpath that connects $a$ and $b$ in $P$.

Given two graphs $H,G$, an embedding of $H$ in $G$ is an injective mapping
$\phi:V(H)\rightarrow V(G)$ such that $\\{\phi(u),\phi(v)\\}\in E(G)$ for
every edge $uv\in E(H)$. We often use $\phi|_{H}$ to denote an embedding of
$H$ (in $G$).

##  2\. Outline of the proofs

In this section we give an outline of our proofs, and compare with previous
approaches. Firstly, what is common for previous proofs [25, 33, 38] is to
distinguish the trees according to the number of leaves. The following key
observation is due to Krivelevich [33].

######  Lemma 2.1.

[33] For any integers $n,k>2$, an $n$-vertex tree either has at least
$\frac{n}{4k}$ leaves or a collection of at least $\frac{n}{4k}$ vertex
disjoint bare paths each of length $k$.

Based on this fact, previous approaches distinguish the trees in
$\mathcal{T}(n,\Delta)$ into two classes. If a tree $T$ has many leaves, then
we remove these leaves and obtain a subtree $T^{\prime}$. The subtree
$T^{\prime}$ can be embedded in the host graph by almost-spanning tree
embedding results (e.g. Theorem 1.9), and then the leaves of $T$ can be
further embedded to the remaining vertices by matching-based arguments.

We first outline the proof of Theorem 1.8 in [25]. The proof of Theorem 1.8
uses another version of Lemma 2.1, that is, $T$ either has many leaves, or has
_one_ long bare path. The authors of [25] actually went one step further,
namely, they further distinguished the _many-leave_ case into two cases
depending on $T^{\prime}$ – either $T^{\prime}$ has a long bare path, or
$T^{\prime}$ has many leaves. Then the three cases are solved by different
methods. In particular, they used a result on Hamiltonian-connectedness to
embed long bare path (after embedding $T^{\prime}$).

Montgomery’s proof of Theorem 1.1 in [38] is far more sophisticated, when
dealing with the _many-bare-path_ case. In fact, for random graphs, in [7]
Alon Krivelevich and Sudakov already observed that one can obtain spanning
tree embeddings for trees with many leaves, by first applying their result on
almost spanning trees and then using a Hall-type matching argument to embed
the leaves of $T$. This is easily done by the _multi-round exposure_
technique, as one can reveal new random edges. However, the case when $T$ has
many (long) bare paths is significantly more challenging. Montgomery developed
a novel method, _absorption using bipartite template_ , to complete the
embedding of a disjoint union of (bare) paths, which we shall use as well in
our proof. This new method has found many applications in embedding problems
in sparse graphs and hypergraphs.

Now we discuss briefly on our proof ideas. In fact, for the many-bare-path
case we could follow the embedding strategy (and some of the results) of
Montgomery. However, since we do not work with random graphs, the many-leave
case is no longer free (modulo the almost spanning tree embedding results),
and in fact becomes challenging. Indeed, using a result of [25], one can
partition the graph $G$ into multiple blocks while reserving the expansion
property in each block (i.e., $G$ expands into each block). Thus, letting $C$
be the leaves of $T$ and $B$ be the set of the parents of $C$, one can embed
$T-C$ by an embedding $\phi$ in a (huge) block of $G$ so that what is left for
the image of $C$ is a block $V^{\prime}$ with good expansion property (namely,
$G$ expands into $V^{\prime}$). However, this “one-sided” expansion is too
weak for us to establish a star-matching result on the bipartite graph
$G[\phi(B),V^{\prime}]$. The hope is to strengthen the embedding $\phi$ so
that $\phi(B)$ also enjoys a good expansion property and thus the matching-
type result can be applied to $G[\phi(B),V^{\prime}]$. To achieve this, it is
natural to check $T^{\prime}$ similarly as in [25] and split into further
cases.

######  Corollary 2.2 (first-round deletion).

For any integers $n,\Delta,k>2$, an $n$-vertex tree
$T\in\mathcal{T}(n,\Delta)$ either has at least $\frac{n}{4k\Delta}$ pendant
stars or a collection of at least $\frac{n}{4k\Delta}$ vertex disjoint
caterpillars each of length $k$.

Figure 1.

This actually gives threes cases (recall that $T^{\prime}$ denotes the subtree
obtained by removing all leaves of $T$):

  1. (1)

the many-bare-path case ($T$ has many bare paths),

  2. (2)

the many-pendant-star case (both $T$ and $T^{\prime}$ have many leaves), and

  3. (3)

the many-caterpillar case ($T$ has many leaves but $T^{\prime}$ does not).

As mentioned above, (1) can be treated by the method of Montgomery, while (2)
and (3) need new ideas. The novel part of our approach lies in the
construction of the almost spanning tree, so that roughly speaking (a large
set of) the leaves of $T^{\prime}$ can be embedded to a block enjoying
expansion property (and then a matching-type argument can embed the leaves of
$T$ to the remaining vertices of $G$). Let $B^{\prime}$ be the set of the
leaves of $T^{\prime}$ and $A$ be the set of the parents of $B^{\prime}$. Then
choose $B\subseteq B^{\prime}$ such that $|B|=|A|$ and vertices of $B$ have
distinct parents, namely, $T[A\cup B]$ is a matching. Let $C$ be the set of
leaves incident to $B$. We start with a random partition of $V(G)$ into three
blocks $V_{1},V_{2},V_{3}$, of size

$|V_{1}|=n-|B|-|C|+22\Delta m,\quad|V_{2}|=|B|\quad\text{ and
}\quad|V_{3}|=|C|-22\Delta m,$

where $m=n/2d$ (recall that every $(n,d)$-expander is $m$-joined). We first
find an embedding $\phi$ that maps $T^{\prime}=T-(B\cup C)$ to $V_{1}$ by
Theorem 1.9, with a leftover of $22\Delta m$ vertices. Next we try to match
$\phi(A)$ and $V_{2}$, which, if successful, would embed $B$ to $V_{2}$ which
has good expansion property. However, this is asking for a _perfect matching_
between $\phi(A)$ and $V_{2}$, and as we only have one-sided expansion
property, this may not be possible (actually, this is by the same reason why
we cannot finish the final star-matching mentioned before). Now, a quick
solution is to enlarge $V_{2}$ by part of $V_{3}$, so that the desired
matching only covers $\phi(A)$ and is not perfect. More precisely, let
$V_{2}^{\prime}$ be obtained from adding $m$ vertices of $V_{3}$ to $V_{2}$.
Since $G$ is $m$-joined, it is easy to find a matching in
$G[\phi(A),V_{2}^{\prime}]$ that covers $\phi(A)$. Now what we want is that
the expansion property from $V_{3}$ to $V_{2}$ is not too much damaged, which
can be guaranteed if $m=o(\frac{d}{n}|B|)$. This strategy leads to a condition
$d=\Theta(\Delta\sqrt{n})$. Indeed, this (with some technical work) is enough
for establishing Theorem 1.10.

To prove Theorem 1.11, we need a more complex approach. Note that we can find
a maximum matching $M$ in $\phi(A)$ and $V_{2}$. It may not be perfect, but by
the $m$-joinedness, there are less than $m$ unmatched vertices on both sides.
Then a naïve idea is to replace the vertices in $\phi(A)$ as follows. For
$v\in\phi(A)\setminus V(M)$, we search for a path of length two from its
parent to $V_{2}\setminus V(M)$, whose internal vertex is from $V_{3}$. This
path would be almost impossible to find – because of its short length. What we
actually do is to try to find a much longer path (indeed, of length
$h:=\sqrt{\log n}$). To make sure the distance of $v$ and its ancestor is
large enough, at the beginning of the proof, we apply Lemma 2.1 to $T_{h}$, a
tree obtained from $T$ by recursively removing all leaves $h$ times. First
assume that $T_{h}$ has many leaves. We redefine $B$ and $C$ such that
vertices of $B$ have distinct ancestors with distance $h$, and denote the set
of their ancestors by $A_{h}$, and $C$ is defined as the leaves of $T$ in
$N(B)$. Then the first step is to embed $T-(B\cup C)$ in a block of $G$. When
embedding $B$, we first find a maximum matching $M$ between $\phi(A)$ and
$V_{2}$. Set $A_{h}^{\prime}\subseteq A_{h}$ be the set of ancestors of
vertices in $\phi(A)\setminus V(M)$ and we try to connect vertices of
$A_{h}^{\prime}$ and $V_{2}\setminus V(M)$, by vertex-disjoint paths of length
$h-1$, using part of vertices of $V_{3}$ (reserved for this connection). After
the connection is done, we also need to rebuild the pendant trees rooted at
these paths (they were embedded by $\phi$ but just discarded, see Figure 2).
After the reconstruction of the pendant trees, $B$ is completely embedded to
$V_{2}$. Now a matching-type argument finishes the embedding of $T$. Second
assume that $T_{h}$ has many bare paths. If e.g. half of these paths are also
bare paths in $T$, then we can follow Montgomery’s approach. Otherwise, half
of these paths have pendant trees rooted at their internal vertices. There are
two further subcases: i) a quarter of the paths have the pendant trees have
height at least two; ii) a quarter of the paths are caterpillars. For i), we
shall first embed the subtree obtained from $T$ excluding pendant stars (one
star for each path). For ii), we first embed the subtree of $T$ with those
caterpillars removed. In both cases, to finish the embedding, a similar (and
slightly more complicated) reconstruction scheme works so that we can embed
the centers of the stars or the roots of the “first” legs of all caterpillars
to a block with expansion property, leaving the final star-matching possible
to achieve.

##  3\. Preliminaries

In this section we collect various tools which have been used in previous
works [23, 25, 33, 38] on embedding (almost) spanning trees, and also present
some new results to aid our embedding.

###  3.1. Random partition of expanders

The following result of Johanssen, Krivelevich and Samotij
[25] allows us to partition our expander into small expanders. For our
convenience, we give a slightly stronger version of their result, whose proof
identically follows from that of Lemma 3.4 in [25].

######  Lemma 3.1.

[25, Lemma 3.4] There exists an absolute constant $n_{0}\in\mathbb{N}$ such
that the following statement holds. Let $k,n\in\mathbb{N}$ and
$d\in\mathbb{R}^{+}$ satisfy $n\geq n_{0}$ and $k\leq\log n$. Furthermore, let
$n,n_{1},\ldots,n_{k}\in\mathbb{N}$ satisfy $n=n_{1}+\ldots+n_{k}$ and let
$d_{i}:=\frac{n_{i}}{5n}d$ satisfy $d_{i}\geq 2\log n$ for all
$i\in\\{1,\ldots,k\\}$. Then, for any graph $G$ which $d$-expands into a
vertex set $W$, with $|W|=n$, the set $W$ can be partitioned into $k$ parts
$W_{1},\ldots,W_{k}$ of sizes $n_{1},\ldots,n_{k}$ respectively, such that $G$
$d_{i}$-expands into $W_{i}$ for every $i\in[k]$.

###  3.2. Building star-matchings

We will use two results on matchings and here we first give a notion of
generalized matching as follows.

######  Definition 3.2.

Given a bipartite graph $G=(A,B,E)$ and an function $f:A\rightarrow\mathbb{N}$
with $\sum_{u\in A}f(u)=|B|$, an $f$-_matching from_ $A$ _into_ $B$ is a
collection of vertex-disjoint stars $\\{S_{u}:u\in A\\}$ in $G$ such that
$S_{u}$ has $u$ as the center and exactly $f(u)$ leaves inside $B$.

More often we call such an $f$-matching a star-matching. The following two
results give sufficient conditions on the existence of star-matchings.

######  Lemma 3.3.

[25, Lemma 3.10] Let $d,m\in\mathbb{N}$ and $G$ be a graph. Suppose that two
disjoint sets $A,B\subseteq V(G)$ satisfy the following conditions:

  1. $(1)$

$|N_{G}(X)\cap B|\geq d|X|$ for all $X\subseteq A$ with $1\leq|X|\leq m$;

  2. $(2)$

$e_{G}(X,Y)>0$ for all $X\subseteq A,Y\subseteq B$ with $|X|=|Y|=m$.

  3. $(3)$

$|N_{G}(w)\cap A|\geq m$ for all $w\in B$.

Then, for every $f:A\rightarrow\\{1,\ldots,d\\}$ with $\sum_{u\in A}f(u)=|B|$,
there exists an $f$-matching from $A$ into $B$.

######  Lemma 3.4.

Let $d,m\in\mathbb{N}$ and $G$ be a graph. Suppose that two disjoint sets
$A,B\subseteq V(G)$ satisfy that

  1. $(1)$

$|N_{G}(X)\cap B|\geq d|X|,N_{G}(Y)\cap A|\geq d|Y|$ for all $X\subseteq
A,Y\subseteq B$ with $1\leq|X|,|Y|\leq m$;

  2. $(2)$

$e_{G}(X,Y)>0$ for all $X\subseteq A,Y\subseteq B$ with $|X|=|Y|=m$

Then, for every $f:A\rightarrow\\{1,\ldots,d\\}$ with $\sum_{u\in A}f(u)=|B|$,
there exists an $f$-matching from $A$ into $B$.

###### Proof.

To build a desired star-matching, we shall show a generalized Hall’s condition
(see, e.g., Bollobás [12])), that is,

$\displaystyle|N(X)\cap B|\geq\sum_{v\in X}f(v)\leavevmode\nobreak\ \text{for
every}\leavevmode\nobreak\ X\subseteq A.$ (3.1)

From the assumption that every set $X$ of at most $m$ vertices in $A$ has at
least $d|X|$ neighbors in $B$, we know that (3.1) holds when $|X|\leq m$. It
remains to consider the following two cases depending on the size of $|X|$:

  * •

$m<|X|\leq|A|-m$: By the assumption $(2)$ and $|B|=\sum_{v\in A}f(v)$, we have

$|N(X)\cap B|>|B|-m\geq\sum_{v\in A}f(v)-\sum_{v\in A\setminus
X}f(v)=\sum_{v\in X}f(v),$

where the second inequality follows as $m\leq|A|-|X|\leq\sum_{v\in A\setminus
X}f(v)$.

  * •

$|A|-m<|X|\leq|A|$: Let $T:=B\setminus N(X)$. We may assume that
$T\neq\emptyset$ for otherwise we are done. As there is no edge between $X$
and $T$, we obtain that $|T|<m$ and $N(T)\cap A\subseteq A\setminus X$. Then
it follows by assumption that $d|T|\leq|N(T)\cap A|\leq|A\setminus
X|\leq\sum_{v\in A\setminus X}f(v)$. Thus we have

$|N(X)\cap B|=|B|-|T|=\sum_{v\in X}f(v)+\sum_{v\in A\setminus
X}f(v)-|T|>\sum_{v\in X}f(v).$

In all cases, condition (3.1) holds and this yields a desired star-matching
covering $A\cup B$. ∎

###  3.3. Connecting pairs of vertices in expanding graphs

The following two results are used to build a family of vertex-disjoint paths
each connecting a prescribed pair of vertices whilst covering all the fixed
vertices.

######  Theorem 3.5.

[37] Let $n$ be sufficiently large and let $\ell\in\mathbb{N}$ satisfy
$\ell\geq 10^{3}\log^{2}n$ and $\ell|n$. Let a graph $G$ contain $n/\ell$
disjoint vertex pairs $(x_{i},y_{i})$ and let
$W=V(G)\setminus(\cup_{i}\\{x_{i},y_{i}\\})$. Suppose $G$ $d$-expands into
$W$, where $d=10^{10}\log^{4}n/\log\log n$. Then we can cover $G$ with
$n/\ell$ disjoint paths $P_{i}$, each of length $\ell-1$, so that, for each
$i$, $P_{i}$ is an $(x_{i},y_{i})$-path.

######  Theorem 3.6 (Path-cover).

There exists $C>0$ such that the following holds for any integer $\ell\geq
200$ and sufficiently integer $n$ with $\ell|n$. Suppose an $n$-vertex graph
$G$ contains $n/\ell$ disjoint vertex pairs $(x_{i},y_{i}),i\in[n/\ell]$ and
let $W=V(G)\setminus(\cup_{i}\\{x_{i},y_{i}\\})$. If $G$ $d$-expands into $W$
with $d=C\ell\sqrt{n}$, then we can cover $G$ with $n/\ell$ disjoint paths
$P_{i}$, each of length $\ell-1$, so that, for each $i$, $P_{i}$ is an
$(x_{i},y_{i})$-path.

We also need a technical lemma which will be used to (re)construct a forest in
the proof of Theorem 1.11. We first introduce a notion of tree array.

######  Definition 3.7 (Tree array).

Given a graph $G$, a subset of vertices $W$, a collection $\mathcal{I}$ of
disjoint pairs of vertices from $V(G)\setminus W$ and integers $s,\Delta$, we
call that $G$ contains a $(W,\mathcal{I},s,\Delta)$_-tree array_ if there
exist

  * •

a family $\mathcal{P}=\\{P_{xy}:(x,y)\in\mathcal{I}\\}$ of mutually vertex-
disjoint paths each of length $s$, where the internal vertices of all paths
$P_{xy}$, denoted as $\mathsf{Int}(\mathcal{P})$, lie inside $W$;

  * •

a family $\\{T_{v}\\}_{v\in\mathsf{Int}(\mathcal{P})}$ of mutually vertex-
disjoint rooted trees inside $W$, such that for every path $P_{xy}$ and every
internal vertex $v$, $T_{v}$ is a $\Delta$-ary tree rooted at $v$ with height
$s$, which is vertex disjoint from $V(\mathcal{P})\setminus\\{v\\}$.

######  Lemma 3.8.

For all $s,t,m,d_{1},\Delta\in\mathbb{N}$ with $d_{1}\geq\Delta+2$ and $s\geq
2\lceil\frac{\log 2m}{\log(d_{1}-1)}\rceil+1$, let $G$ be an $m$-joined graph
and $W\subseteq V(G)$. If $G$ $d_{1}$-expands into $W$ and
$|W|>10d_{1}m+t(s+1)\Delta^{s+1}$, then for every family $\mathcal{I}$ of at
most $t$ disjoint pairs of vertices from $V(G)\setminus W$, $G$ contains a
$(W,\mathcal{I},s,\Delta)$-tree array.

######  Corollary 3.9.

For sufficiently large $n\in\mathbb{N}$ and $d,\Delta\in\mathbb{N}$ with
$n>d\geq\Delta^{5\sqrt{\log n}}$, let $G$ be an $m$-joined graph with

$m\leq\frac{n}{2d}$

and $W$ be a set of at least $\frac{n}{\sqrt{d}}$ vertices in $G$. If $G$
$\Delta^{2\sqrt{\log n}}$-expands into $W$, then for every $s\in[\sqrt{\log
n}-1,2\sqrt{\log n}-1]$ and every family $\mathcal{I}$ of at most $m$ disjoint
pairs of vertices from $V(G)-W$, $G$ contains a
$(W,\mathcal{I},s,\Delta)$-tree array.

###### Proof.

Let $h=\sqrt{\log n}$ and $d_{1}=\Delta^{2h}$. Then $G$ $d_{1}$-expands into
$W$ and $|W|\geq\frac{n}{\Delta^{5h/2}}$. Note that $s\in[h-1,2h-1]$ and

$2\left\lceil\frac{\log 2m}{\log(d_{1}-1)}\right\rceil+1\leq
2\left\lceil\frac{h^{2}-\log\Delta^{5h}}{\log(\Delta^{2h}-1)}\right\rceil+1\leq
h-1.$

Since $n$ and also $h$ are sufficiently large, we have that

$10d_{1}m+m(s+1)\Delta^{s+1}\leq\frac{n}{\Delta^{5h}}(10\Delta^{2h}+10+2h\Delta^{2h})\leq\frac{n}{\Delta^{3h}}(2h+11)\leq\frac{n}{\Delta^{5h/2}}\leq|W|.$

We can apply Lemma 3.8 with $t=m$ to obtain a desired
$(W,\mathcal{I},s,\Delta)$-tree array. ∎

##  4\. Proof of Theorem 1.11

In this section, we prove Theorem 1.11. Throughout the proof, we write

$\displaystyle h=\lceil\sqrt{\log n}\rceil\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ k=\lceil\log^{3}n\rceil.$ (4.1)

Moreover, we may take

$\displaystyle d=\Delta^{5\sqrt{\log n}},\leavevmode\nobreak\
m:=\frac{n}{2d}\leq\frac{n}{2\Delta^{5h-5}}$ (4.2)

and fix $G$ to be an $(n,d)$-expander. Then $G$ is $m$-joined.

Given a tree $T\in\mathcal{T}(n,\Delta)$, we write $T_{0}:=T$ and $T_{i}$ for
the subtree of $T_{i-1}$ obtained by removing all leaves in $T_{i-1}$, where
$i\in[h]$. Let $L_{i}$ be the set of all leaves in $T_{i}$ and
$n_{i}:=|V(T_{i})|,i\in\\{0,1,\ldots,h\\}$. Then it is easy to show that
$n_{i}(1+\Delta+\ldots+\Delta^{i})\geq n$ for every $i\in[h]$. In particular,

$\displaystyle n_{h}\geq\frac{n}{\Delta^{h+1}}.$ (4.3)

The proof of Theorem 1.11 is split into two cases depending on the structure
of subtree $T_{h}$.

###  4.1. $T_{h}$ has many leaves

We first consider the case when $T_{h}$ has a set $L_{h}$ of at least
$n_{h}/4k$ leaves. Note that by definition, for every $u\in L_{h}$, there
exists a choice $f(u)\in L_{1}$ which is of distance exactly $h-1$ from $u$
(we choose an arbitrary one if there are more than one choice). Let
$B\subseteq\\{f(u):u\in L_{h}\\}$ be a set of exactly $n_{h}/4k$ vertices and
$C\subseteq L_{0}$ be the set of descendants of vertices in $B$. Denote by
$A_{2}$ the neighborhood of $B$ inside $L_{2}$ and for every $i=3,4,\ldots,h$,
let $A_{i}$ be the neighborhood of $A_{i-1}$ inside $L_{i}$. Then it is easy
to see that $|A_{i}|=|B|=n_{h}/4k$ for every $i=2,3,\ldots,h$.

Let $T^{\prime}:=T-B\cup C$. Now our proof proceeds in the following steps.

Figure 2. The red trees have height at most $h$ and would be replaced by the
green paths attached with gray subtrees inside $V_{3}$.

Phase $0$. Partition $V(G)$. We first randomly partition $V(G)$ into four
parts $V_{1},V_{2},V_{3},V_{4}$ such that

$\displaystyle|V_{1}|=n-|B|-|C|+22\Delta m,\leavevmode\nobreak\
|V_{2}|=|B|\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
|V_{3}|=|V_{4}|=\frac{|C|}{2}-11\Delta m.$ (4.4)

We can easily check that

$\displaystyle|V_{2}|=|B|=\frac{n_{h}}{4k}\overset{\eqref{eq2}}{\geq}\frac{n}{4k\Delta^{h+1}}\overset{\eqref{eq11}}{\geq}\frac{n}{\sqrt{d}},$
(4.5) $\displaystyle|V_{3}|=|V_{4}|=\frac{|C|}{2}-11\Delta
m\geq\frac{|B|}{2}-11\Delta
m\geq\frac{n}{\Delta^{2h}}-11\Delta\frac{n}{2\Delta^{5h-5}}\overset{\eqref{eq11}}{\geq}\frac{n}{\sqrt{d}},$
(4.6) $\displaystyle|V_{1}|=n-|B|-|C|+22\Delta
m>\sum_{i=2}^{h}|A_{i}|=(h-1)|B|\overset{\eqref{eq31}}{>}\frac{n}{\sqrt{d}}.$
(4.7)

Since $G$ is an $(n,d)$-expander and

$\displaystyle
d_{i}:=\frac{|V_{i}|}{5n}d\geq\frac{\sqrt{d}}{5}>\max\\{\Delta^{2\sqrt{\log
n}},2\log n\\}\leavevmode\nobreak\ \text{for every}\leavevmode\nobreak\
i\in[4],$ (4.8)

by Lemma 3.1 applied to $G$ with $W=V(G)$, there exists such a partition with
the following property:

  1. (A1)

$G$ $d_{i}$-expands into $V_{i}$ for all $i\in[4]$.

Phase $1$. Embed $T^{\prime}$ in $G[V_{1}]$. By property (A1), we can apply
Theorem 1.9 to $G[V_{1}]$ to find an embedding $\phi|_{T^{\prime}}$ that maps
$T^{\prime}$ to $V_{1}$. Indeed, as $d_{1}\geq 2\Delta$ in (4.8), it suffices
to ensure that the order of $T^{\prime}$ is no larger than
$|V_{1}|-4\Delta\lceil\frac{|V_{1}|}{2d_{1}}\rceil$. This easily follows from
(4.7) that

$|V_{1}|-|T^{\prime}|=22\Delta
m\overset{\eqref{eq11}}{>}4\Delta\left\lceil\frac{5n}{2d}\right\rceil=4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil.$

Phase $2$. Embed $B$ into $V_{2}$. We first build a maximal matching $M$
between $\phi(A_{2})$ and $V_{2}$. Denote by $A_{2}^{\prime},B_{2}$ the sets
of vertices in $\phi(A_{2})$ and $V_{2}$, respectively, that are not covered
by $M$. Since $G$ is $m$-joined, we have

$|A_{2}^{\prime}|=|B_{2}|<m.$

In order to finish the embedding of $B_{2}$, we shall first prune subtrees and
then regrow them by using tree arrays. For each $i\in[3,h]$, let
$A_{i}^{\prime}$ be the set of vertices in $\phi(A_{i})$ which are ancestors
of vertices in $A_{2}^{\prime}$ (see Figure 2). Moreover, for every $v\in
A_{2}^{\prime}$ and its ancestor $u\in A_{h}^{\prime}$, denote by $P_{u,v}$
the unique $(u,v)$-path in $\phi|_{T^{\prime}}$. Then all these $P_{u,v}$ are
pairwise disjoint and the removal of $\cup_{v\in A_{2}^{\prime}}E(P_{u,v})$
from $\phi|_{T^{\prime}}$ would yield a family of disjoint trees $T_{x}$ with
root $x\in\cup_{i=2}^{h-1}A^{\prime}_{i}$, each of height at most $h-1$.

Let $\mathcal{I}$ be a family of $|A_{2}^{\prime}|$ disjoint ordered pairs
$(u,w)\in A_{h}^{\prime}\times B_{2}$ of vertices. Note that we have

$d_{3}\geq\Delta^{2\sqrt{\log n}},\leavevmode\nobreak\
|V_{3}|\geq\frac{n}{\sqrt{d}}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |\mathcal{I}|<m$

by (4.6) and (4.8). Then by property (A1) and Corollary 3.9 with $s=h-1$ and
$W=V_{3}$, we obtain a $(V_{3},\mathcal{I},h-1,\Delta)$-tree array. Then one
can obtain an embedding $\phi|_{T-C}$ from $\phi|_{T^{\prime}}$ by

  1. (B1)

first deleting all vertices in $A_{h-1}^{\prime}$ and their descendants (in
$\phi|_{T^{\prime}}$, the trees in red in Figure 2);

  2. (B2)

then connecting all pairs $(u,w)\in\mathcal{I}$ via vertex-disjoint paths
$Q_{u,w}$ each of length $h-1$; and at every vertex $z\in
V(Q_{u,w})\setminus\\{u\\}$, we regrow a desired copy of $T_{x}$ for some
$x\in V(P_{u,v})\setminus\\{u\\}$.

Observe that such paths $Q_{u,w}$ and trees in (B2) can be easily obtained
from the $(V_{3},\mathcal{I},h-1,\Delta)$-tree array (by taking subtrees from
$\Delta$-ary trees if necessary).

Hence it remains to embed $C$ into the remaining set $L$ of vertices with
$L=V(G)-\phi(T-C)$.

Phase $3$. Build a star-matching between $V_{2}$ and $L$.

To finish the embedding of $T$, we define an auxiliary function
$f:V_{2}\rightarrow[\Delta]$ by taking $f(v)=d_{T}(\phi^{-1}(v))-1$, that is,
the number of leaves we need to attach to every $v\in V_{2}$. Then
$|L|=|C|=\sum_{v\in V_{2}}f(v)$. Note that $V_{4}\subseteq L$ and by property
(A1), we observe that for every $X\subseteq L$ with $|X|\leq
m<\frac{5n}{2d}=\frac{|V_{2}|}{2d_{2}}$,

$|N_{G}(X,V_{2})|\geq d_{2}|X|\overset{\eqref{eq34}}{\geq}\Delta|X|$

and similarly $|N_{G}(Y,L)|\geq|N_{G}(Y,V_{4})|\geq d_{4}|Y|\geq\Delta|Y|$ for
every $Y\subseteq V_{2}$ with $|Y|\leq m$. By Lemma 3.4 with $A=V_{2},B=L$, we
obtain a desired $f$-matching, which together with $\phi|_{T-C}$ completes an
embedding of $T$.

###  4.2. $T_{h}$ has many long bare paths

In this section, we consider the case when $T_{h}$ has
$\lfloor\frac{n_{h}}{4k}\rfloor$ vertex-disjoint bare paths, say
$P_{i},i\in\lfloor\frac{n_{h}}{4k}\rfloor$ each of length
$k=\lceil\log^{3}n\rceil$. Let $x_{i},y_{i}$ be the ends of $P_{i}$, for every
$i\in\lfloor\frac{n_{h}}{4k}\rfloor$. Let $Q_{i}\subseteq P_{i}$ be a subpath
of length $k-4h$, with each of ends of distance exactly $2h$ from $x_{i}$ and
$y_{i}$, respectively. Given an internal vertex $v\in V(Q_{i})$, we say
$Q_{i}$ _sees_ a pendant star $S$ _from_ $v$ in $T$ if there is a path in
$T\setminus Q_{i}$ connecting $v$ to the root of $S$. Let
$r=\lfloor\frac{n_{h}}{8k}\rfloor$. In the forthcoming subsections, we shall
consider three subcases depending on the surroundings of $Q_{i}$:

  1. Case A

at least $r$ paths $Q_{i}$ are bare in $T$;

  2. Case B

at least $r/2$ paths $Q_{i}$ form caterpillars in $T$ with at least one leg;

  3. Case C

at least $r/2$ paths $Q_{i}$ see pendant stars in $T$.

####  4.2.1. Many long bare paths $Q_{i}$ in $T$: Case A

We may assume that $Q_{1},Q_{2},\ldots,Q_{r}$ are bare paths in $T$, where
each $Q_{i}$ has ends $a_{i},b_{i}$. Let
$T^{\prime}=T-\cup_{i\in[r]}V(Q_{i}-\\{a_{i},b_{i}\\})$. Recall that every
$Q_{i}$ has length $k^{\prime}:=k-4h$. Then our embedding proceeds by first
randomly partitioning $V(G)$ into two parts $V_{1},V_{2}$ such that

$\displaystyle|V_{1}|=|T^{\prime}|+22\Delta m\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |V_{2}|=(k^{\prime}-1)r-22\Delta m.$

We can easily check that
$|V_{1}|\geq\frac{n}{2},|V_{2}|\geq\frac{n_{h}}{16}-22\Delta
m\geq\frac{n}{\sqrt{d}}$. Since $G$ is an $(n,d)$-expander and

$\displaystyle
d_{i}:=\frac{|V_{i}|}{5n}d\geq\frac{\sqrt{d}}{5}>\max\\{2\Delta,\log^{4}n\\}\leavevmode\nobreak\
\text{for every}\leavevmode\nobreak\ i\in[2],$ (4.9)

by Lemma 3.1, there exists a partition $V_{1}\cup V_{2}=V$ such that $G$
$d_{i}$-expands into $V_{i}$ for all $i\in[2]$. Based on this, we can first
apply Theorem 1.9 to $G[V_{1}]$ to find an embedding of $T^{\prime}$ inside
$V_{1}$. Indeed, it suffices to ensure that $d_{1}\geq 2\Delta$ and the order
of $T^{\prime}$ is no larger than
$|V_{1}|-4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil$. This easily
follows from (4.9) and $|V_{1}|-|T^{\prime}|=22\Delta m\geq
4\Delta\left\lceil\frac{5n}{2d}\right\rceil=4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil.$

Let $\phi|_{T^{\prime}}$ be the resulting embedding of $T^{\prime}$ and $A,B$
be the set of images of ends $a_{i},b_{i}$, respectively. Moreover, denote by
$V_{1}^{\prime}$ the set of leftover vertices not covered by
$\phi|_{T^{\prime}}$. Then $|V_{1}^{\prime}|=22\Delta m$. Now it remains to
embed the bare paths $Q_{i},i\in[r]$ in $V_{2}^{\prime}:=V_{2}\cup
V_{1}^{\prime}$. Recall that $h=\lceil\sqrt{\log n}\rceil$ and
$k=\lceil\log^{3}n\rceil$. Since $G$ $d_{2}$-expands into $V_{2}$ and
$|V_{2}^{\prime}|\leq 2|V_{2}|$, one can easily obtain that $G$ actually
$\frac{d_{2}}{2}$-expands into $V_{2}^{\prime}$. As $d_{2}\geq\log^{4}n$ and
$k^{\prime}=k-4h\geq 10^{3}\log^{2}n$, such a collection of vertex-disjoint
paths can be obtained by Theorem 3.5 applied to $G[A\cup B\cup V_{2}]$ with
$(d_{2},k^{\prime}+1,(k^{\prime}+1)r,V_{2})$ in place of $(d,\ell,n,W)$, which
together with $\phi|_{T^{\prime}}$ completes the embedding of $T$.

####  4.2.2. Many long caterpillars in $T$: Case B

Without loss of generality, we may assume that the subpaths $Q_{i}\subseteq
P_{i},1\leq i\leq r/2$, are caterpillars in $T$ with at least one leg. Note
that by taking induced subgraphs and renaming, we may further assume that each
$Q_{i}$ has length $k^{\prime}:=\lceil\frac{k-4h}{2}\rceil$ and we can write
$Q_{i}=a_{0}^{i}a_{1}^{i}\ldots a_{k^{\prime}}^{i}$ so that $a_{1}^{i}$ is
attached with at least one leg. Denote by $A_{j},j=0,1,\ldots,k^{\prime}$ the
set of the vertices $a_{j}^{i}$ taken over all paths $Q_{i},1\leq i\leq r/2$.
Moreover we write $L$ for the set of leaves of $T$ that are adjacent to
vertices in $\bigcup_{j=1}^{k^{\prime}-1}A_{j}$. Furthermore, we write
$L^{+}:=N_{T}(L)$. Then $A_{1}\subseteq L^{+}$ and
$|L|\geq|L^{+}|\geq|A_{1}|=r/2$.

Let $T^{\prime}:=T-\bigcup_{j=1}^{k^{\prime}-1}A_{j}\cup L$. Now our embedding
proceeds as follows.

Figure 3. The red part is pruned and then used for building a star-matching

Phase $0$. Partition $V(G)$.
We first randomly partition $V(G)$ into five parts
$V_{1},V_{2},V_{3},V_{4},V_{5}$ (see Figure 3) such that

$\displaystyle|V_{2}|=|A_{1}|=r/2,\leavevmode\nobreak\
|V_{4}|=(k^{\prime}-2)|V_{2}|\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |V_{3}|=|V_{5}|=\frac{|L|}{2}-11\Delta m.$
(4.10)

By (4.3) and the fact that $|L|\leq\Delta(|V_{2}|+|V_{4}|)$, we can easily
check that

$\displaystyle|V_{2}|=r/2\geq\lfloor\frac{n_{h}}{16k}\rfloor\geq\frac{n}{16k\Delta^{h+1}}\geq\frac{n}{\sqrt{d}},$
$\displaystyle|V_{3}|=|V_{5}|=\frac{|L|}{2}-11\Delta
m\geq\frac{1}{2}\lfloor\frac{n_{h}}{16k}\rfloor-11\Delta
m\geq\frac{n}{\sqrt{d}},$ (4.11)
$\displaystyle|V_{1}|=n-|V_{2}|-|V_{3}|-|V_{4}|-|V_{5}|=n-|T^{\prime}|+22\Delta
m>|A_{0}|=r/2\geq\frac{n}{\sqrt{d}}.$

Since $G$ is an $(n,d)$-expander and

$\displaystyle
d_{i}:=\frac{|V_{i}|}{5n}d\geq\frac{\sqrt{d}}{5}>\max\\{\Delta^{2\sqrt{\log
n}},\log^{4}n\\}\leavevmode\nobreak\ \text{for every}\leavevmode\nobreak\
i\in[5],$ (4.12)

by Lemma 3.1, there exists such a partition
$\\{V_{1},V_{2},V_{3},V_{4},V_{5}\\}$ with the following property:

  1. (C1)

$G$ $d_{i}$-expands into $V_{i}$ for all $i\in[5]$.

Phase $1$. Embed $T^{\prime}$ in $G[V_{1}]$.
By property (C1), we can apply Theorem 1.9 to $G[V_{1}]$ to find an embedding
$\phi|_{T^{\prime}}$ inside $V_{1}$. Indeed, it suffices to ensure that
$d_{1}\geq 2\Delta$ and the order of $T^{\prime}$ is no larger than
$|V_{1}|-4\Delta\lceil\frac{|V_{1}|}{2d_{1}}\rceil$. This easily follows from
(4.12) and $|V_{1}|-|T^{\prime}|=22\Delta m\geq
4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil.$

Phase $2$. Embed $A_{1}$ into $V_{2}$.
We first build a maximal matching $M$ between $\phi(A_{0})$ and $V_{2}$.
Denote by $A^{\prime}_{0},A_{1}^{\prime}$ the sets of vertices in
$\phi(A_{0})$ and $V_{2}$, respectively, that are not covered by $M$. Since
$G$ is $m$-joined, we have

$|A^{\prime}_{0}|=|A^{\prime}_{1}|<m\leq\frac{n}{2\Delta^{5h-5}}.$

In order to complete the embedding of $A_{1}$, we shall use Corollary 3.9 to
build tree arrays. For each $v\in A_{0}^{\prime}$, let $x_{v}$ be the vertex
such that $\phi^{-1}(x_{v})$ is on $P_{i}\setminus Q_{i}$ with distance $h$ to
$v$ and $X:=\\{x_{v}:v\in A_{0}^{\prime}\\}$ (see Figure 3). Let $\mathcal{I}$
be a family of $|A_{1}^{\prime}|$ disjoint pairs obtained by arbitrarily
pairing vertices between $X$ and $A_{1}^{\prime}$. Since

$|V_{3}|\geq\frac{n}{\sqrt{d}}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |\mathcal{I}|<m,$

by property (C1) and Corollary 3.9 with $s=h$ and $W=V_{3}$, we obtain a
$(V_{3},\mathcal{I},h,\Delta)$-tree array. Using the technique as in (B1)(B2),
one can obtain an embedding $\phi$ of $T-\bigcup_{j=2}^{k^{\prime}-1}A_{j}-L$
such that $\phi(A_{1})=V_{2}$.

Phase $3$. Embed $\bigcup_{j=2}^{k^{\prime}-1}A_{j}$ into $V_{4}$
Let $\mathcal{P}$ be a family of the vertex pairs
$\\{\phi(a_{1}^{i}),\phi(a_{k^{\prime}}^{i})\\}$, $1\leq i\leq r/2$. We shall
use Theorem 3.5 to construct for all pairs in $\mathcal{P}$, pairwise vertex-
disjoint paths each of length $k^{\prime}-1$ whilst covering all vertices in
$V_{4}$. Since $G$ $d_{4}$-expands into $V_{4}$ with $d_{4}>\log^{4}n$ (see
(4.12)) and $k^{\prime}\geq 10^{3}\log^{2}n$, by applying Theorem 3.5 to
$G[V_{4}\cup V(\mathcal{P})]$ with $W=V_{4}$ and $\ell=k^{\prime}$, we obtain
such a family of paths. Let $\phi|_{T-L}$ be the resulting embedding and
$R=V(G)\setminus\phi(T-L)$.

Phase $4$. Embed $L$ into $R$ via a star-matching.
Recall that $L^{+}$ is the neighborhood of $L$ in $T$. We shall build a star-
matching between $\phi(L^{+})$ and $R$. To be more precise, we define an
auxiliary function $f:\phi(L^{+})\rightarrow[\Delta]$ by taking
$f(v)=d_{T}(\phi^{-1}(v))-2$, that is, the number of leaves we need to attach
to every $v\in\phi(L^{+})$ so as to complete the embedding. Note that
$V_{5}\subseteq R,V_{2}\subseteq\phi(L^{+})$. Then it follows from (C1) that
for every $X\subseteq R$ with $|X|\leq
m<\frac{5n}{2d}=\frac{|V_{2}|}{2d_{2}}$,

$|N_{G}(X,\phi(L^{+}))|\geq|N_{G}(X,V_{2})|\geq d_{2}|X|\geq\Delta|X|$

and similarly for every $Y\subseteq\phi(L^{+})$ with $|Y|\leq m$,
$|N_{G}(Y,R)|\geq|N_{G}(Y,V_{5})|\geq d_{5}|Y|\geq\Delta|Y|$. Applying Lemma
3.4, we have a desired $f$-matching, which together with $\phi|_{T-L}$ forms
an embedding of $T$.

####  4.2.3. Many subpaths $Q_{i}$ see pendant stars in $T$: Case C

Figure 4.

Recall that $P_{i}$ is a bare paths in $T_{h}$ of length
$k=\lceil\log^{3}n\rceil$ and has endpoints $x_{i},y_{i}$ and $Q_{i}\subseteq
P_{i}$ is defined as a subpath of length $k-4h$, with each of ends of distance
exactly $2h$ from $x_{i}$ and $y_{i}$, respectively. Similarly, we may assume
that for every $1\leq i\leq r/2$, the subpath $Q_{i}$ sees at least one
pendant star, and we arbitrarily choose such a pendant star, denoted as
$S_{i}$. Accordingly, we denote by

  * •

$C$ the set of centers $c_{i}$ of pendant star $S_{i},i\in[r/2]$;

  * •

$R$ the set of roots $r_{i}$ of pendant star $S_{i},i\in[r/2]$;

  * •

$Z$ the set of vertices $z_{i}\in V(Q_{i}),i\in[r/2]$ such that $Q_{i}$ sees
$S_{i}$ from $z_{i}$;

  * •

$A$ the set of vertices $a_{i}$ inside the subpath
$P_{i}(x_{i},z_{i}),i\in[r/2]$ such that each $a_{i}$ is of distance $h-1$
from $r_{i}$;

  * •

$B$ the set of vertices $b_{i}$ inside the subpath
$P_{i}(z_{i},y_{i}),i\in[r/2]$ such that each $b_{i}$ is of distance $h$ from
$z_{i}$;

Moreover we write $C^{-}$ for the set of leaves in $T$ that are attached to
the vertices in $C$. Thus $r/2\leq|C|\leq|C^{-}|\leq(\Delta-1)|C|$. Let
$T^{\prime}:=T-(C\cup C^{-})$. Now our embedding proceeds as follows.

Phase $0$. Partition $V(G)$ into $V_{1},V_{2},V_{3},V_{4},V_{5}$.
Similar to previous arguments, there exists a partition $V(G)=V_{1}\cup
V_{2}\cup\cdots\cup V_{5}$ satisfying the following properties:

  1. (D1)

$|V_{2}|=|C|,\leavevmode\nobreak\
|V_{3}|=|V_{4}|=|V_{5}|=\frac{|C^{-}|}{3}-7\Delta m,\leavevmode\nobreak\
|V_{1}|=n-|C|-|C^{-}|+21\Delta m=|T^{\prime}|+21\Delta m$;

  2. (D2)

$G$ $d_{i}$-expands into $V_{i}$ with
$d_{i}:=\frac{|V_{i}|}{5n}d\geq\frac{\sqrt{d}}{5}>\max\\{\Delta^{2\sqrt{\log
n}},2\log n\\}$, $i\in[5]$.

Phase $1$. Embed $T^{\prime}$ in $G[V_{1}]$.
By property (D2), one can similarly apply Theorem 1.9 to $G[V_{1}]$ to find an
embedding $\phi|_{T^{\prime}}$ inside $V_{1}$. Indeed, by Theorem 1.9, it
suffices to ensure that $d_{1}\geq 2\Delta$ and the order of $T^{\prime}$ is
at most $|V_{1}|-4\Delta\lceil\frac{|V_{1}|}{2d_{1}}\rceil$, which easily
follows since $|V_{1}|-|T^{\prime}|=21\Delta
m>4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil.$

Phase $2$. Embed $C$ into $V_{2}$.
We first build a maximal matching $M$ between $\phi(R)$ and $V_{2}$. Denote by
$R^{\prime},C^{\prime}$ the sets of vertices in $\phi(R)$ and $V_{2}$,
respectively, that are not covered by $M$. Since $G$ is $m$-joined, we have
$|R^{\prime}|=|C^{\prime}|<m$. Using the same strategy as in Section 4.2.2, we
shall use Corollary 3.9 (twice) to finish the embedding of $C$. Without loss
of generality, we may write
$R^{\prime}=\\{\phi(c_{1}),\ldots,\phi(c_{m-1})\\}$,
$B^{\prime}:=\\{\phi(b_{1}),\ldots,\phi(b_{m-1})\\}$ and
$Z^{\prime}:=\\{\phi(z_{1}),\ldots,\phi(z_{m-1})\\}$. Let $\mathcal{I}$ be a
family of $m-1$ disjoint pairs obtained by arbitrarily pairing vertices
between $A^{\prime}:=\\{\phi(a_{1}),\ldots,\phi(a_{m-1})\\}$ and $C^{\prime}$
(see Figure 4). Since

$|V_{4}|\geq\frac{n}{\sqrt{d}}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |\mathcal{I}|<m,$

by property (D2) and applying Corollary 3.9 with $s=h$ and $W=V_{4}$, we
obtain a $(V_{4},\mathcal{I},h,\Delta)$-tree array. Using the pruning-
rebuilding technique as in (B1)(B2), one can find an adjustment
$\phi^{\prime}$ of $\phi|_{T^{\prime}}$ which maps every $(a_{i},c_{i})$-path
in $T$ ($i\in[m-1]$) and the corresponding subtrees attached (the red parts in
Figure 4) into $V_{4}$, where the set $\\{z_{1},z_{2},\ldots,z_{m-1}\\}$ is
instead mapped to a subset of $V_{4}$, say $D^{\prime}$. However, the current
$\phi^{\prime}$ may fail to map the other segments
$P_{i}(z_{i},b_{i}),i\in[m-1]$ (the purple parts) into paths in $G$. To
overcome this, we use Corollary 3.9 again to rebuild the paths
$P_{i}(z_{i},b_{i}),i\in[m-1]$ together with the corresponding subtrees
attached. This is similarly done by applying Corollary 3.9 with
$\mathcal{I}=\\{(\phi^{\prime}(z_{i}),\phi^{\prime}(b_{i})):i\in[m-1]\\}$ and
$W=V_{5}$, and the resulting embedding, denoted by $\phi|_{T-C^{-}}$, manages
to map $C$ into $V_{2}$.

Phase $3$. Embed $C^{-}$ via a star-matching.
Now it remains to embed $C^{-}$ into the remaining set of vertices in $V(G)$,
say $L$. Note that $V_{3}\subseteq L$ and by property (D2) it holds that for
every $X\subseteq V_{2}$ with $|X|\leq
m<\frac{5n}{2d}=\frac{|V_{3}|}{2d_{3}}$,

$|N_{G}(X,L)|\geq|N_{G}(X,V_{3})|\geq d_{3}|X|\geq\Delta|X|$

and similarly for every $Y\subseteq L$ with $|Y|\leq m$, $|N_{G}(Y,V_{2})|\geq
d_{2}|Y|\geq\Delta|Y|$. Lemma 3.4 applied to $G$ with $(V_{2},L)$ in place of
$(A,B)$, gives a star-matching in which every $v\in V_{2}$ would be connected
to $d_{T}(\phi^{-1}(v))-1$ vertices in $L$, and this combined with
$\phi|_{T-C^{-}}$ completes an embedding of $T$.

###  4.3. Tree array

We first introduce useful tools for the proof of Lemma 3.8. Glebov, Johannsen
and Krivelevich [22] recently modified Haxell’s method [23] to develop a very
flexible approach for embedding bounded degree trees. We first need a key
notion of $(d,m)$-extendable subgraph.

######  Definition 4.1.

[22, $(d,m)$-extendable] Let $d,m\in\mathbb{N}$ satisfy $m\geq 1$ and $d\geq
3$, let $G$ be a graph, and let $S\subseteq G$ be a subgraph. We say that $S$
is _$(d,m)$ -extendable_ if $S$ has maximum degree at most $d$ and

$|\Gamma_{G}(X)\setminus V(S)|\geq(d-1)|X|-\sum_{x\in X\cap V(S)}(d(x,S)-1)$

for all sets $X\subseteq V(G)$ with $|X|\leq 2m$.

The following results of Montgomery [38] give sufficient conditions under
which a $(d,m)$-extendable subgraph can be extended yet remain
$(d,m)$-extendable. This allows us to build up a collection of trees rooted at
a given set of vertices.

######  Lemma 4.2.

[38, Corollary 3.12] Let $d,m,\ell\in\mathbb{N}$ satisfy $m\geq 1$ and $d\geq
3$. Letting $k=\lceil\frac{\log(2m)}{\log(d-1)}\rceil$, suppose $\ell\geq
2k+1$. Let $G$ be an $m$-joined graph and $S$ be a $(d,m)$-extendable subgraph
of $G$ with at most $|G|-10dm-(\ell-2k-1)$ vertices. Suppose $a$ and $b$ are
two distinct vertices in $S$, both with degree at most $d/2$ in S. Then there
is an $(a,b)$-path P of length $\ell$ with internal vertices outside $S$, such
that $S\cup P$ is $(d,m)$-extendable.

######  Lemma 4.3.

[38, Corollary 3.7] Let $d,m\in\mathbb{N}$ satisfy $m\geq 1$, $d\geq 3$ and
$T$ be a tree with maximum degree at most $d-1$, which contains a vertex $t\in
V(T)$. Let $G$ be an $m$-joined graph and suppose $S$ is a $(d,m)$-extendable
subgraph of $G$ with maximum degree $d$. Let $r\in V(S)$ and suppose

$|S|+|T|\leq|G|-2dm-3m.$

Then, there is a copy $T^{\prime}$ of $T$ in $G-(V(S)\setminus\\{r\\})$, in
which $t$ is mapped to $r$, such that $S\cup T^{\prime}$ is $(d,m)$-extendable
in $G$.

###### Proof of Lemma 3.8.

Given integers $m,d_{1},\Delta\in\mathbb{N}$ as in the statement, we fix $G$
to be an $m$-joined graph and $W\subseteq V(G)$ such that $G$ $d_{1}$-expands
into $W$ with $d_{1}\geq\Delta+2$. Now we build the desired tree array in the
following two steps. At the first step, we shall use Lemma 4.2 to build
pairwise vertex-disjoint paths with internal vertices in $W$, each connecting
a prescribed pair of vertices in $\mathcal{I}$. Let $S$ be an empty graph on
vertex set $V(\mathcal{I})$.

######  Claim 4.4.

The subgraph $S$ is a $(d_{1},m)$-extendable subgraph in $G^{\prime}=G[W\cup
V(\mathcal{I})]$.

###### Proof.

By Definition 4.1, it is sufficient to show that for every set $X\subseteq
V(G^{\prime})$ with $|X|\leq 2m$, we have

$|\Gamma_{G^{\prime}}(X)\setminus V(\mathcal{I})|\geq d_{1}|X|.$

As $N_{G}(X,W)\subseteq\Gamma_{G^{\prime}}(X)\setminus V(\mathcal{I})$, it
suffices to verify that $|N_{G}(X,W)|\geq d_{1}|X|$. This trivially follows
since $G$ $d_{1}$-expands into $W$ and $|X|\leq 2m<\frac{|W|}{2d_{1}}$. ∎

Therefore, by repeatedly applying Lemma 4.2 to $G^{\prime}$ with $(d_{1},s,m)$
in place of $(d,\ell,m)$, we can connect the pairs of vertices from
$\mathcal{I}$ by vertex-disjoint paths $P_{1},\ldots,P_{t}$ each of length $s$
in $G^{\prime}$. This can be done as in this process the resulting subgraph
$S_{i}:=S\cup P_{1}\cup\cdots\cup P_{i}$, $i\leq t$, would still be a
$(d_{1},m)$-extendable graph of order at most

$(s+1)t\leq|W|-10d_{1}m-s.$

For the second step, let $R:=V(S_{t})\setminus V(\mathcal{I})$. Then we shall
repeatedly use Lemma 4.3 to build for all vertices $v\in R$, pairwise vertex-
disjoint $\Delta$-ary trees $T_{v}$ of height $s$, where $T_{v}$ has root $v$
and all other vertices in $W\setminus R$. In fact, in the initial step, we
have that

$|S_{t}|+|T_{v}|\leq(s+1)t+(1+\Delta+\Delta^{2}+\cdots+\Delta^{s})<(s+1)\Delta^{s+1}t<|W|-2d_{1}m-3m.$

For an arbitrary vertex $v\in R$, we apply Lemma 4.3 to obtain a desired copy
$T_{v}$ of $\Delta$-ary tree of height $s$ with a root $v$ and in particular
we have that $S_{t}\cup T_{v}$ is also $(d_{1},m)$-extendable in $G[W\cup
V(\mathcal{I})]$. We repeat this step for every $v\in R$ iteratively such that
the corresponding $\Delta$-ary trees $T_{v}$ are pairwise vertex disjoint.
Note that this can be done as at the end of this process the resulting
subgraph $\bigcup_{v\in R}T_{v}\cup S_{t}$ would still be
$(d_{1},m)$-extendable with maximum degree $\Delta+2\leq d_{1}$ and order at
most

$|S_{t}|+|R|(1+\Delta+\Delta^{2}+\cdots+\Delta^{s})\leq
t(s+1)\Delta^{s+1}\leq|W|-2d_{1}m-3m.$

The family $\\{T_{v}:v\in R\\}$ of trees together with the family
$\\{P_{i}:i\in[t]\\}$ of paths as above form a desired
$(W,\mathcal{I},s,\Delta)$-tree array. ∎

##  5\. Proof of Theorem 1.10

The proof of Theorem 1.10 is divided into two cases depending on whether $T$
has many pendant stars or many vertex-disjoint caterpillars of the same
length. This would accordingly be decoded by the following two results.

######  Lemma 5.1 (Pendant stars).

For any constant $0<\gamma<\frac{1}{2}$, there exists $c>0$ such that the
following holds for sufficiently large integer $n$. For all
$\Delta\in\mathbb{N}$ with $\Delta\leq c\sqrt{n}$, every
$(n,\frac{100}{\gamma}\Delta\sqrt{n})$-expander is universal for the trees in
$\mathcal{T}(n,\Delta)$ with at least $\frac{\gamma n}{\Delta}$ pendant stars.

######  Lemma 5.2 (Caterpillars).

For any integer $k\geq 800$ there exists $C>0$ such that the following holds
for sufficiently large integer $n$. For all $\Delta\in\mathbb{N}$ with
$\Delta\leq\frac{\sqrt{n}}{2C}$, every $(n,C\Delta\sqrt{n})$-expander is
universal for the trees in $\mathcal{T}(n,\Delta)$ with at least
$\frac{n}{4k\Delta}$ vertex-disjoint caterpillars each of length $k$.

###### Proof of Theorem 1.10.

Take $k=800$, and choose $\frac{1}{n}\ll c\ll\frac{1}{C}\ll\frac{1}{k}$. Let
$G$ be an $(n,d)$-expander with $d\geq C\Delta\sqrt{n}$, where $\Delta\leq
c\sqrt{n}$. By Corollary 2.2, every $T\in\mathcal{T}(n,\Delta)$ has either at
least $\frac{n}{4k\Delta}$ pendant stars or $\frac{n}{4k\Delta}$ vertex-
disjoint caterpillars each of length $k$. For the former case, by applying
Lemma 5.1 with $\gamma=\frac{1}{4k}$, one can find a copy of $T$ in $G$. For
the latter case, as $c\ll\frac{1}{C}$, Lemma 5.2 immediately gives a copy of
$T$ in $G$. ∎

###  5.1. Many pendant stars: proof of Lemma 5.1

Choose $\frac{1}{n}\ll c\ll\gamma$ and let $T$ be an $n$-vertex tree with
maximum degree $\Delta\leq c\sqrt{n}$. Let $S_{1},S_{2},\ldots,S_{\frac{\gamma
n}{\Delta}}$ be a collection of pendant stars in $T$, and $A$ be the set of
roots of the pendant stars in the collection, where for every $v\in A$, we
denote by $s(v)$ the number of pendant stars in the collection that are rooted
at $v$. Denote by $B=\\{b_{1},b_{2},\ldots,b_{\frac{\gamma n}{\Delta}}\\}$ the
set of centers of the pendant stars in the collection and by $C$ the set of
leaves attached to the vertices in $B$. Thus $\sum_{v\in A}s(v)=|B|$ and
$|B|\leq|C|<\Delta|B|$. Let $T^{\prime}:=T-(B\cup C)$.

Recall that $G$ is an $(n,d)$-expander with
$d=\frac{100}{\gamma}\Delta\sqrt{n}$ and we write $m:=\frac{n}{2d}$. Then our
embedding proceeds as follows.

Phase $0$. Partition $V(G)$.
We first randomly partition $V(G)$ into four parts $V_{1},V_{2},V_{3},V_{4}$
such that

$\displaystyle|V_{1}|=n-|B|-|C|+22\Delta m,\leavevmode\nobreak\
|V_{2}|=|B|=\frac{\gamma n}{\Delta}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |V_{3}|=|V_{4}|=\frac{|C|}{2}-11\Delta m.$
(5.1)

One can easily check that $|V_{i}|\geq\frac{\gamma n}{2\Delta}-11\Delta
m=\frac{\gamma n}{2\Delta}-\frac{11\sqrt{n}}{200}\geq\frac{\gamma n}{3\Delta}$
as $c\ll\gamma$. Since $G$ is an $(n,d)$-expander with

$\displaystyle d=\frac{100}{\gamma}\Delta\sqrt{n}\leavevmode\nobreak\
\text{and thus}\leavevmode\nobreak\ d_{i}:=\frac{|V_{i}|}{5n}d\geq
6\sqrt{n}>\max\\{2\Delta,2\log n\\}\leavevmode\nobreak\ \text{for
every}\leavevmode\nobreak\ i\in[4],$ (5.2)

by Lemma 3.1, there exists such a partition with the following property:

  1. (E1)

$G$ $d_{i}$-expands into $V_{i}$ for all $i\in[4]$.

Phase $1$. Embed $T^{\prime}$ in $G[V_{1}]$.
By property (E1), we can apply Theorem 1.9 to $G[V_{1}]$ to find a copy of
$T^{\prime}$ inside $V_{1}$. Indeed, as $d_{1}\geq 2\Delta$ in (5.2), it
suffices to ensure that the order of $T^{\prime}$ is no larger than
$|V_{1}|-4\Delta\lceil\frac{|V_{1}|}{2d_{1}}\rceil$, and this easily follows
as $|V_{1}|-|T^{\prime}|=22\Delta
m>4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil$. The resulting
embedding of $T^{\prime}$ is denoted as $\phi|_{T^{\prime}}$ and write
$V_{1}^{\prime}=V_{1}\setminus\phi(V(T^{\prime}))$ for the set of leftover
vertices in $V_{1}$. Then we shall extend $\phi$ as follows.

Phase $2$. Embed $B$ into $V_{2}\cup V_{3}$.
We first find a maximal star-matching $M_{1}$ where every star has a center
$\phi(v)$ with $v\in A$ and exactly $s(v)$ leaves in $V_{2}$. Let
$A_{1}=\phi(A)\cap V(M_{1}),B_{1}=V_{2}\cap V(M_{1})$ and
$A_{2}=\phi(A)\setminus A_{1},V_{2}^{\prime}=V_{2}\setminus B_{1}$.

######  Claim 5.3.

$|A_{2}|<m\leavevmode\nobreak\ \text{and thus}\leavevmode\nobreak\
|V_{2}^{\prime}|\leq\Delta m$.

Indeed, suppose $|A_{2}|\geq m$ and thus
$|V_{2}^{\prime}|=\sum_{v\in\phi^{-1}(A_{2})}s(v)=|A_{2}|+k$ for some $k\geq
0$. Then as $G$ is $m$-joined and $|A_{2}|\geq m$, we have
$\sum_{v\in\phi^{-1}(A_{2})}d_{G}(\phi(v),V_{2}^{\prime})=e(A_{2},V_{2}^{\prime})\geq
k+1$. Since $M_{1}$ is maximal, we have $d_{G}(\phi(v),V_{2}^{\prime})\leq
s(v)-1$ for every $v\in\phi^{-1}(A_{2})$. Thus,
$\sum_{v\in\phi^{-1}(A_{2})}d_{G}(\phi(v),V_{2}^{\prime})\leq\sum_{v\in\phi^{-1}(A_{2})}(s(v)-1)=|V_{2}^{\prime}|-|A_{2}|=k$,
a contradiction.

Next we shall greedily build a star-matching $M_{2}$ between $A_{2}$ and
$V_{3}$, where every star has a center $\phi(v)\in A_{2}$ and exactly $s(v)$
leaves in $V_{3}$. By combining the Hall’s condition (see (3.1)), the
existence of such a star-matching easily follows since $G$ $d_{3}$-expands
into $V_{3}$ with $d_{3}>\Delta$ by (5.2). Let $B_{2}=V_{3}\cap V(M_{2})$ and
$V_{3}^{\prime}=V_{3}\setminus B_{2}$.

Phase $3$. Embed $C$ into $R:=V_{1}^{\prime}\cup V_{2}^{\prime}\cup
V_{3}^{\prime}\cup V_{4}$ via a star-matching
It remains to build a star-matching between $B_{1}\cup B_{2}$ and $R$. To be
more precise, we define an auxiliary function $f:B_{1}\cup
B_{2}\rightarrow[\Delta]$ by taking $f(v)=d_{T}(\phi^{-1}(v))-1$, that is, the
number of leaves we need to attach to every $v\in B_{1}\cup B_{2}$ so as to
complete the embedding. By property (E1) and (5.2), we observe that $G$
$d_{4}$-expands into $V_{4}$ for $d_{4}>\Delta$ and every $v\in R$ has

$d(v,B_{1}\cup B_{2})\geq
d(v,V_{2})-|V_{2}^{\prime}|\geq\frac{|V_{2}|}{5n}d-\Delta
m\overset{\eqref{eq6}}{\geq}\frac{\gamma
d}{5\Delta}-\Delta\frac{n}{2d}\overset{\eqref{eq61}}{>}\frac{n}{2d}=m.$

Since $G$ is $m$-joined, we can apply Lemma 3.3 to $G$ with $(B_{1}\cup
B_{2},R,d_{4})$ in place of $(A,B,d)$ to obtain a desired $f$-matching, which
completes an embedding of $T$.

###  5.2. Many caterpillars: proof of Lemma 5.2

In this section, we consider the case when $T$ has $\frac{n}{4k\Delta}$
vertex-disjoint caterpillars of a constant length $k$.

###### Proof of Lemma 5.2.

Choose $\frac{1}{n}\ll\frac{1}{C}\ll\frac{1}{k}$ and throughout the proof we
have

$m=\frac{n}{2d},\leavevmode\nobreak\ d=C\Delta\sqrt{n}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \Delta\leq\frac{\sqrt{n}}{2C}.$

Assume that an $n$-vertex tree $T$ contains a collection of
$\frac{n}{4k\Delta}$ vertex-disjoint caterpillars each containing a central
path $P_{i},1\leq i\leq\frac{n}{4k\Delta}$, of length $k\geq 800$, where
$x_{i},y_{i}$ are the ends of $P_{i}$. In the forthcoming proofs, we shall
write $r=\frac{n}{8k\Delta}$ and consider two subcases as follows:

  1. (1)

at least $r$ paths $P_{i}$ are bare in $T$;

  2. (2)

at least $r$ paths $P_{i}$ are internally attached with leaves in $T$;

For the first case, we may assume that $P_{1},P_{2},\ldots,P_{r}$ are bare
paths in $T$ and let $T^{\prime}=T-\cup_{i\in[r]}V(P_{i}-\\{x_{i},y_{i}\\})$.
Then our embedding proceeds by first randomly partitioning $V(G)$ into two
parts $V_{1},V_{2}$ such that

$\displaystyle|V_{1}|=|T^{\prime}|+21\Delta m\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |V_{2}|=(k-1)r-21\Delta m.$ (5.3)

We can easily check that
$|V_{1}|\geq\frac{n}{2},|V_{2}|\geq\frac{n}{16\Delta}-21\Delta
m\geq\frac{n}{32\Delta}$ as $d\geq C\Delta^{2}$. Note that $G$ is an
$(n,d)$-expander and

$\displaystyle
d_{i}:=\frac{|V_{i}|}{5n}d\geq\frac{d}{160\Delta}=\frac{C}{160}\sqrt{n}\geq\max\\{2\Delta,2\log
n\\}\leavevmode\nobreak\ \text{ for every }\leavevmode\nobreak\ i\in[2].$
(5.4)

By Lemma 3.1, there exists a partition $V_{1}\cup V_{2}=V$ such that $G$
$d_{i}$-expands into $V_{i}$ for all $i\in[2]$. Based on this, we can first
apply Theorem 1.9 to $G[V_{1}]$ to find an embedding of $T^{\prime}$ inside
$V_{1}$. Indeed, as $d_{1}\geq 2\Delta$, it suffices to ensure that the order
of $T^{\prime}$ is no larger than
$|V_{1}|-4\Delta\lceil\frac{|V_{1}|}{2d_{1}}\rceil$. This easily follows since
$|V_{1}|-|T^{\prime}|=21\Delta
m>4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil.$ Let $\phi$ be the
resulting embedding of $T^{\prime}$ and $X,Y$ be the set of images of ends
$x_{i},y_{i}$, respectively. Now it remains to embed the bare paths
$P_{i},i\in[r]$ using $V_{2}$. By the choice of $\frac{1}{C}\ll\frac{1}{k}$
and the fact that $d_{2}\geq\frac{C}{160}\sqrt{n}\geq
C_{\ref{pathcover2}}k\sqrt{n}$, such a collection of vertex-disjoint paths can
be obtained by Lemma 3.6 applied to $G[X\cup Y\cup V_{2}]$ with
$(d_{2},k+1,(k+1)r,V_{2})$ in place of $(d,\ell,n,W)$, which together with
$\phi$ completes the embedding of $T$.

For the second case, the proof strategy is similar to that in Section 4.2.2.
Without loss of generality, we may assume that $P_{1},P_{2},\ldots,P_{r}$ are
central paths from vertex-disjoint caterpillars in $T$, each with at least one
leg. Following the technique in Section 4.2.2, we take subpaths
$Q_{i}\subseteq P_{i},1\leq i\leq r$ such that each $Q_{i}$ has length
$k^{\prime}=\lfloor k/2\rfloor$ and one can write
$Q_{i}=a^{i}_{0}a^{i}_{1}\ldots a^{i}_{k^{\prime}}$ so that $a^{i}_{1}$ is
attached with at least one leaf. For every $j\in\\{0,1,\ldots,k^{\prime}\\}$,
denote by $A_{j}$ the set of the vertices $a^{i}_{j}$ taken over all paths
$Q_{i},1\leq i\leq r$. Moreover we write $L$ for the set of all leaves in $T$
that are attached to the internal vertices of the paths $Q_{i},1\leq i\leq r$.
Write $L^{+}=N_{T}(L)$. Then $A_{1}\subseteq L^{+}$ and $r=|A_{j}|\leq|L|$ for
every $j\in\\{0,1,\ldots,k^{\prime}\\}$.

Let $T^{\prime}:=T-(\bigcup_{j=1}^{k^{\prime}-1}A_{j}\cup L)$. Now our
embedding proceeds as follows.
Phase $0$. Partition $V(G)$.
We first randomly partition $V(G)$ into four parts $V_{1},V_{2},V_{3},V_{4}$
such that

$\displaystyle|V_{1}|=|T^{\prime}|+21\Delta m,\leavevmode\nobreak\
|V_{2}|=|A_{1}|=r,|V_{3}|=(k^{\prime}-2)r\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |V_{4}|=|L|-21\Delta m.$

Observe that for every $i\in[4]$, $|V_{i}|\geq r-21\Delta
m\geq\frac{n}{16k\Delta}$ as $d\geq C\Delta^{2}$. Since $G$ is an
$(n,d)$-expander and

$\displaystyle
d_{i}:=\frac{|V_{i}|}{5n}d\geq\frac{d}{80k\Delta}=\frac{C}{80k}\sqrt{n}>\max\\{2m,2\Delta,2\log
n\\}\leavevmode\nobreak\ \text{ for every}\leavevmode\nobreak\ i\in[4],$ (5.5)

by Lemma 3.1, we can obtain such a partition with the following property:

  1. (F1)

$G$ $d_{i}$-expands into $V_{i}$ for all $i\in[4]$.

Phase $1$. Embed $T^{\prime}$ in $G[V_{1}]$.
By property (F1), we can apply Theorem 1.9 to $G[V_{1}]$ to find a copy of
$T^{\prime}$ inside $V_{1}$, denoted as $\phi|_{T^{\prime}}$. Indeed, this
easily follows since $d_{1}\geq 2\Delta$ in (5.5) and
$|V_{1}|-|T^{\prime}|=21\Delta
m>4\Delta\left\lceil\frac{|V_{1}|}{2d_{1}}\right\rceil.$

Phase $2$. Embed $A_{1}$ into $V_{2}\cup V_{3}$.
We first build a maximal matching $M_{1}$ between $\phi(A_{0})$ and $V_{2}$.
Denote by $A^{\prime}_{0},A_{1}^{\prime}$ the sets of vertices in
$\phi(A_{0})$ and $V_{2}$, respectively, that are not covered by $M$. Since
$G$ is $m$-joined, we have $|A^{\prime}_{0}|=|A^{\prime}_{1}|<m$. Moreover, by
property (F1) and (5.5), we have that $d(v,V_{3})\geq d_{3}\geq 2m$. Thus one
can easily obtain a matching $M_{2}$ from $A_{0}^{\prime}$ to a subset
$B_{1}\subseteq V_{3}$ with $|B_{1}|=|A_{0}^{\prime}|$. Let
$V_{2}^{\prime}=(V_{2}\setminus A_{1}^{\prime})\cup B_{1}$ and
$V_{3}^{\prime}=(V_{3}\setminus B_{1})\cup A_{0}^{\prime}$. Then
$|V_{3}^{\prime}\setminus V_{3}|=|V_{2}^{\prime}\setminus V_{2}|\leq m$ and
note that $V_{2}^{\prime}=\phi(A_{1})$. Furthermore, it is easy to verify that
$G$ $\frac{d_{2}}{2}$-expands into $V_{2}^{\prime}$ and
$\frac{d_{3}}{2}$-expands into $V_{3}^{\prime}$ as $d_{i}\geq 2m$.

Phase $3$. Embed the subpaths $Q_{i}-a_{0}^{i}$ using $V_{3}^{\prime}$
By the choice of $\frac{1}{C}\ll\frac{1}{k}$ and the fact that
$\frac{d_{3}}{2}\geq\frac{C}{160k}\sqrt{n}\geq C_{\ref{pathcover2}}k\sqrt{n}$,
such a collection of vertex-disjoint paths can be obtained by Lemma 3.6
applied to $G[V_{2}^{\prime}\cup\phi(A_{k^{\prime}})\cup V_{3}^{\prime}]$ with
$(\frac{d_{3}}{2},k^{\prime}+1,(k^{\prime}+1)r,V_{3}^{\prime})$ in place of
$(d,\ell,n,W)$. This yields an embedding $\phi|_{T-L}$.

Hence it remains to embed $L$ into the remaining set $R$ of vertices with
$R=V(G)-\phi(T-L)$.

Phase $4$. Embed $L$ into the leftovers via a star-matching.
Recall that $L^{+}$ is the neighborhood of $L$ in $T$ and $A_{1}\subseteq
L^{+}$. Also observe that $V_{4}\subseteq R$. We shall build a star-matching
between $\phi(L^{+})$ and $R$. To finish the embedding of $T$, we define an
auxiliary function $f:\phi(L^{+})\rightarrow[\Delta]$ by taking
$f(v)=d_{T}(\phi^{-1}(v))-2$, that is, the number of leaves we need to attach
to every $v\in\phi(L^{+})$. Then as $G$ $\frac{d_{2}}{2}$-expands into
$V_{2}^{\prime}$, we observe that for every $v\in R$

$d(v,\phi(L^{+}))\geq
d(v,V_{2}^{\prime})\geq\frac{d_{2}}{2}\overset{\eqref{eq56}}{\geq}m.$

Moreover, as $V_{4}\subseteq R$ and $G$ $d_{4}$-expands into $V_{4}$ with
$d_{4}\overset{\eqref{eq56}}{>}\Delta$, we obtain that

$|N(X,R)|\geq|N(X,V_{4})|\geq d_{4}|X|\geq\Delta|X|\leavevmode\nobreak\ \text{
for every}\leavevmode\nobreak\ X\subseteq\phi(L^{+})\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\ |X|\leq m.$

Applying Lemma 3.3 with $(\phi(L^{+}),R,\Delta)$ in place of $(A,B,d)$, we
have a desired $f$-matching, which together with $\phi|_{T-L}$ forms an
embedding of $T$.

∎

##  6\. Covering Expanders with paths

This section is devoted to the proof of Lemma 3.6. Before that, we first give
a result as follows.

######  Lemma 6.1.

Let $m,d_{1}\in\mathbb{N}$ with $m\geq d_{1}\geq 2$ and $G$ be a graph that is
$m$-joined. Suppose $G$ contains disjoint vertex sets $X$, $Y$ and $U$, with
$X=\\{x_{1},\ldots,x_{2m}\\}$, $Y=\\{y_{1},\ldots,y_{2m}\\}$ and $|U|\geq
20d_{1}m$. Then for all integers $k_{i}$, $i\in[2m]$, satisfying

$\frac{2\log m}{\log d_{1}}+1\leq k_{i}\leq\frac{|U|}{2},$

there exists for some $i$ an $(x_{i},y_{i})$-path of length exactly $k_{i}$,
whose internal vertices lie in $U$.

The proof of Lemma 6.1 can be found in the appendix.

######  Lemma 6.2.

[37, Bipartite-template] There is a constant $n_{0}$, such that for every
$n\geq n_{0}$ with $3|n$, there exists a bipartite graph $H$ on vertex classes
$X$ and $Y\cup Z$ with $|X|=n$, $|Y|=|Z|=2n/3$, and maximum degree $40$, so
that the following is true. Given any subset $Z^{\prime}\subseteq Z$ with
$|Z^{\prime}|=n/3$, there is a matching between $X$ and $Y\cup Z^{\prime}$.

###  6.1. Proof of Theorem 3.6

Given a vertex $v\in V(G)$ and an integer $k\in\mathbb{N}$, a $k$-_fan rooted
at_ $v$ is a subgraph consisting of $k$ triangles which mutually intersect on
no other vertices than $v$, where every edge not incident with $v$ is called
an _absorber_ for $v$. Now we are ready to prove Lemma 3.6.

###### Proof.

Choose $\frac{1}{n}\ll\frac{1}{C}\ll\frac{1}{\ell}$ and let $G,W$ be given
such that $G$ $d$-expands into $W$, where

$\displaystyle d=C\ell\sqrt{n},\leavevmode\nobreak\
|W|=\frac{\ell-2}{\ell}n\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
m=\lceil\frac{|W|}{2d}\rceil<\frac{\sqrt{n}}{C\ell}.$ (6.1)

Then by Definition 1.7 $G$ is $m$-joined. Let

$X=\\{x_{1},x_{2},\ldots,x_{n/\ell}\\},\leavevmode\nobreak\
Y=\\{y_{1},y_{2},\ldots,y_{n/\ell}\\}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ r=\frac{n}{10^{4}\ell}.$

Our goal is to find pairwise vertex-disjoint $(x_{i},y_{i})$-paths,
$i\in[n/\ell]$, each of length $\ell$. Our proof proceeds in the following
steps.

We first randomly partition $W$ into four parts $W_{1},W_{2},W_{3},W_{4}$ such
that

$\displaystyle|W_{1}|=|W_{2}|=2r\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
|W_{i}|=\frac{|W|-4r}{2}\geq\frac{n}{3}\leavevmode\nobreak\ \text{for
every}\leavevmode\nobreak\ i\in\\{3,4\\}.$ (6.2)

Let $d_{i}=\frac{|W_{i}|}{5|W|}d$ for every $i\in[4]$. Then
$d_{i}>\frac{2r}{5n}d>2\log n$. As $G$ $d$-expands into $W$, by Lemma 3.1,
there exists a partition $\\{W_{1},\ldots,W_{4}\\}$ so that $G$
$d_{i}$-expands into $W_{i}$ for every $i\in[4]$.

Phase $1$. Building an absorbing structure.
Take subsets
$X_{1}=\\{x_{1},x_{2},\ldots,x_{3r}\\},Y_{1}=\\{y_{1},y_{2},\ldots,y_{3r}\\}$
and write $X_{2}=X\setminus X_{1},Y_{2}=Y\setminus Y_{1}$.

######  Claim 6.3.

There is a subset $A\subseteq W_{2}\cup W_{3}\cup W_{4}$ with
$|A|=3r(\ell-2)-r$ such that for any subset $U\subseteq W_{1}$ with $|U|=r$,
there is a collection of $3r$ vertex disjoint $(x_{i},y_{i})$-paths of length
$\ell-1$, $i\in[3r]$, in $A\cup U$. In fact, therefore, such paths cover the
set $A\cup U$.

###### Proof of claim.

We shall first create pairwise disjoint $40$-fans $F_{v}$ with root $v$ for
every $v\in W_{1}\cup W_{2}$ and the remaining vertices inside $W_{3}$. To
achieve this, we choose a subset $T\subseteq W_{3}$ such that
$|T|=\frac{|W_{3}|}{2}$ and $d(v,T)\geq\frac{1}{4}d(v,W_{3})$ for every $v\in
V(G)$. Such a set $T$ can be found by choosing $\frac{|W_{3}|}{2}$ vertices in
$W_{3}$ uniformly at random and by applying Chernoff’s inequality and a union
bound. Let $T^{\prime}=W_{3}\setminus T$. We claim that for every set $L$ of
$m$ vertices in $W_{1}\cup W_{2}$ and every set $S\subseteq W_{3}$ of
$\frac{n}{100}$ vertices, there exists a $40$-fan with a root in $L$ and the
remaining vertices in $S$. In fact, as $G$ is $m$-joined, by averaging, there
is a vertex, say $v\in L$, that has a set $S_{v}$ of neighbors inside $S$ with

$|S_{v}|>\frac{|S|-m}{m}\geq\frac{n}{200m}\overset{\eqref{eq70}}{\geq}80m.$

Thus as $G$ is $m$-joined, we can greedily pick a matching of $40$ edges in
$S_{v}$, which together with $v$ form a $40$-fan $F_{v}$ as desired. Based on
this claim we can greedily choose pairwise disjoint $40$-fans $F_{v}$ for all
but at most $m$ vertices $v\in W_{1}\cup W_{2}$, where all the remaining
vertices of such fans $F_{v}$ come from $T^{\prime}$. This is possible as
$|T^{\prime}|=\frac{|W_{3}|}{2}>\frac{n}{6}\geq 80|W_{1}\cup
W_{2}|+\frac{n}{100}$. Now it remains to find fans for a set $L^{\prime}$ of
at most $m$ vertices from $W_{1}\cup W_{2}$, and here we shall use $T$
(reserved to cover the leftover vertices). This can be trivially done as for
every $v\in V(G)$,
$d(v,T)\geq\frac{1}{4}d(v,W_{3})\geq\frac{|W_{3}|}{20|W|}d>\frac{d}{60}\geq
160m\geq 80|L^{\prime}|+80m$. Denote by $A_{v}$ the set of absorbers for $v$
in $F_{v},v\in W_{1}\cup W_{2}$ and let $M=\cup_{v\in W_{1}\cup W_{2}}A_{v}$.
Then $M$ is indeed a matching of size $160r$ in $W_{3}$. Let
$W_{3}^{\prime}=W_{3}\setminus V(M)$ and thus $|W_{3}^{\prime}|=|W_{3}|-320r$.

To describe how to route our paths through these triangles in the fans, we
refer to an auxiliary bipartite graph $H$ obtained by Lemma 6.2 applied with
$n=3r$. The bipartite graph $H$ has maximum degree $40$ and vertex classes
$X=[3r]$ and $Y\cup Z$ such that $|Y|=|Z|=2r$ and for any subset
$Z^{\prime}\subseteq Z$ with $|Z^{\prime}|=r$ there is a perfect matching
between $X$ and $Z^{\prime}\cup Y$ in $H$. Fix an arbitrary bijection
$\tau:Y\cup Z\to W_{1}\cup W_{2}$ with $\tau(Z)=W_{1}$. Now we first pick
pairwise disjoint matchings $M_{i}\subseteq M,i\in[3r]$ such that

  1. (G1)

for every $i\in[3r]$ and every $v\in\tau(N_{H}(i))$, $M_{i}$ consists of
exactly one edge in $A_{v}$.

Recall that $X_{1}=\\{x_{1},\ldots,x_{3r}\\},Y_{1}=\\{y_{1},\ldots,y_{3r}\\}$.
Next, we shall build pairwise disjoint $(x_{i},y_{i})$-paths $P_{i}$ of length
$\ell-2$ for every $i\in[3r]$ such that $M_{i}\subseteq E(P_{i})$ and the
other internal vertices come from $W_{3}^{\prime}\cup W_{4}$. As $|M_{i}|\leq
40$, we may take $|M_{i}|=40$ for instance and set
$M_{i}=\\{u_{j}v_{j}:j\in[40]\\}$ to ease the notation. Observe that $\ell\geq
200>3(|M_{i}|+1)+|M_{i}|$, every such $P_{i}$ ought to be constructed by
connecting the corresponding $41$ pairs of vertices

$\\{x_{i},u_{1}\\},\\{v_{1},u_{2}\\},\ldots\\{v_{j},u_{j+1}\\},\ldots,\\{v_{40},y_{i}\\}$

using pairwise disjoint paths $P_{i,j}$ of length $k_{i,j}\geq 3,j\in[41]$
satisfying

$\sum_{j\in[41]}k_{i,j}=\ell-2-|M_{i}|.$

To do this, in total we have a set of $\sum_{i\in[3r]}(|M_{i}|+1)\leq 123r$
such pairs to connect as above, say $\mathcal{P}$, and the number of vertices
used in all these connections is at most $3r\ell$. Note that by the choice of
$\frac{1}{C}\ll\frac{1}{\ell}$ and $r=\frac{n}{10^{4}\ell}$, we have

$|W_{3}^{\prime}|=|W_{3}|-320r=\frac{|W|}{2}-322r\overset{\eqref{eq71}}{>}\frac{n}{6}>3r\ell+20m^{2}.$

By repeatedly applying Lemma 6.1 with $d_{1}=m$ and $U$ playing the role of
the set of vertices in $W_{3}^{\prime}$ uncovered by previous connections, one
can greedily connect all but a subfamily
$\mathcal{P}^{\prime}\subseteq\mathcal{P}$ of at most $2m$ pairs via vertex-
disjoint paths $P_{i,j}$ with all the internal vertices in $W_{3}^{\prime}$.
Now we shall connect the remaining pairs in $\mathcal{P}^{\prime}$ using
$W_{4}$. Note that $G$ $d_{4}$-expands into $W_{4}$ and thus for every $v\in
V(G)$,

$d(v,W_{4})\geq
d_{4}=\frac{|W_{4}|}{5|W|}d>\frac{d}{20}\overset{\eqref{eq70}}{>}10m\ell.$

Thus one can greedily complete the connection for $\mathcal{P}^{\prime}$ as
the total number of vertices used in connections is at most $2m\ell$.

Let $A=\cup_{i\in[3r]}(P_{i}\setminus\\{x_{i},y_{i}\\})\cup W_{2}$ and thus
$|A|=3r(\ell-2)-r$. We claim this is such a set as required by the claim.
Indeed, let $U\subseteq W_{1}$ be any set of size $r$. From the property of
the graph $H$, we can find a perfect matching between $\tau^{-1}(U)\cup Y$ and
$[3r]$. For each $i\in[3r]$, take the vertex $v\in U\cup W_{2}$ such that
$\tau^{-1}(v)\in\tau^{-1}(U)\cup Y$ is matched to $i$ and also take an
$(x_{i},y_{i})$-path of length $\ell-1$ on $V(P_{i})\cup\\{v\\}$, i.e., in
$P_{i}$ replacing the unique edge $uw\in P_{i}\cap A_{v}$ by the path $uvw$
(see (G1)). These paths altogether cover $U\cup A$, as required. ∎

Phase $2$. Connect almost all pairs $\\{x_{i},y_{i}\\}$ for $x_{i}\in
X_{2},y_{i}\in Y_{2}$.
Let $W^{\prime}=W\setminus(A\cup W_{1})$ and $s=\frac{1+c}{\ell-2}r$ for
$c=\frac{1}{8}$. Then
$|W^{\prime}|=\frac{\ell-2}{\ell}n-3r(\ell-2)-r=(\ell-2)|X_{2}|-r$ and $s>2m$.
By repeatedly applying Lemma 6.1 with $U=W^{\prime}$, $d_{1}=m$ and
$k_{i}=\ell$, one can greedily connect pairs $\\{x_{i},y_{i}\\}$, where
$x_{i}\in X_{2},y_{i}\in Y_{2}$, via vertex-disjoint paths $P_{i}$ of length
$\ell-1$ with all the internal vertices in $W^{\prime}$ until there are
exactly $s$ pairs remaining. Since in total the number of vertices unused in
the connections is at least

$|W^{\prime}|-(\ell-2)(|X_{2}|-s)=(\ell-2)s-r=cr\geq 20m^{2},$

if after this there are $t$ vertex pairs remaining, where $t>s>2m$, then take
among them $2m$ pairs $\\{x_{i},y_{i}\\}$. Lemma 6.1 would give one more path
for some $\\{x_{i},y_{i}\\}$, contradicting $t>s$. The process terminates,
therefore, with only $s$ pairs remaining, denoted as $\mathcal{S}$.

Phase $3$. Connect the pairs in $\mathcal{S}$ using $W_{1}$
Let $S$ be the set of indices $i$ such that $\\{x_{i},y_{i}\\}\in\mathcal{S}$
and $L$ be the set of remaining vertices in $W^{\prime}$ not covered by any
path in previous steps. Then
$|L|=|W^{\prime}|-(\ell-2)(|X_{2}|-s)=(\ell-2)s-r=cr$. Write
$X_{S}=\\{x_{i}:i\in S\\},Y_{S}=\\{y_{i}:i\in S\\}$ and
$L=\\{u_{1},u_{2},\ldots,u_{cr}\\}$.

Now we shall connect all pairs $\\{x_{i},y_{i}\\}\in\mathcal{S}$ via pairwise
disjoint paths of length exactly $\ell-1$, each having internal vertices in
$W_{1}$. To achieve this, we choose a partition $T_{1}\cup T_{2}=W_{1}$ such
that $|T_{1}|=3|T_{2}|$ and $G$ $\frac{d_{1}}{20}$-expands into $T_{i}$ for
$i\in[2]$. Since $G$ $d_{1}$-expands into $W_{1}$ and
$\frac{|T_{i}|}{5|W_{1}|}d_{1}\geq\frac{d_{1}}{20}>2\log 2r$, such a partition
can be obtained by applying Lemma 3.1.

As $G$ $\frac{d_{1}}{20}$-expands into $T_{1}$, we first find a star-matching
$M^{\prime}$ into $T_{1}$ from $X_{S}\cup Y_{S}\cup L$, such that $x_{i}$ (or
$y_{i}$) is matched to one vertex, say $x_{i}^{1}$ (resp. $y_{i}^{1}$), and
every $u_{j}\in L$ is matched to two vertices, say $v_{j}^{1}$ and
$v_{j}^{2}$, respectively. Indeed, by Hall’s condition, it suffices to
guarantee that $N(X,T_{1})\geq 2|X|$ for every subset $X\in X_{S}\cup
Y_{S}\cup L$: the case $|X|<m$ easily follows as $G$
$\frac{d_{1}}{10}$-expands into $T_{1}$; as $G$ is $m$-joined, if $|X|\geq m$,
then $N(X,T_{1})>|T_{1}|-m\geq r\geq 2|X|$ because $|X|\leq|X_{S}\cup
Y_{S}\cup L|=2s+cr\leq\frac{r}{2}$. Write
$T_{1}^{\prime}=T_{1}-V(M^{\prime})$. We then arbitrarily partition all the
pairs $\\{v_{j}^{1},v_{j}^{2}\\},j\in[cr]$ into $s$ groups of nearly equal
size, denoted by $U_{1},U_{2},\ldots,U_{s}$.

Next we shall find a maximal collection of pairwise disjoint
$(x_{i},y_{i})$-paths $P_{i}$ ($i\in S$) of length $\ell-1$ with all internal
vertices in $T_{1}$ such that each $P_{i}$ passes through the paths
$v_{j}^{1}u_{j}v_{j}^{2}$ for all $\\{v_{j}^{1},v_{j}^{2}\\}\in U_{i}$. Note
that

$\frac{cr}{s}-1\leq|U_{i}|\leq\frac{cr}{s}+1=\frac{c}{1+c}(\ell-2)+1\leq
c(\ell-2)=\frac{\ell-2}{8}$

and thus $\ell>3(|U_{i}|+1)+2|U_{i}|$. Setting
$U_{i}=\\{\\{v_{j}^{1},v_{j}^{2}\\}:j\in[t]\\}$ for some $t\in\mathbb{N}$ to
ease the notation, we will build such a path $P_{i}$ by connecting the
corresponding $|U_{i}|+1$ pairs

$\\{x_{i},v_{1}^{1}\\},\\{v_{1}^{2},v_{2}^{1}\\},\\{v_{2}^{2},v_{3}^{1}\\},\ldots,\\{v_{j}^{2},v_{j+1}^{1}\\},\\{v_{j+1}^{2},v_{j+2}^{1}\\},\ldots,\\{v_{t}^{2},y_{i}\\}$

of vertices via pairwise disjoint paths of nearly equal length
$\ell_{1},\ell_{2},\ldots,\ell_{t+1}$ with $\ell_{j}\geq 3$ and
$\sum_{j\in[t+1]}\ell_{j}=\ell-2t-1$. To do this, in total we have a set of
$\sum_{i\in S}(|U_{i}|+1)$ pairs to connect as above, say $\mathcal{P}_{S}$,
and the number of vertices in $T_{1}$ used in all these connections is at most
$s(\ell-2)-|L|=r$. Note that $|T_{1}|=\frac{3r}{2}\geq r+20m^{2}$ and every
subpath in the connections has length

$3\leq\ell_{j}\leq\frac{\ell-1-2t}{t+1}+1\leq\frac{\ell}{cr/s}\leq\frac{2\ell}{c(\ell-2)}\leq\frac{4}{c}=:\ell_{\max}.$

Connect as many pairs in $\mathcal{P}_{S}$ as possible via pairwise vertex-
disjoint paths of prescribed lengths $\ell_{j}$. Then by repeatedly applying
Lemma 6.1 with $d_{1}=m$ and $U$ playing the role of the remaining set of at
least $20m^{2}$ vertices in $T_{1}$ in the process, there is a subfamily
$\mathcal{P}^{\prime}\subseteq\mathcal{P}_{S}$ of at most $2m$ pairs left. Now
we shall connect the remaining pairs in $\mathcal{P}^{\prime}$ using $T_{2}$.
Note that $G$ $\frac{d_{1}}{20}$-expands into $T_{2}$ and thus as
$\frac{1}{C}\ll\frac{1}{\ell}$,

$d(v,T_{2})\geq\frac{d_{1}}{20}\geq\frac{|W_{1}|}{100|W|}d\geq\frac{d}{10^{5}\ell}\geq
10m\ell_{\max}.$

Then one can greedily complete the connections for pairs in
$\mathcal{P}^{\prime}$ because the total number of vertices used in $T_{2}$ is
at most $2m\ell_{\max}$.

In summary, we obtain a set $A$ (see Claim 6.3) and a collection of pairwise
disjoint paths $P_{1},P_{2},\ldots,P_{\frac{n}{\ell}}$, where the first $3r$
paths have length $\ell-2$ whilst the remaining paths have length $\ell-1$.
Let $W_{1}^{\prime}$ be the vertices of $W_{1}$ not used in any of the
previous paths $P_{i}$. Then
$|W_{1}^{\prime}|=|W_{1}|+|L|-s(\ell-2)=2r+cr-(1+c)r=r$. Using the properties
of the set $A$, we can find a collection of $3r$ pairwise disjoint paths of
length $\ell-1$, each connecting $x_{i}$ and $y_{i}$ for every $i\in[3r]$
whilst covering the set $A\cup W_{1}^{\prime}$. This completes all the desired
paths which cover the entire vertex set. ∎

## References

  * [1] P. Allen, J. Böttcher, H. Hàn, Y. Kohayakawa, and Y. Person.  Blow-up lemmas for sparse graphs.  arXiv:1612.00622v4, 2019.
  * [2] N. Alon.  Explicit ramsey graphs and orthonormal labelings.  Electron. J. Combin., 1:Research Paper 12, approx. 8, 1994.
  * [3] N. Alon and V. Asodi.  Sparse universal graphs.  volume 142, pages 1–11. 2002.  Probabilistic methods in combinatorics and combinatorial optimization.
  * [4] N. Alon and M. Capalbo.  Sparse universal graphs for bounded-degree graphs.  Random Structures Algorithms, 31(2):123–133, 2007.
  * [5] N. Alon, M. Capalbo, Y. Kohayakawa, V. Rödl, A. Ruciński, and E. Szemerédi.  Universality and tolerance (extended abstract).  In 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), pages 14–21. IEEE Comput. Soc. Press, Los Alamitos, CA, 2000.
  * [6] N. Alon and N. Kahale.  Approximating the independence number via the $\theta$-function.  Math. Programming, 80(3, Ser. A):253–264, 1998.
  * [7] N. Alon, M. Krivelevich, and B. Sudakov.  Embedding nearly-spanning bounded degree trees.  Combinatorica, 27(6):629–644, 2007.
  * [8] L. Babai, F. R. K. Chung, P. Erdős, R. L. Graham, and J. H. Spencer.  On graphs which contain all sparse graphs.  In Theory and practice of combinatorics, volume 60 of North-Holland Math. Stud., pages 21–26. North-Holland, Amsterdam, 1982.
  * [9] J. Balogh, B. Csaba, M. Pei, and W. Samotij.  Large bounded degree trees in expanding graphs.  Electron. J. Combin., 17(1):Research Paper 6, 9, 2010.
  * [10] J. Beck.  Combinatorial games, volume 114 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 2008.  Tic-tac-toe theory.
  * [11] S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg.  Universal graphs for bounded-degree trees and planar graphs.  SIAM J. Discrete Math., 2(2):145–155, 1989.
  * [12] B. Bollobás.  Modern graph theory, volume 184 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1998.
  * [13] J. Böttcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk, and Y. Person.  Universality for bounded degree spanning trees in randomly perturbed graphs.  Random Structures Algorithms, 55(4):854–864, 2019.
  * [14] M. R. Capalbo and S. R. Kosaraju.  Small universal graphs.  In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 741–749. ACM, New York, 1999.
  * [15] F. R. K. Chung and R. L. Graham.  On graphs which contain all small trees.  J. Combinatorial Theory Ser. B, 24(1):14–23, 1978.
  * [16] F. R. K. Chung and R. L. Graham.  On universal graphs for spanning trees.  J. London Math. Soc. (2), 27(2):203–211, 1983.
  * [17] F. R. K. Chung, R. L. Graham, and N. Pippenger.  On graphs which contain all small trees. II.  In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, volume 18 of Colloq. Math. Soc. János Bolyai, pages 213–223. North-Holland, Amsterdam, 1978.
  * [18] D. Dellamonica, Jr., Y. Kohayakawa, V. Rödl, and A. Ruciński.  An improved upper bound on the density of universal random graphs.  In LATIN 2012: theoretical informatics, volume 7256 of Lecture Notes in Comput. Sci., pages 231–242. Springer, Heidelberg, 2012.
  * [19] A. Ferber, G. Kronenberg, and K. Luh.  Optimal threshold for a random graph to be 2-universal.  Trans. Amer. Math. Soc., 372(6):4239–4262, 2019.
  * [20] A. Ferber and R. Nenadov.  Spanning universality in random graphs.  Random Structures Algorithms, 53(4):604–637, 2018.
  * [21] K. Frankston, J. Kahn, B. Narayanan, and J. Park.  Thresholds versus fractional expectation-thresholds.  Ann. of Math. (2), 194(2):475–495, 2021.
  * [22] R. Glebov, D. Johannsen, and M. Krivelevich.  Hitting time appearance of certain spanning trees in the random graph process.  in preparation.
  * [23] P. E. Haxell.  Tree embeddings.  J. Graph Theory, 36(3):121–130, 2001.
  * [24] D. Hefetz, M. Krivelevich, and T. Szabó.  Hamilton cycles in highly connected and expanding graphs.  Combinatorica, 29(5):547–568, 2009.
  * [25] D. Johannsen, M. Krivelevich, and W. Samotij.  Expanders are universal for the class of all spanning trees (extended abstract).  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1539–1551. ACM, New York, 2012\.
  * [26] A. Johansson, J. Kahn, and V. Vu.  Factors in random graphs.  Random Structures Algorithms, 33(1):1–28, 2008.
  * [27] J. Kahn and G. Kalai.  Thresholds and expectation thresholds.  Combin. Probab. Comput., 16(3):495–502, 2007.
  * [28] J. Kahn, E. Lubetzky, and N. Wormald.  The threshold for combs in random graphs.  Random Structures Algorithms, 48(4):794–802, 2016.
  * [29] J. H. Kim.  Perfect matchings in random uniform hypergraphs.  Random Structures Algorithms, 23(2):111–132, 2003.
  * [30] J. H. Kim and S. J. Lee.  Universality of random graphs for graphs of maximum degree two.  SIAM J. Discrete Math., 28(3):1467–1478, 2014.
  * [31] J. Komlós, G. N. Sárközy, and E. Szemerédi.  Spanning trees in dense graphs.  Combin. Probab. Comput., 10(5):397–416, 2001.
  * [32] M. Krivelevich.  Triangle factors in random graphs.  Combin. Probab. Comput., 6(3):337–347, 1997.
  * [33] M. Krivelevich.  Embedding spanning trees in random graphs.  SIAM J. Discrete Math., 24(4):1495–1500, 2010.
  * [34] M. Krivelevich and B. Sudakov.  Sparse pseudo-random graphs are Hamiltonian.  J. Graph Theory, 42(1):17–33, 2003.
  * [35] M. Krivelevich and B. Sudakov.  Pseudo-random graphs, more sets, graphs and numbers.  Bolyai Soc. Math. Stud., 15:199–262, 2006.
  * [36] A. Lubotzky, R. Phillips, and P. Sarnak.  Ramanujan graphs.  Combinatorica, 8(3):261–277, 1988.
  * [37] R. Montgomery.  Embedding bounded degree spanning trees in random graphs.  preprint, arXiv:1405.6559, 2014.
  * [38] R. Montgomery.  Spanning trees in random graphs.  Adv. Math., 356:106793, 92, 2019.
  * [39] J. Park and H. Pham.  A proof of the kahn-kalai conjecture.  arXiv:2203.17207, 2022.
  * [40] M. Talagrand.  Are many small sets explicitly small?  In STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 13–35. ACM, New York, 2010.

##  Appendix A Proof of Lemma 6.1

We will also find the following result in [13], which is preciously formulated
in [9].

######  Theorem A.1.

[13, Corollary 6] Let $\Delta,m,M\in\mathbb{N}$ and $H$ be a non-empty graph
such that for every $X\subseteq V(H)$, if $0<|X|\leq m$, then
$N_{H}(X)|\geq\Delta|X|+1$ and, if $|X|=m$, then $|N_{H}(X)|\geq\Delta m+M$,
then $H$ contains every tree in $\mathcal{T}(M,\Delta)$. Moreover, for any
$T\in\mathcal{T}(M,\Delta)$ and any vertices $x\in V(T),y\in V(G)$, there
exists an embedding of $T$ into $G$ which maps $x$ to $y$.

###### Proof of Lemma 6.1.

Recall that $G$ is $m$-joined and contains disjoint vertex sets
$X=\\{x_{1},\ldots,x_{2m}\\}$, $Y=\\{y_{1},\ldots,y_{2m}\\}$ and $U$ with
$|U|\geq 20d_{1}m$. Divide $U$ into two sets, $U_{1}$ and $U_{2}$, each of
size $\frac{|U|}{2}$. Pick a maximal subset $B\subseteq U_{1}$ such that
$|B|\leq m$ and $|N(B,U_{1})|<2d_{1}|B|$. Let $V_{1}=U_{1}\setminus B$.

Claim.  Every $A\subseteq V_{1}$ with $0<|A|\leq m$ has $|N(A,V_{1})|\geq
2d_{1}|A|$.

###### Proof of claim.

Suppose for contradiction that there is a set $A\subseteq V_{1}$ with
$0<|A|\leq m$ and $|N(A,V_{1})|<2d_{1}|A|$. Then $|N(A\cup
B,U_{1})|<2d_{1}(|A|+|B|)$, so by the maximality of $B$ we must have that
$m<|A\cup B|\leq 2m$. As $G$ is $m$-joined, we have $|N(A\cup
B,U_{1})|\geq|U_{1}|-|A\cup B|-m$. Therefore,

$|N(A,V_{1})|\geq|N(A\cup B,U_{1})|-|N(B,U_{1})|\geq|U_{1}|-3m-2d_{1}m\geq
2d_{1}m.$

∎

We have that $|V_{1}|\geq|U_{1}|-m=\frac{|U|}{2}-m$ and every set $A\subseteq
V_{1}$ with $|A|\leq m$ satisfies $|N(A,V_{1})|\geq 2d_{1}|A|$. Similarly,
find a set $V_{2}\subseteq U_{2}$ with the same expansion property, with
$|V_{2}|\geq\frac{|U|}{2}-m$.

Now as $G$ is $m$-joined, if $X^{\prime}\subseteq X$ is a set of size $m$,
then $|N(X^{\prime},V_{1})|>|V_{1}\setminus X^{\prime}|-m$ and hence some
vertex $x\in X^{\prime}$ must have at least $\frac{|V_{1}|-2m}{m}\geq 2d_{1}$
neighbours in the graph $V_{1}$. Therefore, at least $m+1$ vertices in $X$
have at least $2d_{1}$ neighbours in $V_{1}$. Similarly at least $m+1$
vertices in $Y$ have at least $2d_{1}$ neighbours in $V_{2}$. Therefore, there
is some index $j\in[2m]$ for which $x_{j}$ and $y_{j}$ have at least $2d_{1}$
neighbours in $V_{1}$ and $V_{2}$, respectively.

The graph $H=G[V_{1}\cup\\{x_{j}\\}]$ then has the property that, given any
set $A\subseteq V(H)$, if $0<|A|\leq m$, then $|N_{H}(A)|\geq d_{1}|A|+1$,
and, if $|A|=m$, then $|N_{H}(A)|\geq|H|-2m$. Let $T$ be the $d$-ary tree of
height $\ell=\lceil\log m/\log d_{1}\rceil$. As $k_{j}\geq 2\log m/\log
d_{1}+1$, we have that $\lfloor k_{j}/2\rfloor-\ell-1\geq 0$. Attach a path of
length $\lfloor k_{j}/2\rfloor-\ell-1$ to the root of $T$ to get the tree
$T^{\prime}$ and let the end vertex of the path which is not the root of $T$
be $t_{1}$. The tree $T^{\prime}$ has at most
$k_{j}/2+2d_{1}^{\ell}\leq\frac{|U|}{4}+2m(d_{1}+1)<|H|-2m-2md_{1}$ vertices.
Therefore, by Theorem A.1, $H$ contains a copy of $T^{\prime}$ so that the
vertex $t_{1}$ is embedded onto the vertex $x_{j}$. Say this copy of
$T^{\prime}$ is $S_{1}$. Similarly, $G[V_{2}\cup\\{y_{j}\\}]$ contains a
$d_{1}$-ary tree with a path of length $\lceil k_{j}/2\rceil-\ell$ connecting
the root of the regular tree to $y_{j}$. Call this tree $S_{2}$.

The set of vertices in the last level of the $d_{1}$-ary trees each contain at
least $m$ vertices. Suppose these sets are $W_{1}$ and $W_{2}$ for the trees
$S_{1}$ and $S_{2}$ respectively. Then there exists an edge $v_{1}v_{2}$ with
$v_{1}\in W_{1},v_{2}\in W_{2}$. Taking the path of length $\lceil
k_{j}/2\rceil-1$ through the tree $S_{1}$ from $x_{j}$ to $v_{1}$, the path
$v_{1}v_{2}$ and the path of length $\lfloor k_{j}/2\rfloor$ through the tree
$S_{2}$ from $v_{2}$ to $y_{j}$, we obtain a desired $(x_{j},y_{j})$-path of
length $k_{j}$, with internal vertices in $U$. ∎

##  Appendix B Proof of Proposition 1.12

###### Proof.

Given constants $p,\beta>0$ and an $n$-vertex $(p,\beta)$-bijumbled graph $G$
with minimum degree $\delta\geq 4\sqrt{p\beta n}$, we prove that $G$ is an
$(n,d_{1})$-expander with $d_{1}=\frac{pn}{4\beta}\geq 100$. Indeed, it is
easy to verify that $G$ is $\frac{n}{2d_{1}}$-joined since for every two
disjoint vertex sets $X,Y$ size at least $\frac{n}{2d_{1}}=\frac{2\beta}{p}$
we have

$e(X,Y)\geq
p|X||Y|-\beta\sqrt{|X||Y|}\geq\frac{4\beta^{2}}{p}-\frac{2\beta^{2}}{p}>0.$

By definition 1.6, it remains to verify that for every $X\subseteq V(G)$ with
$|X|<\frac{n}{2d_{1}}$, $N(X)\geq d_{1}|X|$, and we split it into two cases,
where we write $Y=N(X)$.

If $|X|\geq 100\frac{\beta^{2}}{p^{2}n}$, then as $|V\setminus
X|\geq\frac{3n}{4}$ and

$p|X||Y|+\beta\sqrt{|X||Y|}\geq e(X,N(X))=e(X,V\setminus X)\geq
p|X||V\setminus X|-\beta\sqrt{|X||V\setminus X|},$

we obtain that
$p|Y|+\beta\sqrt{\frac{|Y|}{|X|}}\geq\frac{3}{4}pn-\beta\sqrt{\frac{n}{|X|}}$.
This implies that

$|Y|\geq\frac{3}{4}n-\frac{2\beta}{p}\sqrt{\frac{n}{|X|}}\geq\frac{3}{4}n-\frac{2\beta}{p}\sqrt{\frac{p^{2}n^{2}}{100\beta^{2}}}>\frac{n}{2}\geq
d_{1}|X|.$

If $|X|<100\frac{\beta^{2}}{p^{2}n}$ and assume for contradiction that
$|Y|<d_{1}|X|$, then $\delta|X|\leq e(X,X\cup Y)\leq p|X||X\cup
Y|+\beta\sqrt{|X||X\cup Y|}\leq p|X|^{2}(d_{1}+1)+\beta|X|\sqrt{d_{1}+1}$.
Recall that $d_{1}=\frac{pn}{4\beta}\geq 100$ and
$|X|<100\frac{\beta^{2}}{p^{2}n}$. It follows that

$\delta\leq p(d_{1}+1)|X|+\beta\sqrt{d_{1}+1}<50\beta+\sqrt{\frac{p\beta
n}{2}}\leq 50\sqrt{\frac{p\beta n}{400}}+\sqrt{\frac{p\beta
n}{2}}<4\sqrt{p\beta n},$

a contradiction.

The case when $G$ is an $(n,d,\lambda)$-graph is much easier. First reset
$d_{1}=\frac{d}{2\lambda}>4$ and by Expander Mixing Lemma,
$e(X,Y)\geq\frac{d}{n}|X||Y|-\lambda\sqrt{|X||Y|(1-\frac{|X|}{n})(1-\frac{|Y|}{n})}>\frac{d}{n}(\frac{\lambda
n}{d})^{2}-\frac{\lambda^{2}n}{d}=0$ for every two disjoint vertex sets $X,Y$
size at least $\frac{n}{2d_{1}}=\frac{\lambda n}{d}$. Then we will show that
for every $X\subseteq V(G)$ with $|X|<\frac{\lambda n}{d}$, $N(X)\geq
d_{1}|X|$. Suppose this is invalid for some $X\subseteq V(G)$, i.e,
$N(X)<d_{1}|X|$. Similarly set $Y=N(X)$ and thus

$d|X|\leq e(X,X\cup Y)<\frac{d}{n}|X||X\cup Y|+\lambda\sqrt{|X||X\cup
Y|}\leq\frac{d}{n}(d_{1}+1)|X|^{2}+\lambda|X|\sqrt{d_{1}+1}.$

Then it implies that
$d<\frac{d}{n}(d_{1}+1)|X|+\lambda\sqrt{d_{1}+1}\leq\lambda(\frac{d}{2\lambda}+1)+\lambda\sqrt{\frac{d}{2\lambda}+1}$,
i.e, $\frac{d}{2\lambda}<\sqrt{\frac{d}{2\lambda}+1}+1$, a contradiction to
the fact that $\lambda<\frac{d}{8}$. ∎