# Embedding induced trees in sparse expanding graphs

António Girão  and  Eoin Hurley

###### Abstract.

Inspired by the network routing literature [1], we develop what we call a
“Pre-Emptive Greedy Algorithm” to embed bounded degree induced trees in sparse
expanders. This generalises a powerful and central result of Friedman and
Pippenger to the induced setting. As corollaries we obtain that a sparse
random graph contains all bounded degree trees of linear order (whp) and that
the induced and size induced Ramsey numbers of bounded degree trees are
linear. No such linear bounds were previously known. We also prove a nearly-
tight result on induced forests in bounded degree countable expanders. We
expect that our new result will find many more applications.

AG: Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK. E-mail:
<EMAIL_ADDRESS>Research supported by EPSRC grant EP/V007327/1 and ERC
Advanced Grant no. 883810

EH: Korteweg de Vries Instituut, Universiteit van Amsterdam, Science Park 904,
1098 XH Amsterdam, The Netherlands. E-mail<EMAIL_ADDRESS>
##  1\. Background

Over the past century, a central theme in Combinatorics has been to find the
right conditions that guarantee the existence of specific subgraphs. Examples
include Dirac’s Theorem [19] from the $40$’s, Ramsey theory [53], universal
graphs [51] and multiple questions in random graph theory going back as far as
the birth of the subject itself [27]. On the applications side, the travelling
salesman problem or network routing problems can both be phrased in terms of
finding or containing appropriate subgraphs.

Dirac’s Theorem is perhaps the classical result in this area, it states that
_every_ $n$-vertex graph with minimum degree at least $n/2$ contains a
Hamilton cycle. Thirty five years later Pósa [52] gave the first proof of
Hamiltonicity (with high probability) in sparse random graphs of average
degree $\Omega(\log n)$. Implicit in his work was the following fundamental
deterministic result ($N(X)$ is the set of vertices with a neighbour in $X$).

######  Theorem 1.1 (Pósa).

Let $G$ be a graph such that every subset $X\subset V(G)$ with at most $n$
vertices satisfies $|N(X)|>3|X|-1$, then $G$ contains a path/cycle on at least
$3n-2$ vertices.

This result (and the method of Pósa rotations) quickly found other
applications, most notably in Beck’s proof [6] that the size ramsey number of
paths is linear in its order. This answered a question from the seminal paper
of Erdős, Faudree, Schelp and Rousseau [25] for which Erdős had later offered
$\$100$ [28]. Beck conjectured that such a linear upper bound should hold not
just for paths but for any bounded degree tree (see Section 1.2), but could
not prove it. Finally, Friedman and Pippenger [32] confirmed this by showing
the following beautiful generalisation of Pósa’s Theorem.

######  Theorem 1.2.

Let $G$ be a graph such that every set $X$ with at most $2n-2$ vertices
satisfies $|N(X)|\geq(d+2)|X|$, then $G$ contains every tree with maximum
degree at most $d$ on $n$ vertices.

This proved to be a fundamental result with many applications in graph theory
and in the network routing theory [29]. It was used by Alon, Krivelevich and
Sudakov [4] to embed almost spanning trees in sparse random graphs. The method
was later refined by Haxell [38] and modified by Glebov, Johannsen and
Krivelevich [35] before it was used by Montgomery [50] to show that
$G(n,C_{\Delta}\log n/n)$ contains every spanning tree of maximum degree
$\Delta$ with high probability, thus resolving a conjecture of Kahn. Friedman
and Pippinger’s method has also been recently used by Draganić, Krivelevich
and Nenadov [21] in conjunction with a rolling back technique to embed a
variety of very sparse graphs in expanders. It was used even more recently,
(again with rolling back) by Draganić, Montgomery, Munhá Correia, Pokrovskiy
and Sudakov [23] to prove a long standing conjecture of Krivelevich and
Sudakov stating that pseudorandom graphs are Hamiltonian. Finally, it is a key
ingredient in many bounds in size ramsey theory for bounded degree
(hyper)trees [39], (hyper)graphs of bounded treewidth [8, 43, 41], and other
related families of sparse (hyper)graphs [48].

Finding induced subgraphs, while equally natural, is more challenging than the
non-induced case and our understanding typically lags behind. In the case of
bounded degree trees and related sparse graphs, a technical but significant
reason for this gap in our understanding is the lack of any induced analogue
of Friedman and Pippenger’s powerful result. This is our main contribution.

Note that both in Pósa’s and Friedman and Pippenger’s results there is only a
lower bound on order of the vertex boundary of subsets. Thus large cliques
satisfy the conditions of both theorems although they do not contain any non-
trivial induced tree. We must therefore add an upper bound on average degree
of small subgraphs, that is, we must forbid small dense spots. We also need a
maximum degree condition that is trivial to satisfy in all of our applications
but we believe it to be a mere artifact of our proof (since we use the Lovász
Local Lemma). One final difference with Pósa’s and Friedman and Pippenger’s
results is an extra factor of $\Delta$ which we conjecture could be removed
completely, but removing it will likely require some new ideas.

######  Theorem 1.3.

Let $G$ be a graph with minimum degree $10^{7}\Delta$ and maximum degree at
most $\exp(\Delta/10^{9})$ such that every subgraph on at most
$(10^{7}\Delta+1)n$ vertices has average degree at most $12/5$. Then $G$
contains every tree with maximum degree at most $\Delta$ on $n$ vertices as an
induced subgraph.

One drawback of Friedman and Pippenger’s theorem is that it is non-
algorithmic. This was rectified by Dellamonica and Kohayakawa [20] who (under
a slightly stronger and more robust expansion condition) reduced the problem
to that of finding a matching in a robustly expanding bipartite graph. They
then applied an algorithmic (also online) result of Aggarwal, Bar-Noy,
Coppersmith, Ramaswami, Schieber and Sudan [1] on such matchings (the
motivation of [1] was to obtain algorithmic versions of Friedman and
Pippenger’s applications in the network routing literature). It is from this
latter proof [1] that we take our inspiration and we call the overall strategy
the “Pre-Emptive Greedy Algorithm”. Our result yields an efficient online
algorithm for finding such trees.

We anticipate that Theorem 1.3 will find many applications. We present three
examples, the first two make significant progress on two long-standing and
central problems in induced Ramsey theory and in the theory of random graphs,
while the third is a near tight result on induced forests in countable (very
strong) expanders.

###  1.1. Induced Subgraphs of Random Graphs

One of the oldest problems in the theory of random graphs is estimating the
size of the largest independent set in $G(n,p)$. This value was asymptotically
determined for $0<p<1$ constant and $n\rightarrow\infty$ by Grimmett and
Mcdiarmid in the 70’s [36]. They showed that with high probability $G(n,p)$
contains an independent set of order

$\frac{2+o(1)}{\log(1/(1-p))}\log n.$ (1)

The matching upper bound follows from the first moment method. It is natural
to wonder whether there is anything special about independent sets in this
regard or whether any sufficiently sparse induced graph of the same order
should also appear. Indeed, Erdős and Palka [26] showed in the early 80s that
the order of the largest induced tree in $G(n,p)$ was also given by (1). If
one wants find a specific tree on that many vertices, such as a path or
regular tree, then one can turn to Ruciński [55] who proved the same bound
(1), provided the maximum degree of the tree is sub-polynomial in its order.

Another regime of $G(n,p)$, the so called _sparse_ regime, where $pn=d$ is
constant, has received a lot of attention in recent decades. This regime
presents mathematical challenges not faced in the dense case (the classical
second moment approach breaks down), and further, most applications coming
from computer science, statistical physics and mathematical modelling use
graphs of constant average degree. Erdős and Palka suggested the problem of
extending their result to the sparse regime and conjectured that for all $d>1$
there exists $C_{d}$ such that $G(n,d/n)$ contains an induced tree of order
$C_{d}\cdot n$ with high probability. In other words they conjectured that
there is an induced tree of linear order in $G(n,d/n)$. In a flurry of
activity this was simultaneously proven by De la Vega [22], Frieze and Jackson
[31], Kučera and Rödl [44], and Łuczak and Palka [47]. The best constant,
$C_{d}=(1+o(1))\log d/d$, was due to De La Vega who proved that the greedy
algorithm succeeds (with high probability) by tracking stochastic differential
equations. Frieze and Jackson [30] soon showed that one can actually find an
induced path (even a cycle) of linear order, albeit for a smaller constant
$C_{d}$ and only if $d$ is sufficiently large. Suen [56] and Łuczak [49]
improved the result on induced paths to show that as long as $d>1$, $G(n,d/n)$
contains an induced path of linear order and further that for large $d$ one
could take $C_{d}=(1+o(1))\log d/d$, matching De La Vega’s bound for induced
trees. Suen’s result was a particularly elegant use of the depth first search
tree that avoided a lot of the technicalities of the stochastic differential
equation method.

Of course, the fact that $G(n,d/n)$ contains an independent set of linear
order follows from the average degree of the graph and a random greedy
algorithm finds an independent set of order $(1+o(1))(\log d/d)n$ (matching
the order of De le Vega’s induced tree). To this day this is the largest
independent set or induced tree one can find in $G(n,d/n)$ _efficiently_. This
value appears to be an algorithmic barrier related to the so-called shattering
and freezing thresholds [16] and different tools are needed to go beyond it.
Indeed, the asymptotic order of the largest independent set in $G(n,d/n)$ was
not determined until the brilliant insight of Frieze [33] who proved that if
$d$ is sufficiently large then it is

$(2+o(1))\frac{\log d}{d}n,$ (2)

extending (1). De La Vega, using Frieze’s result as a black box, showed that
the order of the largest induced tree is also (2). For all these exact
asymptotic results, the upper bounds follow from the first moment method and
the first moment gives the same bound for any fixed graph of degeneracy at
most $2$, such as a matching, a tree or a cycle. This suggests this bound may
be tight for a broader class, provided, say $d/n<p<.99$ for some appropriate
constant $d$. However, following the rapid progression of the seventies,
eighties and early nineties, the past three decades have been comparatively
slow. Draganić [24] extended Ruciński’s results beyond the constant $p$ regime
by showing that $G(n,p)$ contains any bounded degree tree of order (1),
provided $n^{-1/2}\log^{10/9}n<p<.99$. He also conjectured that the result
should apply to all trees of maximum degree $\Delta$ provided $d/n<p<.99$ for
some $d(\Delta)$ (recall that (1) and (2) coincide). Cooley, Draganić, Kang
and Sudakov [11] showed that the order of the largest induced matchings is
indeed given by (1) and (2), and they made the same conjecure. Paths are
perhaps the simplest case of the conjecture and it was only recently that
Draganić, Glock and Krivelevich [18] showed that, so long as $d$ is
sufficiently large, $G(n,d/n)$ contains an induced path of order (2) with high
probability. They further re-iterated the conjecture of Draganić. But in spite
of this precise conjecture, and the fact that we know asymptotically the order
of the longest induced cycle and the order of the largest induced tree, _no
linear bound_ for a general bounded degree induced tree in $G(n,d/n)$ was
known. We remedy this.

######  Theorem 1.4.

There is $C>0$, such that for all $\Delta\in\mathbb{N}$ and $d>2^{20\Delta}$,
$G(n,d/n)$ contains all trees with maximum degree at most $\Delta$ and order
at most $\frac{Cn}{d\log^{2}(d)}$ as induced subgraphs with high probability.

We observe our result is essentially tight as a function of $d$, up to a
$C\log^{3}(d)$ factor. We also note that we could drop the lower bound on $d$
(to a linear function of $\Delta$) provided the order of the tree is at most
$Cn/(d\log(d))^{2}$.

###  1.2. Ramsey Theory of Sparse Graphs

One of the most famous recent results in Ramsey theory is the Burr-Erdős
Conjecture, proved by Lee [46]. It states that for all $d$ there exists
$C_{d}$ such that any $n$-vertex graph with degeneracy at most $d$ has ramsey
number at most $C_{d}\cdot n$, in other words _graphs of bounded degeneracy
have linear ramsey numbers_. This extended the central result of Chvatál,
Rödl, Szemerédi and Trotter [17], who proved that bounded degree graphs have
linear ramsey numbers. The original bound from [17] on $C_{\Delta}$ came from
the regularity lemma and was thus huge. This was greatly improved by Graham,
Rödl and Ruciński [37] and further by Conlon, Fox and Sudakov [12] who showed
one can take $C_{\Delta}=2^{c\Delta\log\Delta}$. The best lower bound, coming
from bipartite graphs is $2^{c\Delta}$ (also due to [37]) and this is
conjectured to be tight (up to the constant in the exponent) by Conlon, Fox
and Sudakov [13]. If tight for all $\Delta(n)$ then this would given a nice
generalisation of the upper bound of Erdős and Szekeres (up to the constant in
the exponent).

Two natural generalisations of Ramsey theory are size ramsey theory $\hat{r}$
and induced Ramsey theory $r_{\text{ind}}$, and we further have their common
generalisation, size induced ramsey theory $\hat{r}_{\text{ind}}$.

$\displaystyle r_{\text{ind}}(H)$ $\displaystyle=\min\\{v(G):\text{in any
$2$-colouring of $E(G)$ there is a monochromatic copy of $H$ that is induced
in $G$}\\},$ $\displaystyle\hat{r}(H)$ $\displaystyle=\min\\{e(G):\text{in any
$2$-colouring of $E(G)$ there is a monochromatic copy of $H$}\\},$
$\displaystyle\hat{r}_{\text{ind}}(H)$ $\displaystyle=\min\\{e(G):\text{in any
$2$-colouring of $E(G)$ there is a monochromatic copy of $H$ that is induced
in $G$}\\}.$

Note that trivially we have $r(H)\leq
r_{\text{ind}}(H),\hat{r}(H)\leq\hat{r}_{\text{ind}}(H)$, and further
$\hat{r}(H)\leq{r(H)\choose 2}$ and
$\hat{r}_{\text{ind}}(H)\leq{r_{\text{ind}}(H)\choose 2}$. In all three of the
above cases there are trees (which have degeneracy one) that have ramsey
number superlinear in their order, thus the Burr Erdős conjecture does not
generalise. A fundamental question then asks:

> For which families of graphs are the ramsey numbers linear in the number of
> vertices?

Let $\mathcal{T}$ be the set of all trees and $\mathcal{T}_{\Delta}$ those of
maximum degree at most $\Delta$, and let $\mathcal{G}_{\Delta}$ and
$\mathcal{H}_{d}$ be the families of graphs of degree and degeneracy at most
$\Delta$ and $d$ respectively. In Table 1 we collect estimates for the maximum
ramsey number of an $n$-vertex graph from each family.

|  Paths |  $\mathcal{T}_{\Delta}$ |  $\mathcal{T}$ |  $\mathcal{G}_{\Delta}$ |  $\mathcal{H}_{d}$
---|---|---|---|---|---
$r(\cdot)$ |  $\Theta(n)$ |  $\Theta(n)$ |  $\Theta(n)$ |  $\Theta(n)$ [17] |  $\Theta(n)$ [46]
$\hat{r}(\cdot)$ |  $\Theta(n)$ [6] |  $\Theta(n)$ [32] |  ${n^{2}/4\leq\cdot\leq n^{3}\log^{4}n}$ [7], [7] |  $cne^{c\sqrt{\log n}}<\cdot<n^{2-1/\Delta-o(1)}$ [54, 57], [45] |  $\Theta(n^{2})$ [7],[46]
$r_{\text{ind}}(\cdot)$ |  $\Theta(n)$ [40] |  $\Theta(n)$ |  ${\omega(n)\leq\cdot\leq n^{2}\log^{2}n}$ [34], [7] |  $\cdot<n^{O(\Delta)}$ [14] |  $\omega(n)<\cdot<n^{O(d\log d)}$ [34],[34]
$\hat{r}_{\text{ind}}(\cdot)$ |  $\Theta(n)$ [40] |  $\Theta(n)$ |  ${n^{2}/4\leq\cdot\leq n^{3}\log^{4}n}$ [7], [7] |  $cne^{c\sqrt{\log n}}<\cdot<n^{O(\Delta)}$ [54, 57],[14] |  $n^{2}/4<\cdot<n^{O(d\log d)}$ [7],[34]
Table 1.  Bounds for the maximum ramsey number of an $n$-vertex graph from
each family; paths, bounded degree trees, trees, bounded degree graphs,
bounded degeneracy graphs. Original results are in red.

For size ramsey numbers linear bounds for paths were proven by [6]. This
answered a question from the seminal paper of Erdős, Faudree, Schelp and
Rousseau [25] for which Erdős had later offered $\$100$ [28]. With an
impressive application of the the probabilistic method Beck [6] also proved an
upper bound of $C_{\Delta}n\log^{12}n$ for trees of maximum degree $\Delta$,
while he conjectured that a bound of $C_{\Delta}n$ should hold. Friedman and
Pippenger’s [32] “beautiful” result proved a linear upper bound and this was
tightened by Haxell and Kohayakawa [39] via a subtle anyalysis of Friedman and
Pippenger’s method, resolving Beck’s conjecture111Beck actually made an even
more specific conjecture for each tree, but we will not discuss it here.. On
the other hand it was shown that no such bounds are possible for general trees
by Beck [7] or graphs of maximium degree $3$ by Rödl and Szemerédi [54]. Rödl
and Szemerédi further conjectured that for all $\Delta$ there exists
$\epsilon>0$ such that for all large $n$ the maximum size ramsey number of
maximum degree $\Delta$ graphs on $n$ vertices is between $n^{1+\varepsilon}$
and $n^{2-\varepsilon}$. This upper bound was settled by Kohayakawa, Rödl,
Schact and Szemerédi [45] while for the lower bound the best result is due to
Tikhomirov [57] who significantly improved the bound of [54] through a clever
random twist on their construction.

For induced ramsey numbers (and in fact size induced ramsey numbers), a linear
bound for paths was proved by Haxell, Kohayakawa and Łuczak [40]. Fox and
Sudakov showed that no linear upper bound for induced ramsey numbers of trees
was possible, while remarkably the case of bounded degree graphs remains wide
open. Indeed, no non-trivial (super-linear) lower bound is known while the
best upper bound due to conlon, Fox and Zhao [14] is $n^{C\Delta}$. In [34]
the authors asked if there exists a constant $C$, independent of $\Delta$,
such that the induced ramsey number of $n$-vertex graphs with maximum degree
at most $\Delta$ is at most a polynomial in $n$ of degree at most $C$ (the
coefficients may depend on $\Delta$).

Of course lower bounds from size ramsey numbers yield lower bounds for induced
size ramsey numbers, thus neither bounded degree graphs nor trees satisfy
linear upper bounds. As was remarked in the paper of Bradac, Draganić and
Sudakov [5]: ”…for bounded degree trees we know that the size-Ramsey number is
linear in their number of vertices, whereas for its induced counterpart we
have no good bounds while we have every reason to believe that the answer
should also be linear”. We prove the first linear bounds for induced and size
induced ramsey numbers of general bounded degree trees.

######  Theorem 1.5.

For all $\Delta\in\mathbb{N}$ there exists $C_{\Delta}$ such that for any tree
$T$ of maximum degree at most $\Delta$ on $n$ vertices
$\hat{r}_{\text{ind}}(T)<C_{\Delta}\cdot n$. One can take
$C_{\Delta}=10^{25}\Delta^{3}\log(\Delta)$.

Of course one can replace $\hat{r}_{\text{ind}}$ by $r_{\text{ind}}$ for free.
While this paper was in preparation Hunter and Sudakov [41] also proved the
above theorem. They proceed by very different techniques, cleverly reducing
the problem to the non-induced case, via carefully constructed subgraphs of
blowups. Their methods give worse bounds (an exponential dependency on
$\Delta$) but one nice thing is that it extends to graphs of bounded
treewidth. In order to do this they once again reduce to the non-induced case
which was proved by [8] (the two-colour case was proved simultaneously by
[43]). These results in turn use Friedman and Pippenger’s result as a black
box. Thus, it is very natural to ask if one can use our induced Friedman and
Pippenger type result to avoid any reduction to the non-induced case and
improve the quantitative bounds due to Hunter and Sudakov (which are very
large due to the use of sparse regularity).

In fact, we prove something much stronger than the above statement. Given a
family of graphs $\mathcal{G}$ a _Universal graph_ for $\mathcal{G}$ is a
graph that contains all graphs of $\mathcal{G}$ as subgraphs. The study of
such objects goes back at least as far as Moon [51], with the central question
being bounds on their size and order. The induced question is also well
studied [15] and now it is even known that an induced universal graph of order
$O(n)$ exists for the family of trees on $n$ vertices (even unbounded degrees)
[2]. The constructions are far from random. If in any colouring of our graph
$G$ we have a monochromatic (induced) universal graph then we say that our
graph is (induced) partition universal. An induced such result (also going by
the name adjacency labelling) for bounded degree graphs is what was actually
proved in [45]. Of course a density universal result is stronger again, that
is, a result that says: in any subgraph of density $\varepsilon>0$ one finds
all of said subgraphs. This is what we have proven; a density universal
theorem for bounded degree trees of order $n$ with an upper bound on the
number of edges that is linear in $n$.

######  Theorem 1.6.

For all $\Delta,n\in\mathbb{N}$ and $\varepsilon>0$ there exists a graph $G$
with less than $C(\Delta,\varepsilon)\cdot n$ edges such that any subgraph
$J\subset G$ containing $\varepsilon\cdot e(G)$ edges contains every tree of
maximum degree $\Delta$ and order at most $n$ as an induced subgraph of $G$.
One can take
$C(\Delta,\varepsilon)=\mathopen{}\mathclose{{}\left(10^{42}\Delta^{3}\log(\Delta)\log(\frac{1}{\varepsilon})^{3}}\right)/\varepsilon^{2}$.

We remark that Butler [10] showed that there is no induced universal graph of
linear order for bounded degree graphs, thus one cannot replace bounded degree
trees by general bounded degree graphs in the above theorem, even if one sets
$\varepsilon=1$ and replaces the bound on the number of edges by the same
bound on the order. It was also shown by Chung and Graham [15], that even with
$\varepsilon=1$, if we remove the bounded degree condition the theorem above
does not work222Further, a minor adjustment to the proof allows one to prove
the above theorem with a larger constant, for bounded degree forests (instead
of trees), see the discussion of rolling back in the conclusion.. In order to
see the strength of the constant, note that this implies state of the art
bounds even in the case of the multicolour size ramsey number of induced paths
(see Theorem 1.7 and discussion).

###  1.3. Dense Induced Forests in Countable Sparse Expanders

Friedman and Pippenger’s result also applies to countable graphs, where it is
best phrased in terms of Cheeger’s constant. For a countable graph $G$ we
define the vertex Cheeger constant as

$h_{v}(G)\coloneqq\inf_{X}\mathopen{}\mathclose{{}\left\\{\frac{|N(X)\backslash
X|}{|X|}}\right\\},$

where the infimum is over all finite sets $X\subset V(G)$. Friedman and
Pippenger’s result (because it is online) implies that if $d>3$ and $h(G)\geq
d$ then $G$ contains a tree with $h(T)\geq d-2$. Benjamini and Schramm [9]
proved the following stronger theorem about _spanning_ forests, which is
actually a characterisation in the case of graphs with integer Cheeger
constant.

######  Theorem 1.7 (Benjamini-Schramm [9]).

Suppose $d\geq 0$ is an integer and $G$ is a graph with $h(G)\geq d$. Then $G$
has a rooted spanning forest in which the roots have degree $d$ and all other
vertices have degree $d+2$.

One can also define the Cheeger constant in terms of edge boundaries (this is
perhaps the more classical quanitity),

$h(G)\coloneqq\inf_{X}\mathopen{}\mathclose{{}\left\\{\frac{e(X,G\backslash
X)}{|X|}}\right\\},$

where again the infimum is over finite sets $X\subset V(G)$. The use of the
edge boundary is essentially forced on you if you are looking for induced
structures. For regular graphs $G$ this Cheeger constant is dual to the
supremum of average degree over all finite subgraphs. Our technique extends,
as Friedman and Pippenger’s did, to finding an induced tree in countable
graphs and in fact it immediately yields a spanning version, in the spirit of
Benjamini and Schramm. The attentive reader will correctly object that there
is only one induced spanning subgraph of a graph. Our result is not spanning
but is _as spanning as possible_ (given the degrees of the induced forest we
embed). A _pseudoforest_ is a graph in which every component contains at most
one cycle. A $\Delta$-ary pseudoforest is a pseudoforest in which all acyclic
components are $\Delta$-ary trees and all other components are
$(\Delta+1)$-regular. A subgraph is _component-wise induced_ if each component
is an induced subgraph.

######  Theorem 1.8.

There exists $\varepsilon>0$ such that if $G$ is a $d$-regular graph with
$h(G)>d-3+\frac{1}{10^{7}\Delta+1}$ for some $\Delta<\varepsilon d$, then $G$
contains a spanning $\Delta$-ary pseudoforest $F$, that is component-wise
induced, with the property that one can turn $F$ into an induced forest by
deleting one vertex from each of its components.

There is only one $d$-regular graph with $h(G)>d-2$, and that is the
$d$-regular tree, and if $h(G)=d-2$ then $G$ is a pseudoforest. Our result
says that we can weaken this condition and still find a ”dense” family of
induced trees. The induced forest intersects all neighbourhoods in at least
$\Delta$ vertices which is essentially best possible. Further, one cannot
weaken the bound on Cheeger’s constant by much (even without the component-
wise induced condition), as is witnessed by blowing up the edges of the
$d/2$-regular tree by $K_{2,2}$’s (one replaces the vertices with independent
sets). This graph has $h(G)=d-4$ but does not even contain a binary spanning
pseudoforest with the properties described in Theorem 2.18 333To see this we
will refer to the vertices that are to be deleted in the statement of Theorem
2.18 as roots of $F$. If there is any pair $u$ and $v$ of twin vertices with
$v$ not a root then $v$ must be in the same component of $F$ as $u$ (deleting
$u$ leaves an induced tree containing neighbours of $u$). Call this component
$C$. By the inducedness of $T=C-r$ (where $r$ is the root of $C$) all
neighbours of $u$ in the tree are neighbours of $v$ in the tree. It follows
that there is at least one $4$-cycle in $C$ containing $u$ and $v$, but then
the component must have been $3$-regular (by the definition of a binary
pseudoforest) in which case there are three $4$-cycles, a contradiction. Thus
all pairs of twins are both roots, and so are all vertices, which is clearly
impossible..

### Notation

Let $N(v)$ denote the open neighbourhood of $v$ and let $N[v]\coloneqq
N(v)\cup v$ be the closed. For a set $X\subset V(G)$ we let
$N(X)\coloneqq\cup_{v\in X}N(v)$ and $N[X]=X\cup_{v\in X}N(v)$.

##  2\. Proof Overview

Our approach is inspired by the proof of Aggarwal, Bar-Noy, Coppersmith,
Ramaswami, Schieber and Sudan [1], who showed that a certain online matching
game was winnable in robustly expanding bipartite graphs. The online matching
game goes as follows. We have a graph $H=(A,B)$ and $X\subset A$ matched to a
set $Y\subset B$ (initially these will be empty). The adversary picks an
element $x\in A\backslash X$ and we have to choose an element $y\in
B\backslash Y$ and match $X\cup x$ to $Y\cup y$.

######  Theorem 2.1.

Let $H=(A,B)$ be a bipartite subgraph. Suppose that for all subgraphs
$F\subset H$ with $\deg_{F}(v)>\deg_{H}(v)/2$ for all $v\in V(H)$ we have
$|N_{F}(X)|>2|X|$ for all $X\subset A$ with $|X|\leq n$. Then there is a
polynomial time algorithm to find an online matching of order $n$ in $A$.

We call the high-level strategy used for Theorem 2.1 and in this paper the
Pre-emptive Greedy Algorithm. It was applied to the problem of efficiently
finding linear order bounded degree trees in expanders by [20]. While [20]
used Theorem 2.1 as a black box, we describe the high level strategy if one
were to open the box and run the argument in the case of bounded degree trees
(not necessarily induced). The high level strategy is the same in our case.
The game is as follows.

### The Game

We wish to embed a bounded degree tree $T$ in a graph $G$. The graph $G$ is
given to us, but $T$ is chosen by the adversary one vertex at a time. We start
from the empty tree $T$, and in each round the adversary adds one vertex to
$T$, to obtain $T^{\prime}$, maintaining that $T^{\prime}$ has both maximum
degree at most $\Delta$ and is a tree. In each round we find an embedding of
$T^{\prime}$ in $G$ that extends our earlier embedding of $T$. Formally we
find an injective homomorphism $\phi^{\prime}(T^{\prime})$ such that the
restriction of $\phi^{\prime}$ to $T$ is simply $\phi$, the homomorphism we
had from the previous round. Then in each round our adversary asks us to
extend our current tree (embedded in $G$) from a vertex of degree at most
$\Delta-1$ (in the embedded tree $T$). We lose when we cannot extend, we win
if we play $n$ rounds without losing (and thus embed an $n$-vertex tree).

We now _informally_ describe the strategy, leaving all formal definitions to
later sections.

### The Pre-Emptive Greedy Algorithm

Let us begin naïvely. If one were to greedily embed the tree, one could, after
some short amount of time, end up in the following situation. The adversary
asks you to extend the tree from a vertex $v$, but all of $v$’s neighbours are
already in the tree. This prevents you from extending your tree without
creating a cycle, so you lose. You must _pre-empt_ this situation. One thing
you could try would be to watch all the vertices in the graph each time you
extend your tree. If a vertex $v$ has too many neighbours in the tree i.e. it
is _critical_ , then one immediately _reserves_ some neighbours of $v$ that
are not in the tree. You _reserve_ these vertices for the eventuality that at
some point in the future you are asked to extend your tree from $v$. You will
not use the vertices _unless_ you are extending from $v$. Note that $v$ is not
necessarily in your tree, and it may never be.444If one wants to tighten
Theorem 1.3 by reducing the factor of $\Delta$, then this wastefulness is one
place to start. But if you are at $v$ then you can _escape_ using the reserved
vertices.

Of course, there is an issue here, there is a risk of a _criticality cascade_.
That is, when we reserve vertices for $v$ we may take neighbours away from a
different almost critical vertex $u$, forcing us to reserve vertices for $u$.
But doing that may mean that we make another vertex $w$ critical and so on,
raising two issues.

  1. (1)

Perhaps the criticality cascade consumes the whole graph (i.e. it makes every
vertex critical).

  2. (2)

Perhaps in reserving vertices for $u$ and $v$ we have used all the neighbours
of some other vertex $w$.

Thus we must be more clever. We require expansion properties of $G$ to show
that criticality cascades cannot be much larger than the current tree, this
prevents problem (1). For the second problem, rather than fixing critical
vertices one by one, each time we extend our _tree_ (not including reserving
vertices) we find all the vertices that _might_ (we can’t predict the future,
but we can bound it) be caught in a criticality cascade and call this set $C$
(this is not too big!). Because they are only _at risk_ of becoming critical,
the vertices in $C$ are not critical yet and still have many neighbours that
are not in the tree. If we require many more neighbours than $\Delta$ to be
available, then perhaps we can find a way to reserve $\Delta-1$ neighbours for
each vertex in $C$ _simultaneously_. Aggarwal, Bar-Noy, Coppersmith,
Ramaswami, Schieber and Sudan used a robust expansion condition, Hall’s
Theorem and augmenting paths to show these remedies work in the case of online
matchings (the case of trees reduces to that case). None of those tools work
in the case of induced trees however the high level strategy is similar.

  1. (1)

Extend the tree greedily until some set $C$ of vertices is at risk of being
caught in a _criticality cascade_.

  2. (2)

Simultaneously _reserve_ neighours for each of the vertices in $C$.

  3. (3)

Consider these _reserved_ vertices as part of the extended “tree” and repeat.

To summarise our earlier analysis, in order for this algorithm to work it
suffices that:

  1. (1)

Criticality cascades cannot be much larger than the set that they start from
(see Lemma 2.9).

  2. (2)

If $C$ is not too large and each vertex in $C$ has enough neighbours not in
the tree, then we can _simultaneously_ reserve $\Delta-1$ vertices for each
vertex of $C$ (see Lemma 2.13).

######  Remark.

In the above algorithm, we watch every vertex all the time, and actually
ensure that we can always extend from any vertex that has not been extended
$\Delta$ times yet. Thus we can actually build a spanning forest, this is what
allows Theorem 2.18.

As previously mentioned none of the arguments that were used in the non-
induced case work in the induced case. Thus we must introduce some tools.
These will allow us to prove Lemmas 2.9 and 2.13, before proving the main
theorem.

###  2.1. Formal Machinery

We begin by introducing directed graphs, because directing an edge from $u$ to
$v$ will be useful for encoding that we have reserved $u$ for $v$. An oriented
subgraph $D$ of a simple graph $G$ is a subgraph $H\subset G$ along with an
orientation for each of its edges $E(H)$. We view $D$ as a digraph living on
the same vertex set as $G$. For a vertex $v\in V(G)$, we define the _in-
neighbours_ of $v$ as $N^{-}_{D}(v)\coloneqq\\{u:uv\in E(D)\\}$. The following
two propositions will allow us to extend our tree or pseudoforest while only
focusing on local information. In spite of their simplicity they are crucial
to our proof.

######  Proposition 2.2.

A connected graph $T$ has an orientation such that every vertex has in-degree
at most $1$ and at least one vertex has in-degree $0$, if and only if $T$ is a
tree.

###### Proof.

The if direction is straightforward because if $T$ is a tree then we can
choose a root abitrarily and orient all edges away from the root.

For the only if direction, let $r$ be a vertex of in-degree $0$ and observe
that due to the connectedness of $T$ we have a path $P_{ru}$ from $r$ to $u$
for any $u\in V(T)\backslash r$. Because $r$ has in-degree $0$, the edge $rw$
incident to $r$ in $P_{ru}$ must be oriented away from $r$. Because every
other vertex has in-degree at most $1$ we see that all edges in $P_{ru}$ are
oriented away from $r$. Now suppose, for contradiction that there is a cycle
$C$ in $T$, and let $u$ be a vertex in the cycle with shortest distance to $r$
(in the undirected sense). By choosing appropriate paths from $r$ via $u$ to
other vertices in $C$, we see that every path within $C$, with end-vertex $u$,
must be oriented away from $u$. But this is impossible in a cycle. ∎

######  Proposition 2.3.

A graph $F$ has an orientation such that every vertex has in-degree at most
$1$ if and only if $F$ is a pseudo-forest.

###### Proof.

For the if direction we orient each component individually. If a component $C$
is a tree then we are done by Proposition 2.2 and if it contains one cycle
then we cyclically orient the cycle and orient all other edges away from said
cycle.

For the only if direction fix such an orientation and consider a component $C$
of $F$. If $C$ has a vertex of in-degree $0$ then we are done by the previous
proposition. Otherwise assume, aiming for a contradiction that $C$ has two
distinct cycles $S$ and $S^{\prime}$. Clearly both cycles must be cyclically
oriented. Thus each vertex in $S$ has an in-edge that is in $E(S)$. The same
is true for $S^{\prime}$ and it follows that all edges incident to $S$ and
$S^{\prime}$ that are not in $E(S)$ or $E(S^{\prime})$ respectively, are
oriented away from $S$ or $S^{\prime}$ respectively. In particular this means
that the cycles cannot intersect in any path (including the path that is just
a vertex), because all edges of $S^{\prime}$ with exactly one endvertex in a
maximal path $P$ in the intersection would both be oriented away from $P$,
implying $S^{\prime}$ is not cyclically oriented. Therefore by the
connectedness of $C$ there exists a path with at least one edge from $S$ to
$S^{\prime}$ and so it must start oriented away from $S$ and finish oriented
away from $S^{\prime}$, implying that there is a vertex of in-degree $2$ on
the path. ∎

Of course we are interested not only in trees, but in induced trees. Thus we
define the following object which combines the local-witness properties of
Propositions 2.2 and 2.3 with a subtle inducedness condition. The next
definition is key to our proof. Let $G$ be a graph and $D$ a (bi-)oriented
subgraph of $G$. We define $V_{\text{in}}(D)$ and $V_{\text{out}}(D)$ to be
the vertices with at least one in-neighbour or at least one out-neighbour
respectively.

######  Definition 2.4.

Given a graph $G$, an escape-way $D$ is an oriented subgraph of $G$ satisfying
that the in-degree (in $D$) of each vertex of $G$ is at most $1$ and such that
if $x,y\in V_{\text{in}}(D)$ and $xy\in E(G)$ then exactly one of $xy$ or $yx$
is in $E(D)$. The latter condition implies that $V_{\text{in}}(D)$ induces a
subgraph of $D$ in $G$.

For example, an induced forest, oriented away from its roots is an escape-way.
An induced cycle, oriented to be a directed cycle, is an escape-way.
Instructively, the following example is also an escape-way. Take an induced
forest $T_{1},\dots,T_{t}$ and orient each tree away from some root
$r_{1},\dots,r_{t}$ ($r_{i}\in T_{i}$). Now add to $E(G)$ (but not to $D$), a
clique containing $r_{1},\dots,r_{t}$. See the discussion following Corolary
2.10 for more motivation. Note that subgraphs of escape-ways are escape-ways
and if $D$ is an escape-way and $u\in N^{+}_{D}(v)$, we say that $D$ _reserves
$u$ for $v$_.

In our pre-emptive greedy algorithm we are interested in extending our escape-
way chunk by chunk. We cannot use Hall’s Theorem or the augmenting path
properties that [1] used. Thus we need to understand when two escape-ways are
compatible. While Proposition 2.2 showed that certain components of escape-
ways are trees, we also require inducedness. Therefore it is tempting to say
that if $u$ is reserved for $v$, then no neighbours of $u$ are allowed to join
the tree. This is almost correct, but its flaw is fatal; if we block all
neighbours of $u$ then we can never extend from $u$! The correct rule is that
no neighbours of $u$ are allowed to join the tree, _unless we are extending
from $u$._ For a vertex $v\in V(G)$, we define the set of _available
neighbours_ of $v$ as $A_{D}(v)\coloneqq
N_{G}(v)\backslash(V_{\text{in}}(D-v)\cup N_{D}^{-}(v))$. Note that
$A_{D}(v)\subset N_{G}(v)$. A neighbour $u$ of $v$ in $G$ is therefore not
available if either $u$ has an in-neighbour that is not $v$ _or_ $u$ is an in-
neighbour of $v$.

######  Definition 2.5.

Suppose $D$ is a (bi-)oriented subgraph of $G$. We define $K(D)$ to be the
(bi-)oriented subgraph of $G$, obtained by starting from $D$ and adding, for
all edges $uv\in E(D)$, all edges $vw$ for $w\in N_{G}(v)\setminus u$.

Observe that if $D$ is an escape-way then $K(D)$ contains no bi-oriented
edges. Further it is clear that if $D\subset D^{\prime}$ then $K(D)\subset
K(D^{\prime})$. We say an escape-way $D$ in $G$ _agrees_ with a (bi-)oriented
subgraph $H$ of $G$ if the following hold:

  * •

For all $x\in V_{\text{in}}(H)\cap V_{\text{in}}(D)$ we have
$N^{-}_{H}(x)=N^{-}_{D}(x)$, and

  * •

For all $xy\in E(H)$, $yx\not\in E(D)$.

######  Proposition 2.6.

Given escape-ways $D$ and $D^{\prime}$ in $G$ the following are equivalent:

  1. (1)

$D\cup D^{\prime}$ is an escape-way in $G$,

  2. (2)

$D^{\prime}$ agrees with $D$,

  3. (3)

For each $x\in V(G)$ we have $N^{+}_{D^{\prime}}(x)\subset A_{K(D)}(x)$.

###### Proof.

First we show that $(1)$ implies $(2)$ by showing the contrapositive. There
are two reasons $(2)$ may not hold. If there exists $x\in
V_{\text{in}}(D^{\prime})\cap V_{\text{in}}(D)$ but
$N^{-}_{H}(x)\not=N^{-}_{D}(x)$, then $x$ has in-degree at least $2$ in $D\cup
D^{\prime}$ meaning that $D\cup D^{\prime}$ is not an escape-way. If $xy\in
E(D)$ and $yx\in E(D^{\prime})$ then $D\cup D^{\prime}$ has bi-oriented edges,
meaning it is not an escape-way.

We also show that $(2)$ implies $(3)$ via the contrapositive. Suppose there
exists $y\in N^{+}_{D^{\prime}}(x)$ and $y\not\in A_{K(D)}(x)$. There could be
two reasons for $y\not\in A_{K(D)}(x)$. Suppose first $yx\in D$. Then, $xy\in
E(D^{\prime})$ and $yx\in E(D)$, hence $D^{\prime}$ does not agrees with $D$.
If on the other hand $zy\in E(D)$ for some $z\not=x$ then $y\in
V_{\text{in}}(D^{\prime})\cap V_{\text{in}}(D)$ but
$N^{-}_{H}(x)\not=N^{-}_{D}(x)$.

Finally we show that (3) implies (1), again via the contrapositive. As $D$ and
$D^{\prime}$ are escape-ways there are only two reasons that $D\cup
D^{\prime}$ would not be an escape-way. The first is that some vertex $y$ has
in-degree at least $2$ in $D\cup D^{\prime}$. But then we must have two
distinct edges $xy\in D$ and $zy\in D^{\prime}$ which would imply that $y\in
V_{\text{in}}(K(D)-z)$ and so $y\not\in A_{K(D)}(z)$. The second is that there
are $x\in V_{\text{in}}(D)$ and $y\in V_{\text{in}}(D^{\prime})$ with $xy\in
G$ but $xy,yx\not\in E(D)\cup E(D^{\prime})$. In this case $xy\in E(K(D))$ and
so $y\not\in A_{K(D)}(z)$ for any $z\not=x$.

∎

Having established these technical properties we prepare to prove that
criticality cascades cannot be too large. We will use the following bootstrap
percolation process to capture all vertices that might be caught in a
criticality cascade from $X$.

######  Definition 2.7.

Given a set of vertices $X$ in a graph $G$, we define $C(X)\subset V(G)$, the
_$d$ -critical set of $X$_ as the terminal set of the following boostrap
percolation process. We let $X_{0}\coloneqq X$ and given $X_{i}$ we let
$X_{i+1}$ be the union of $X_{i}$ with all vertices $v$ that have at least $d$
neighbours within distance at most $2$ from $X_{i}$ in $G\backslash v$ (where
$x\in X_{i}$ has distance $0$).

It follows immediately from the definition that if $X\subset X^{\prime}$ then
the $d$-critical set of $X^{\prime}$ contains that of $X$. Further, the
$(d-1)$-critical set of $X$ contains the $d$-critical set. The reason this
definition is useful is because of its relationship to escape-ways.
Essentially it provides an upper bounds on how much the available
neighbourhood can be reduced by fixing certain escape-ways.

######  Proposition 2.8.

Let $X$ be a set of vertices in a graph $G$, and let $C(X)$ be the
$d$-critical set of $X$. Suppose $B$ is an escape-way with
$V_{\text{out}}(B)\subset C(X)$. Then $|A_{K(B)}(v)|\geq\deg_{G}(v)-d$ for all
vertices $v\not\in C(X)$.

###### Proof.

Let $v\not\in C(X)$. The crucial fact is that if $u\in N(v)$ has distance at
least $3$ from $V_{\text{out}}(B)$ in $G\backslash v$, then $u\in
A_{K(B)}(v)$. By the definition of $C(X)$ if $v\not\in C(X)$ then at most
$d-1$ neighbours of $v$ have distance less than $3$ from $X$. It follows that
at most that many have distance less than $3$ from $V_{\text{out}}(B)$ in
$G\backslash v$. ∎

The following straightforward Lemma shows that large criticality cascades
generate sets that are noticeably denser than trees or cycles. This is useful
because it implies they cannot be too large in graphs with no dense spots (see
proof of main theorem).

######  Lemma 2.9.

Let $X$ be a finite set of vertices in a graph $G$, and let $C(X)$ be the
$d$-critical set of $X$.

  * •

If $G[X]$ is connected and $|C(X)|\geq 2|X|$ then there exists a graph
$H\subset G$ on at most $(2d+2)|X|$ vertices with average degree at least
$2+\frac{d-2}{2d+2}$.

  * •

If $C(X)$ is unbounded then there exist a sequence of finite graphs $H\subset
G$ with average degree approaching $3(1-\frac{1}{d+1})$.

###### Proof.

We analyse the bootstrap percolation that generates $C(X)$ from $X$, with the
added assumption that the vertices are added one by one. We break ties by a
global ordering of the vertices. This does not affect the terminal set which
we call $C\coloneqq C(X)$. We start from $X$ and let $v_{1}$ be the first
vertex added and so on. By definition $v_{i+1}$ was added because it has at
least $d$ neighbours who are at distance at most $2$ from
$X\cup\\{v_{1},\dots,v_{i}\\}$.

For the first case let $C^{\prime}=X\cup\\{v_{1},\dots,v_{|X|}\\}$. This
exists by assumption. Let the graph $H^{\prime}\subset G$ be a minimal
spanning subgraph such that the boostrap percolation w.r.t. $H^{\prime}$
starting at $X$ reaches all of $C^{\prime}$ and in the same order as above. We
define four groups of vertices in $H$. The first two are natural, the initial
set $X$ and the newly critical $C^{\prime}\backslash X$. Now for each $v\in
C^{\prime}\backslash X$, we know that there at least $d$ neighbours that
caused $v$ to be in $C^{\prime}$. Choose $d$ of these arbitrarily and call
this set $Y_{v}$. We then let $Y$ be the union of all these sets over $v\in
C^{\prime}\backslash X$. Note that $Y$ may intersect both $X$ and
$C^{\prime}\backslash X$. Finally we define $Z\coloneqq
V(H^{\prime})\backslash(C^{\prime}\cup Y)$. The role of the vertices in $Z$
(by process of elimination, and the minimality of $H^{\prime}$) is to
guarantee that the vertices in $Y$ are at distance less than $2$ from the
earlier stages of the percolation. We now construct a surjective map
$f:Y\rightarrow Z$ in order to show $|Z|\leq|Y|$. We assume $Z$ is non-empty
as the inequality is trivial otherwise. For $w\in Y$ let $j$ be the smallest
index such that $w\in Y_{v_{j}}$. Let $f(w)$ be an arbitrary vertex in $Z$ on
a path of length $2$ between $w$ and $X\cup\\{v_{1},\dots,v_{j-1}\\}$ in
$H^{\prime}$. If no such vertex exists let $f(w)$ be arbitrary in $Z$. By the
minimality of $H^{\prime}$ this map is a surjection. Indeed otherwise there
would exist a vertex $u\in Z$ whose deletion does not affect the bootstrap
percolation rule. As $Y$ has order at most $d(|C^{\prime}|-|X|)$ this implies
that the order of $H^{\prime}$ is at most
$|C^{\prime}|+(2d)(|C^{\prime}|-|X|)=(2d+2)|X|$.

We now iteratively delete leaves (degree one vertices) of $H^{\prime}$ until
we are left with a graph $H$ that has no leaves. Observe that for each $v\in
C^{\prime}\backslash X$, every pair of edges incident to $v$ in $H^{\prime}$
lie on a common cycle in $H^{\prime}$. This is because they both lie on paths
from $v$ to $X$ and $G[X]$ is connected. Therefore every edge incident to $v$
in $H^{\prime}$ is also in $H$. This allows us to lower bound the degree of
every vertex in $H$ by $2$ and every vertex in $C^{\prime}\backslash X$ (in
$H$) by $d$. By summing up the degrees in $H$ we obtain a lower bound on the
average degree. In particular

$\displaystyle\frac{\sum\deg(v)}{v(H)}$
$\displaystyle\geq\frac{d(|C^{\prime}|-|X|)+2(v(H)-(|C^{\prime}|-|X|))}{v(H)}=\frac{2v(H)+(d-2)|X|}{v(H)}$
(3) $\displaystyle=2+\frac{|X|(d-2)}{v(H)}\geq
2+\frac{|X|(d-2)}{(2d+2)|X|}=2+\frac{d-2}{2d+2},$ (4)

where in the second step we used that $|C^{\prime}|-|X|=|X|$. Thus $H$ is the
desired graph.

For the unbounded case, we can be more wasteful. We construct a sequence of
graphs $H_{0},H_{1},\dots$ with $H_{0}=G[X]$ inductively as follows. Given
$H_{i}$ if $v_{i+1}\in H_{i}$ then let $H_{i+1}=H_{i}$. Otherwise do the
following. By the definition of $v_{i+1}$ it has at least $d$ neighbours
$u_{1},\dots,u_{d}$ that are at distance $0,1$ or $2$ from $H_{i}$. We
construct $H_{i+1}$ in $j$ steps $H_{i}=H_{0}\cup
v_{i+1},\dots,H_{i}^{d}=H_{i+1}$, again inductively. For $j\in[d]$ note that
$\text{dist}(u_{j},H_{i}^{j-1})\leq 2$ by assumption. Add a path of length
$dist(u_{j},H_{i}^{j-1})$ to $H_{i}^{j-1}$ to obtain $H_{i}^{j}$. Thus we have
added $dist(u_{j},H_{i}^{j-1})$ vertices and $dist(u_{j},H_{i}^{j-1})+1$
edges. Letting $M$ denote the sum over $j$ of the aforementioned distances we
have that to get from $H_{i}$ to $H_{i+1}$ we have added $M+1$ vertices and
$M+d$ edges. Thus the ratio $(M+d)/(M+1)$ of edges added to vertices added is
minimised when $M$ is maximised. $M$ is bounded above by $2d$ and so we obtain
that the ratio of edges added to vertices added is at least

$\frac{3d}{2d+1}>\frac{3}{2}\mathopen{}\mathclose{{}\left(1-\frac{1}{d+1}}\right).$

Thus if $C(X)$ is unbounded then the average degree of the $H_{i}$’s
approaches $3d/(d+1)$. ∎

Our final lemma before we prove the main theorem states that in graphs of
small degeneracy we can find escape-ways that reserve a large portion of each
vertex’ neighbourhood for each vertex. In fact it has a few more bells and
whistles than that so we first state a corollary that captures its essence.

######  Corollary 2.10.

Let $G$ be a graph with maximum degree $\Delta$ such that every subgraph of
$G$ has average degree at most $3$. There exists an escape-way $D$ in $G$ with
$\deg^{\text{out}}_{D}(v)\geq\frac{|\deg(v)|}{10^{7}}-5\log\Delta$ for all
$v\in V(G)$.

This result sheds light on the delicate definition of an escape-way. We have
already seen in Propositions 2.2 and 2.3 that the definition is sufficient to
encode trees and pseudoforests. We now show that very slight alterations to
the definition of an escape-way make Corollary 2.10 impossible.

First suppose we required $V_{\text{in}}(D)\cup V_{\text{out}}(D)$ (instead of
just $V_{\text{in}}(D)$) to induce a subgraph of $D$ in $G$. We construct $G$
as follows. Consider a cycle $C$ of length $\ell$ with a single chord and add
$d$ pendant edges to each vertex of the cycle. Then $G$ has maximum degree
$d+3$ and every subgraph has average degree less than $3$. If $d$ is large
enough then every vertex of the cycle must be in $V_{\text{out}}(D)$ for any
$D$ as in Corollary 2.10. But if $V_{\text{in}}(D)\cup V_{\text{out}}(D)$
induced a subgraph of $D$ in $G$ then all of the edges in $C$ as well as the
chord are in $D$. But orienting these edges will create a vertex of in-degree
$2$, which contradicts that $D$ is an escape-way.

Secondly suppose that instead of requiring that $V_{\text{in}}(D)$ induces a
subgraph of $D$ in $G$ we required that our escape-ways are unions of disjoint
stars (oriented away from the root). Let $G$ be the $d$-ary tree of depth $3$.
Thus $G$ has max degree $d+1$ and all subgraphs have average degree less than
$2$. If $d$ is large then root $r$ must have at least one out-neighbour, say
$v$. But then if $v$ also has an out-neighbour $V_{\text{in}}(D)$ the stars
(one rooted $r$ and one at $v$) are not disjoint. Thus if $d$ is large, there
is no $D$ satisfying Corollary 2.10.

The maximum degree condition in Corollary 2.10 is due to our use of the Lovász
Local Lemma.

######  Theorem 2.11 (Lovász Local Lemma).

Suppose there are a set of events such that each event is mutually independent
of all but $d$ other events. If each event occurs with probability less than
$1/ed$ then the probability that none of the events occur is positive.

We will also require McDiarmid’s Inequality for Lipschitz functions of
independent random variables.

######  Lemma 2.12.

Suppose $X_{1},\dots,X_{m}$ are independent binary random variables and
$f:\\{0,1\\}^{m}\rightarrow\mathcal{R}$ is an $s$-Lipschitz function. Then for
any $t>0$

$\mathbb{P}\mathopen{}\mathclose{{}\left[\mathbb{E}[X]-X>t}\right]<\exp\mathopen{}\mathclose{{}\left(-\frac{2t^{2}}{ms^{2}}}\right).$

We now state the lemma in full detail. Given a subgraph $G^{\prime}\subset G$
we denote by $A_{D}^{G^{\prime}}(v)\coloneqq A_{D}(v)\cap N_{G^{\prime}}(v)$,
the available neighbours of $v$ in $G$ with respect to $D$, that are also
neighbours of $v$ in $G^{\prime}$.

######  Lemma 2.13.

Suppose $F$ is an undirected graph with maximum degree $\Delta$ such that all
subgraphs have average degree at most $3$. Further suppose $F$ has a spanning
subgraph $G$ and an oriented subgraph $H$. Then $F$ has an escape-way $D$ that
agrees with $H$, such that
$\deg^{\text{out}}_{D}(v)\geq\frac{|A_{H}^{G}(v)|}{10^{7}}-5\log\Delta$ for
all $v\in V$.

The reason for two graphs $F$ and $G$ is to prepare for our ramsey theoretic
applications ($G$ will be a large monochromatic subgraph). We cannot just
forget about $F$ because in induced ramsey theory one wants a monochromatic
subgraph that is induced in the original graph. For the oriented subgraph $H$,
the motivation is to encode the contraint that the escape-way $D$ that we seek
should combine with an escape-way $D^{\prime}$ that we already have, to give a
bigger escape-way (see proof of main theorem).

###### Proof.

The idea is to use the average degree condition to bound the degeneracy by $C$
and find an orientation of $F$ in which all but $C$ of the available
neighbours of each vertex are out-neighbours. We then sample a random subgraph
of this orientation and carefully resolve clashes (keeping the earlier edge in
the degeneracy ordering) to turn it into an escape-way called $\mathbf{D}$. In
expectation this will leave everyone with a large out-neighbourhood and we
complete the proof by showing concentration (once again using the average
degree condition) and applying the LLL.

Fix an ordering of $V(G)$ which witnesses that the degeneracy of $F$ is at
most $C$. Namely, writing $V(J)=V(G)=\\{v_{1},\dots,v_{n}\\}$ we have
$|N(v_{j})\cap\\{v_{1},\dots,v_{j-1}\\}|\leq C$ for all $2\leq j\leq n$.
Orient all the edges in $E(J)\backslash E(H)$ so that for all such edges
$v_{i}v_{j}$ we have $i<j$, and copy the orientation of all other edges from
$H$. Call the resulting digraph $G^{\prime\prime}$. Let $G^{\prime}$ be the
subdigraph of $G^{\prime\prime}$ consisting of edges of the form $vu$ for
$u\in A_{H}^{G}(v)$ and observe that
$|N^{\text{out}}_{G^{\prime}}(v)|\geq|A_{H}^{G}(v)|-C$ for $v\in V(G)$.

Now we choose a subdigraph $\mathbf{J}$ of $G^{\prime}$ by including each edge
of $G^{\prime}$ independently with probability $p\coloneqq 1/C^{2}$. We then
deterministically resolve clashes, choosing a further subdigraph $\mathbf{D}$
of $\mathbf{J}$ as follows. For each $i\in[n]$, if:

  1. (1)

$\deg^{\text{in}}_{\mathbf{J}}(v_{i})\geq 2$ or

  2. (2)

$\deg^{\text{in}}_{\mathbf{J}}(v_{i})=1$ and there exists $u\in
N^{\text{in}}_{G^{\prime\prime}}(v_{i})\backslash
N^{\text{in}}_{\mathbf{J}}(v_{i})$ with $\deg^{\text{in}}_{\mathbf{J}}(u)\geq
1$,

then we delete all edges of $\mathbf{J}$ that are oriented towards $v_{i}$. We
observe that $\mathbf{D}$ is a deterministic function of $\mathbf{J}$, and
that by construction $\mathbf{D}$ is an escape-way. Indeed, $(1)$ ensures that
the indegree of any vertex is at most $1$ and $(2)$ ensures that the vertices
of indegree at least $1$ induce (in $F$) a subgraph of $\mathbf{D}$. We denote
by $\mathbf{J}_{ww^{\prime}}$ the event that $\\{ww^{\prime}\in
E(\mathbf{J})\\}$, for each edge $ww^{\prime}\in E(G^{\prime})$. Thus
$\mathbf{J}$ can be viewed as $\prod_{e\in E(G^{\prime})}\mathbf{J}_{e}$.
Similarly, we denote, for each edge $ww^{\prime}\in E(G^{\prime})$, by
$\mathbf{D}_{ww^{\prime}}$, the event that $\\{ww^{\prime}\in
E(\mathbf{D})\\}$.

######  Claim 2.14.

For each $vu\in E(G^{\prime})$ we have $\mathbb{P}[\mathbf{D}_{vu}]\geq
1/(eC^{2})$.

###### Proof.

Consider an arbitrary edge $vu\in E(G^{\prime})$. The probability that $vu\in
E(\mathbf{J})$ is simply $\mathbb{P}[\mathbf{J}_{vu}]=p$. Then the probability
of $\mathbf{D}_{vu}$ given $\mathbf{J}_{vu}$ is precisely the probability that
for all $w\in N^{\text{in}}_{G^{\prime}}(u)\backslash v$ we have $wu\not\in
E(\mathbf{J})$ (i.e. not $\mathbf{J}_{wu}$) and
$\deg^{\text{in}}_{\mathbf{J}}(w)=0$. In other words, the probability that a
set of at most $C(C-1)$ edges that appeared in $G^{\prime}$ do not appear in
$\mathbf{J}$. This occurs with probability at least $(1-p)^{C(C-1)}$.
Recalling that $p=1/C^{2}$, and using the relation that
$1-1/x\geq\mathrm{e}^{-(1/(x-1))}$ which holds for all reals $x>1$, we can
lower bound this probability by $\mathrm{e}^{-\frac{C(C-1)}{C^{2}-1}}\geq
1/\mathrm{e}$. Thus the probability of the event $\mathbf{D}_{vu}$ is at least
$p(1-p)^{C(C-1)}\geq 1/(eC^{2})$. ∎

######  Claim 2.15.

For each vertex $v\in V(G)$ and edge $e\in E(G^{\prime})$, changing the
outcome of $\mathbf{J}_{e}$ effects the outcome of at most $8$ events
$\mathbf{D}_{vu}$.

###### Proof.

Recall that $\mathbf{D}$ is a deterministic function of $\mathbf{J}$. The
event $\mathbf{D}_{vu}$ depends on only: the event $\mathbf{J}_{vu}$, and for
each $w\in N^{\text{in}}_{G^{\prime}}(u)\backslash u$ the events
$\mathbf{J}_{wu}$ and $\mathbf{J}_{w^{\prime}w}$ for each $w^{\prime}\in
N^{\text{in}}_{G^{\prime}}(w)$. The same can be said for $\mathbf{D}_{e}$ for
any edge $e\in E(G^{\prime})$. Thus if $\mathbf{D}_{vu}$ depends on
$\mathbf{J}_{qw}$ then it must be that

  * •

$qw=vu$ or

  * •

$w=u$ or

  * •

$w\neq v$ and $wu\in E(G^{\prime})$.

The first two candidates can hold for at most one vertex $u$ in total. Thus if
$\mathbf{J}_{qw}$ effects $\ell$ events $\mathbf{D}_{vu}$ then there must be
at least $\ell-1$ vertices in the common neighbourhood of $w$ and $v$. But
this implies that there exists a small subgraph of average degree
$\frac{4(\ell-1)}{(\ell-1)+2}$. Thus by the condition that all subgraphs have
average degree at most $3$, we have $\ell\leq 8$. ∎

######  Claim 2.16.

For all $v\in V(G^{\prime})$ we have

$\mathbb{P}\mathopen{}\mathclose{{}\left[\deg^{\text{out}}_{\mathbf{D}}(v)<\frac{|A_{H}^{G}(v)|-C}{2eC^{2}}}\right]<\exp\mathopen{}\mathclose{{}\left[-\frac{(|A_{H}^{G}(v)|-C)^{2}}{|A_{H}^{G}(v)|\cdot
200\cdot e^{2}C^{6}}}\right].$

###### Proof.

Let $v\in V(G^{\prime})$ be arbitrary. As
$|N^{\text{out}}_{G^{\prime}}(v)|\geq|A_{H}^{G}(v)|-C$ we have, by Claim 2.14
that
$\mathbb{E}[|\deg^{\text{out}}_{\mathbf{D}}(v)|]\geq(|A_{H}^{G}(v)|-C)/(eC^{2})$.
Further $\deg^{\text{out}}_{\mathbf{D}}(v)$ is a function of
$\\{\mathbf{J}_{vu}\\}$ where $u$ ranges over
$N^{\text{out}}_{G^{\prime}}(v)$. Recall that
$\deg^{\text{out}}_{\mathbf{D}}(v)$ depends on at most
$m\coloneqq|A_{H}^{G}(v)|C^{2}$ events. Further by Claim 2.15 it depends on
these events in a Lipschitz manner with constant $8$. Therefore we can apply
McDiarmid’s inequality with $t=\frac{|A_{H}^{G}(v)|-C}{2eC^{2}}$,
$m=|A_{H}^{G}(v)|C^{2}$ and $s=8$ to get

$\mathbb{P}\mathopen{}\mathclose{{}\left[\deg^{\text{out}}_{\mathbf{D}}(v)<\frac{|A_{H}^{G}(v)|-C}{2eC^{2}}}\right]<\exp\mathopen{}\mathclose{{}\left[-\frac{2\cdot
t^{2}}{m\cdot
s^{2}}}\right]\leq\exp\mathopen{}\mathclose{{}\left[-\frac{2(|A_{H}^{G}(v)|-C)^{2}}{|A_{H}^{G}(v)|C^{2}\cdot
8^{2}\cdot 4e^{2}C^{4}}}\right].$

∎

Call the quantity inside the exponent of the end last equations $q_{v}$. For
the final step we wish to apply the LLL to conclude that with positive
probabilty we have that $\mathbf{D}$ satisfies the conditions of the Lemma. We
note that if $q_{v}\leq 5\log\Delta$ then the statement holds trivially for
$v$ as $\deg^{\text{out}}_{D}(v)\geq 0$. For all other $v\in V(G)$ we will
introduce a bad event
$\mathbf{B}_{v}\coloneqq\\{\deg^{\text{out}}_{\mathbf{D}}(v)<\frac{|A_{H}^{G}(v)|-C}{2eC^{2}}\\}$.
Clearly if no bad events occur then the guarantees of the Lemma are satisfied.
We have, by Claim 2.16, that
$\mathbb{P}[\mathbf{B}_{v}]<\exp\mathopen{}\mathclose{{}\left[-q_{v}}\right]$
and by assumption $q_{v}>5\log\Delta$. It follows that
$\mathbb{P}[\mathbf{B}_{v}]<1/\Delta^{5}$.

Now we upper bound the number of dependent bad events per bad event. If for
some pair $u,v\in V(G^{\prime})$, we have that $\mathbf{B}_{u}$ and
$\mathbf{B}_{v}$ are dependent then there must be a vertex $w$ at distance at
most $2$ from both $u$ and $v$ in $J$. Thus for each $u$ there are at most
$\Delta^{4}$ vertices $v$ such that $\mathbf{B}_{u}$ and $\mathbf{B}_{v}$ are
dependent. We apply the LLL via the relation $e\cdot q\cdot
d\leq\mathrm{e}\cdot\frac{1}{\Delta^{5}}\cdot\Delta^{4}=\frac{\mathrm{e}}{\Delta}\leq
1$. The LLL then tells us that with positive probability none of the events
$\mathbf{B}_{v}$ occur. Further, as observed earlier, with probability one,
$\mathbf{D}$ is an escape-way, and it follows that there exists at least one
escape-way $D$ as guaranteed by the Lemma. Substituting $C=3$ completes the
proof with the estimate $q_{v}>|A_{H}^{G}(v)|/10^{7}$. ∎

We are now ready to prove the following result which is a stronger version of
our main result (Theorem 1.3).

######  Theorem 2.17.

Let $\Delta\in\mathbb{N}$ and suppose $G$ is a graph of maximum degree at most
$\exp(\Delta/10^{9})$ such that all subgraphs on at most $(10^{7}\Delta+1)n$
vertices have average degree at most $12/5$. Further suppose $J\subset G$ is a
spanning subgraph with minimum degree at least $10^{7}\Delta$. Then $J$
contains all trees on $n$ vertices with maximum degree at most $\Delta$ as
induced subgraphs of $G$.

###### Proof.

Let $T$ be a fixed tree on $n$ vertices and maximum degree $\Delta$. We pick a
root $r\in V(G)$. We will follow an online process extending locally our
current tree $T_{i}$ whereby at each step an adversary picks a vertex $x$ of
degree at most $\Delta-1$ from the current tree and we extend the tree from
that $x$.

The Pre-emptive Greedy Algorithm. Throughout the process we will maintain an
escape-way $B_{i}$ which contains $T_{i}$ rooted at $r$. We will write
$D_{i}\coloneqq K(B_{i})$. On a high level, one can think of $B_{i}$ as those
edges which are reserved for (possibly) extending the current tree $T_{i}$.
The directed-ness of an edge in $B_{i}$, say from $u$ to $v$, is to signal the
fact that _if_ the edge $uv$ is ever used, then that is because we extend
_from_ $u$ _to_ $v$.

In step one our adversary chooses a root $r=T_{1}\subset T$ and we choose any
vertex $r\in V(G)$ to be the root. The root requires some special treatment
(an unimportant technicality). We add all edges from $r$ to $N_{G}(r)$ into
$B_{1}$ and we delete all other vertices adjacent to $r$ from $J$. Due to the
condition that there are no small graphs of average degree at least $12/5$ co-
degrees are bounded $7$ and this deletion reduces the degree of any vertex in
our graph by at most $7$. For convenience and because $d\geq 1000$, we shall
ignore this $7$ and continue to call the remaining graph $J$. We now state the
formal properties to be maintained throughout the whole process. Suppose at
step $i$, we have a tree $T_{i}$ in $G$ and an escape-way $B_{i}$ in _both_
$G$ and $J$. We will always assume there is an isomorphism $f$ from $T_{i}$ to
a sub-tree of $T$ and for ease of notation identify $x\in T_{i}$ with $f(x)$.
We let $X_{i}$ denote the non-leaf vertices of $T_{i}$ and let $C_{i}\coloneqq
C(X_{i})\subseteq V(J)$ denote the $d$-critical vertices of $X_{i}$. Note that
$X_{i}$, $C_{i}$ and $D_{i}$ are determined by $T_{i}$ and $B_{i}$. We will
have $B_{i}\subseteq B_{i+1}$ and $T_{i}\subset T_{i+1}$, and thus
$X_{i}\subset X_{i+1}$, $D_{i}\subseteq D_{i+1}$ and $C_{i}\subseteq C_{i+1}$
for all $i\in[n-1]$. We further ensure:

  1. (1)

$T_{i}\subset B_{i}$;

  2. (2)

$V_{\text{out}}(B_{i})=C_{i}$;

  3. (3)

For every $v\in C_{i}$ we have $\deg^{+}_{B_{i}}(v)\geq\Delta-1$ and
$\deg_{B_{i}}(r)=\deg_{G}(r)$.

As $C_{1}=r$ it is trivial to see that the conditions are satisfied initially.
We now proceed by induction and assume we have $T_{i},B_{i},X_{i},C_{i}$ and
$D_{i}$ as described for some $i\in[n-1]$. At each step, an adversary chooses
a vertex $x$ from the current tree $T_{i}$ with $d_{T_{i}}(x)<\Delta$ and asks
us to append a leaf to $x$. We now show how we can maintain the above
properties while extending $T_{i}$. Let $x\in T_{i}$ be the chosen vertex.

###  2.2. Case $1$: $x\in C_{i}$.

We simply choose an out-neighbour of $x$, say $y\in N^{+}_{B_{i}}(x)\backslash
N_{T_{i}}(x)$. This exists by (3) since $d_{T_{i}}(x)\leq\Delta-1$ and because
if $x$ is not the root then it has an in-neighbour in $B_{i}$. We let
$T_{i+1}=T_{i}\cup xy$. We then define $B_{i+1}\coloneqq B_{i}$ and note that
it contains $T_{i+1}$.

###  2.3. Case $2$: $x\notin C_{i}$.

In this case, $x$ has many available neighbours, and so we would like to
simply add them to our tree. However, informally, adding arbitrary edges to
$B_{i}$ may trigger a criticality cascade. In order to find out which vertices
near $x$ might be so affected we look at the $d$-critical set
$C_{i+1}\coloneqq C(C_{i}\cup x)$ of $C_{i}\cup x$. Because $C_{i}=C(X_{i})$
we have that $C_{i+1}=C(X_{i}\cup x)$.

We observe that $|C_{i+1}|<2|X_{i}\cup x|$. Indeed suppose otherwise, then the
$100$-critical set of $X_{i}\cup x$ is at least as large and so by Lemma 2.9,
there would exists a graph $H\subset J$ of order at most $300n$ and average
degree at least $12/5$. This would contradict the assumptions of the theorem.
Thus, in particular, we have that $C^{*}\coloneqq C_{i+1}\backslash C_{i}$ has
order most $n$. Further, because $V_{\text{out}}(B_{i})=C_{i}$ by induction,
Proposition 2.8 tells us that $|A^{G}_{D_{i}}(v)|\geq\deg_{G}(v)-d\geq d$ for
all $v\not\in C_{i}$ (and thus all $v\in C^{*})$.

For each $v\in C^{*}$ we add $d$ vertices from $A^{G}_{D_{i}}(v)$, along with
$v$, to a set we call $C^{+}$. Thus $|C^{+}|\leq(d+1)|C^{*}|\leq(d+1)n$. We
now give as input to Lemma 2.13, the graph $J[C^{+}]$ as $F$, the graph
$G[C^{+}]$ as $G$ and $D_{i}$ the (bi)oriented subgraph of $J$ as $H$. We
input the maximum degree of $\exp(d/10^{9})$ and note that this $F$ has
degeneracy at most $3$, because it has order most $10^{7}\Delta n$ (degeneracy
is at most the maximum average degree over all subgraphs). Lemma 2.13
therefore gives us an escape-way $I$, that agrees with $D_{i}$, such that the
out-degree of each vertex $v\in C^{*}$ is at least
$\frac{d}{10^{7}}-5\frac{d}{10^{9}}$, which is at least $\Delta$ because
$d>10^{7}\Delta$. We obtain $I^{\prime}$ from $I$ by deleting all edges whose
initial vertex is not in $C^{*}$. We let $B_{i+1}$ be the union of $B_{i}$ and
$I^{\prime}$.

Crucially $I^{\prime}$ agrees with $D_{i}=K(B_{i})$ because $I$ agrees with
$D_{i}$ and so $B_{i+1}$ is an escape-way by Proposition 2.6. We now let
$T_{i+1}\coloneqq T_{i}\cup xy$ for some $y\in N_{B_{i+1}}(x)$, so that
clearly $T_{i+1}\subset B_{i+1}$ as required by (1). To see (3) we first note
it holds by induction for $v\in C_{i}$ because $B_{i}\subset B_{i+1}$ and for
$v\in C^{*}$ by the construction of $I^{\prime}$. Similarly for (2). This
completes the induction step.

Thus we obtain our tree $T_{n}$ as a subgraph of our escape-way $B_{n}$ in $G$
and $J$. We must check that is induced. First note that because
$\deg_{B_{i}}^{+}(r)=\deg_{G}(r)$ and all other neighbours were deleted, we
have that the in-degree of $r$ is zero. By Proposition 2.2 this implies that
the component of $B_{n}$ containing $r$ is a tree. Further by the definition
of escape-way, $V_{\text{in}}(B_{n})$ induces a subgraph of $B_{i}$, thus all
that remains to note is that any neighbours of $r$ that are in the tree are
out-neighbours of $r$. This completes the proof.

∎

######  Theorem 2.18.

There exists $\varepsilon>0$ such that if $G$ is a $d$-regular graph with
$h(G)>d-3+\frac{1}{10^{7}\Delta+1}$ for some integer $\Delta<\varepsilon d$,
then $G$ contains a spanning $\Delta$-ary pseudoforest $F$, that is component-
wise induced, with the property that one can turn $F$ into an induced forest
by deleting one vertex from each of its components.

###### Proof.

We run the same argument as in the proof of Theorem 1.3, with some minor
adjustments. Firstly in the online game, the adversary is now allowed to ask
us to add neighbours to any vertex in $G$, this does not effect the process it
just means that the current $T_{i}$ may not be connected. We enumerate the
vertices of $G$ and assume that the adversary will ask us to extend the
vertices in that order. We always extend from a vertex $\Delta$ times in a
row. We choose the root $r$ arbitrarily, but we do not do anything to its
neighbours and we just proceed with the induction. Case $1$ is identical but
in Case $2$ we only require that the critical sets are finite and we show so
by applying Lemma 2.9. It is clear that as our adversary will eventually ask
us to extend $T_{i}$ from every vertex and give it out-degree $\Delta$ that we
obtain in the limit a spanning escape-way $D$ with all out-degrees $\Delta$.
By Proposition 2.3 this is a spanning pseudoforest, and it is straightforward
to see that it is $\Delta$-ary.

We now describe which vertices to delete. By Proposition 2.2 if a component of
$D$ has a cycle then it has no vertex of in-degree $0$. For each component we
either delete one vertex from the at most one cycle, or we delete the at most
one vertex with in-degree $0$ (if there two vertices of indegree $0$ in the
same component, then any path between them must have a vertex with indegree at
least $2$). Thus all remaining vertices are in $V_{\text{in}}(D)$ and so the
resulting graph is induced. Further, there are no cycles because we deleted a
vertex from each. ∎

##  3\. Induced trees in random graphs

We will show how we can derive easily Theorem 1.4 from Theorem 1.3. We restate
it below for convenience of the reader.

######  Theorem 1.4.

There is $C>0$, such that for all $\Delta\in\mathbb{N}$ and $d>2^{20\Delta}$,
$G(n,d/n)$ contains all trees with maximum degree at most $\Delta$ and order
at most $\frac{Cn}{d\log^{2}(d)}$ as induced subgraphs with high probability.

###### Proof.

Let $G\sim G(n,d/n)$, where $d>2^{20\Delta}$ and $\Delta\geq 1$. It is a
simple observation that the following holds w.h.p.

  1. (i)

For every $S\subset V(G)$, $e(G[S])=\frac{d|S|^{2}}{2n}\pm dn/10$;

  2. (ii)

For every $S\subset V(G)$, with
$\frac{n}{200d\log(d)}\leq|S|\leq\frac{n}{100d\log(d)}$,
$e(G[S])\leq(1+1/5)|S|$;

  3. (iii)

There are at most $n/4$ vertices with degree greater than $20d$.

Let $G$ satisfy the above. Delete from $G$ all vertices of degree greater than
$20d$. By (iii), we obtain an induced subgraph $G^{\prime}\subset G$ on at
least $3n/4$ vertices. Let $S\subset V(G^{\prime})$ be a maximal subset of
size at most $\frac{n}{200d\log(d)}$ with $e(G^{\prime}[S])>(1+1/5)|S|$. By
assumption $|S|\leq\frac{n}{200d\log(d)}$. Delete $S$ and let
$G^{\prime\prime}\coloneqq G[V(G^{\prime})\setminus S]$. It is clear that by
maximality and (ii) no $S^{\prime}\subset V(G^{\prime\prime})$ of size at most
$\frac{n}{200d\log(d)}$ spans more than $(1+1/5)|S|$ edges. Furthermore, by
(ii), $|G^{\prime\prime}|\geq n/2$ and by (i), we know
$e(G^{\prime\prime})\geq\frac{d}{8}|G^{\prime}|$. Finally, passing to an
induced subgraph $G^{\prime\prime\prime}\subset G^{\prime\prime}$ with minimum
degree at least $d/16$, we have thus constructed an induced subgraph of
$G(n,d/n)$ with $\delta(G^{\prime\prime\prime})\geq d/16$ and
$\Delta(G^{\prime\prime\prime})\leq 20d$. Moreover, (by (i)), we know
$|G^{\prime\prime\prime}|\geq n/50$. It is easy to see
$G^{\prime\prime\prime}$ satisfies the conditions of Theorem 1.3 with
$n\coloneqq\frac{n}{10^{14}d\log^{2}(d)}$ and $\Delta\coloneqq 10^{6}\log(d)$.

∎

##  2\. Induced size Ramsey of trees

In this section, we will prove Theorem 1.6 which trivially implies Theorem 1.5
by taking $\varepsilon=1/2$. As above, we restate the theorem for convenience
of the reader.

######  Theorem 1.6.

For all $\Delta,n\in\mathbb{N}$ and $\varepsilon>0$ there exists a graph $G$
with less than $C(\Delta,\varepsilon)\cdot n$ edges such that any subgraph
$J\subset G$ containing $\varepsilon\cdot e(G)$ edges contains every tree of
maximum degree $\Delta$ and order at most $n$ as an induced subgraph of $G$.
One can take
$C(\Delta,\varepsilon)=\mathopen{}\mathclose{{}\left(10^{42}\Delta^{3}\log(\Delta)\log(\frac{1}{\varepsilon})^{3}}\right)/\varepsilon^{2}$.

###### Proof.

Let
$N\coloneqq\frac{10^{30}n\log(\Delta)\Delta^{2}\log(\frac{1}{\varepsilon}))^{3}}{\varepsilon}$
and $d\coloneqq\frac{10^{12}\Delta\log(\frac{1}{\varepsilon})}{\varepsilon}$
Let $G\sim G\mathopen{}\mathclose{{}\left(N,d/N}\right)$ then as above we know
that w.h.p. the following holds.

  1. (i)

For every $S\subset V(G)$, $e(G[S])=\frac{d|S|^{2}}{2N}\pm dN/10$;

  2. (ii)

For every $S\subset V(G)$, with
$\frac{N}{200d\log(d)}\leq|S|\leq\frac{N}{100d\log(d)}$,
$e(G[S])\leq(1+1/5)|S|$;

  3. (iii)

There are at most $N/4$ vertices with degree greater than $20d$.

Let $G$ satisfy the above and delete all vertices of degree greater than
$20d$. We obtain an induced subgraph $G^{\prime}$ on at least $3N/4$ vertices
with $\Delta(G_{1})\leq 20d$. Let $S\subset V(G^{\prime})$ be a maximal subset
of size at most $\frac{N}{200\log(d)}$ with $e(G^{\prime}[S])>(1+1/5)|S|$. By
assumption $|S|\leq\frac{n}{200d\log(d)}$. Delete $S$ and let
$G^{\prime\prime}\coloneqq G[V(G^{\prime})\setminus S]$. It is clear that by
maximality and (ii) no $S^{\prime}\subset V(G^{\prime\prime})$ of size at most
$\frac{n}{200d\log(d)}$ spans more than $(1+1/5)|S|$ edges. Furthermore, by
(ii), $|G^{\prime\prime}|\geq N/2$ and by (i), we know
$e(G^{\prime\prime})\geq\frac{d}{8}|G^{\prime}|$. Finally, passing to an
induced subgraph $G^{\prime\prime\prime}\subset G^{\prime\prime}$ with minimum
degree at least $d/16$, we have thus constructed an induced subgraph of
$G(N,d/N)$ with $\delta(G^{\prime\prime\prime})\geq d/16$ and
$\Delta(G^{\prime\prime\prime})\leq 20d$. Moreover, (by (i)), we know
$|G^{\prime\prime\prime}|\geq N/50$. $G^{\prime\prime\prime}$ will be the
desired graph.

All we need to show is that given any $J\subset G^{\prime\prime\prime}$ with
$e(J)\geq\varepsilon e(G^{\prime\prime})$, $J$ contains an induced copy (in
$G^{\prime\prime\prime}$) of every tree on $n$ vertices and maximum degree
$\Delta$. We first let $J^{\prime}\subset J$ be an induced subgraph of $J$
with minimum degree $\varepsilon d/20\geq
10^{7}(10^{6}\Delta\log(1/\varepsilon))=10^{7}f$, where $f\coloneqq
10^{6}\Delta\log(1/\varepsilon)$. Moreover, by assumption
$\Delta(G[V(J^{\prime})])\leq 20d\leq 2^{f/10^{9}}$ and every subset $|S|$ of
size at most
$10^{10}n\Delta\log(\Delta)\log(\frac{1}{\varepsilon})\geq(10^{7}f+1)n$ spans
at most $(1+1/5)|S|$ edges. We may now invoke Theorem 2.17 with
$G^{\prime\prime\prime}\coloneqq G$, $J\coloneqq J$, $\Delta\coloneqq f$ and
$n\coloneqq n$. ∎

We now easily derive an induced size ramsey result for $q$ colours by taking
$\varepsilon\coloneqq 1/q$ in Theorem 1.6

######  Theorem 1.7.

There is $C>0$ such that the following holds. Let $q,\Delta,n\geq 1$. Then,
there is a graph $G$ on at most $C\Delta^{3}\log(\Delta)q^{2}\log(q)^{3}n$
edges such that in every $q$-edge-colouring of $G$ there is a colour class
which spans all trees $T$ on at most $n$ vertices and $\Delta(T)\leq\Delta$ as
induced subgraphs of $G$.

We observe this is almost tight as a function of $q$ since even for the non-
induced case one has that the $q$ size ramsey number of a path on $n$ vertices
is at least $cq^{2}n$, for some absolute $c>0$.

##  2\. Concluding remarks

We have developed an algorithmic approach to embed bounded degree trees in
sparse expanding graphs, generalising the remarkable result of Friedman and
Pippenger [32]. We have applied this result to give the state of the art on
the bounds for multiple questions. We will now discuss some further avenues of
research and state some open problems.

###  2.1. Tightening Theorem 1.3

There are three main places where one could tighten Theorem 1.3, each of which
would yield slight but growing (as a function of $\Delta$ or $d$) improvements
in our applications. Firstly, one could try remove the maximum degree
condition. We use this exclusively when applying the LLL in Lemma 2.13.
Secondly, one could try to remove the factor of $\Delta$ in the order of the
sets upon which we place our density constraint. Morally, this factor comes
from reserving $\Delta$ neighbours for critical vertices even though some
critical vertices may never actually be extended from. Finally, one could try
to replace the average degree upper bound of $12/5$ by some larger constant.
This upper bound is used in three places. It is used to bound the degeneracy
in Lemma 2.13, but there is a lot of slack in this application. That is, one
merely requires that $\Delta$ is much smaller than $d/C^{2}$, where $d$ is the
minimum of the graph given to Lemma 2.13 (we think the factor of $C^{2}$ is
roughly tight here). It is also used within Lemma 2.13 when we bound the
Lipschitz constant, but this could be avoided by simply requiring girth at
least $5$. The place where it is really required is when it used to show that
criticality cascades eventually stop (Lemma 2.9). In the case of Theorem 1.3
there may be an interesting dependency between the average degree upper bound
and the order of the sets that must satisfy it. We find this latter problem
particularly intriguing. For example, in a more concrete way we could not
answer the following nice question.

######  Problem 2.1.

Let $d_{1},d_{2}$ be positive integers. Is there $f(d_{1},d_{2})\geq 1$ and
$\varepsilon(d_{1},d_{2})>0$ such that the following holds. Let $G$ be a graph
with average degree $f(d_{1},d_{2})$ such that all subset of size at most $n$
have average degree at most $d_{2}$. Is there an induced subgraph
$G^{\prime}\subset G$ of average degree at least $d_{1}$ such that all subsets
$S\subset V(G^{\prime})$ of size at most $\varepsilon(d_{1},d_{2})n$ in
$G^{\prime}$ span at most $3/2|S|$ edges?

Finally, we mention a related problem. Theorem 2.18 in its current form is
almost tight. However, if we impose girth at least $5$ then can we apply it to
graphs with $h(G)>d-f(d)$ for any function $f$ that tends to infinity with
$d$? We see no reason why $f$ could not be taken a polynomial.

###  2.2. Rolling backwards

In [21], Friedman-Pippenger result was cleverly combined with a “rolling-back”
technique which allowed them to find different structures in expanding graphs.
It is natural to ask whether our method also allows for roll-backs and indeed,
it does. The key points are that in the proof of the main result we induct on
properties of $T_{i}$, $C_{i}$ and $B_{i}$, while $C_{i}$ can be viewed as a
monotone function of $T_{i}$. When rolling back, one deletes some vertices of
the current embedded tree $T_{i}$ to obtain $T^{\prime}$ and only keep the
directed edges of $B_{i}$ that start from the new $C_{i}$ which is in turn a
function of $T^{\prime}$. The desired properties are maintained. One can even
delete non-leaf vertices when rolling back although the bound on the order of
the critical bootstrap percolation will be worse (larger) than the factor of
$2$ in Lemma 2.8 (which uses that $G[X]$ is connected).

###  2.3. Induced ramsey and induced size ramsey

Recently, Draganić and Keevash [42] gave a bound on the induced size ramsey
number of paths, $\hat{r}_{\text{ind}}^{q}(P_{n})=O(nq^{3}\log^{2}(q))$.
Theorem 1.7 gives an improvement on this by essentially a factor of $q$. We
believe however the size ramsey and induced size ramsey of bounded degree
trees should not behave very differently as a function of the number of
colours.

######  Conjecture 2.2.

Let $\Delta\geq 1$ and $T$ be a tree on $n$ vertices with
$\Delta(T)\leq\Delta$. Then, for every $q\geq 1$,

$\hat{r}_{\text{ind}}^{q}(T)=O_{\Delta}(\hat{r}^{q}(T)).$

We reiterate a central problem in the area regarding the induced ramsey number
of bounded degree graphs. The best upper bound on the induced ramsey number
for graphs of bounded degree is $n^{O(\Delta)}$ proved by Conlon, Fox and Zhao
[14]. It is therefore remarkable that the possibility of induced ramsey
numbers of bounded degree graphs being linear remains open.

######  Problem 2.3.

Is there $\Delta\geq 1$, such that for every $C>0$, there is a graph $G$ on
$n$ vertices and $\Delta(G)\leq\Delta$ with $r_{\text{ind}}(G)>Cn$?

###  2.4. Induced structures in random graphs

We are confident our main result will be very useful in finding other large
induced structures in random graphs. For example, one could ask what is the
largest $k$ for which $G(n,p)$ contains an induced subdivision of a $K_{k}$
whp? This would be a induced version of a classical result of Ajtai, Kómlos
and Szemerédi [3] which guarantees that whp $G(n,p)$ where
$p=o(\frac{1}{{\sqrt{n}}})$ contains a subdivison of $K_{(1+o(1))\Delta}$
where $\Delta$ is the maximum degree of $G(n,p)$. Finally, we think our
methods could be helpful in proving essentially tight bounds for the size of
induced bounded degree trees in $G(n,p)$.

######  Conjecture 2.4.

For every $\Delta\geq 1$ there is $C_{\Delta}>0$ such that the following
holds. For all $\frac{C_{\Delta}}{n}\leq p\leq 0.1$, $G(n,p)$ contains w.h.p.
all trees of order
$\Omega\mathopen{}\mathclose{{}\left(\frac{\log(pn)}{p}}\right)$ with maximum
degree $\Delta$.

We do not even know the above result for any bounded degree tree (including a
path).

## References

  * ABNC+ [96] Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, and Madhu Sudan.  Efficient routing in optical networks.  Journal of the ACM (JACM), 43(6):973–1001, 1996.
  * ADK [17] Stephen Alstrup, Søren Dahlgaard, and Mathias Knudsen.  Optimal induced universal graphs and adjacency labeling for trees.  Journal of the ACM (JACM), 64(4):1–22, 2017.
  * AKS [79] Miklós Ajtai, János Komlós, and Endre Szemerd́i.  Topological complete subgraphs in random graphs.  Studia Scientiarum Mathematicarum Hungarica, 14:293–297, 1979.
  * AKS [07] Noga Alon, Michael Krivelevich, and Benny Sudakov.  Embedding nearly-spanning bounded degree trees.  Combinatorica, 27(6):629–644, 2007.
  * BDS [23] Domagoj Bradač, Nemanja Draganić, and Benny Sudakov.  Effective bounds for induced size-Ramsey numbers of cycles.  arXiv preprint arXiv:2301.10160, 2023.
  * Bec [83] József Beck.  On size ramsey number of paths, trees, and circuits. i.  Journal of Graph Theory, 7(1):115–129, 1983.
  * Bec [90] József Beck.  On size Ramsey number of paths, trees and circuits. ii.  Mathematics of Ramsey theory, pages 34–45, 1990.
  * BKM+ [21] Sören Berger, Yoshiharu Kohayakawa, Giulia Satiko Maesaka, Taísa Martins, Walner Mendonça, Guilherme Oliveira Mota, and Olaf Parczyk.  The size-Ramsey number of powers of bounded degree trees.  Journal of the London Mathematical Society, 103(4):1314–1332, 2021\.
  * BS [97] Itai Benjamini and Oded Schramm.  Every graph with a positive cheeger constant contains a tree with a positive cheeger constant.  Geometric & Functional Analysis GAFA, 7(3):403–419, 1997.
  * But [09] Steve Butler.  Induced-universal graphs for graphs with bounded maximum degree.  Graphs and Combinatorics, 25(4):461, 2009.
  * CDKS [21] Oliver Cooley, Nemanja Draganić, Mihyun Kang, and Benny Sudakov.  Large induced matchings in random graphs.  SIAM Journal on Discrete Mathematics, 35(1):267–280, 2021.
  * CFS [12] David Conlon, Jacob Fox, and Benny Sudakov.  On two problems in graph Ramsey theory.  Combinatorica, 32:513–535, 2012.
  * CFS [15] David Conlon, Jacob Fox, and Benny Sudakov.  Recent developments in graph Ramsey theory.  Surveys in combinatorics, 424(2015):49–118, 2015.
  * CFZ [14] David Conlon, Jacob Fox, and Yufei Zhao.  Extremal results in sparse pseudorandom graphs.  Advances in Mathematics, 256:206–290, 2014.
  * CG [83] Fan Chung and Ronald Graham.  On universal graphs for spanning trees.  Journal of the London Mathematical Society, 2(2):203–211, 1983\.
  * COE [15] Amin Coja-Oghlan and Charilaos Efthymiou.  On independent sets in random graphs.  Random Structures & Algorithms, 47(3):436–486, 2015.
  * CRST [83] Václav Chvatál, Vojtech Rödl, Endre Szemerédi, and William Trotter.  The Ramsey number of a graph with bounded maximum degree.  Journal of Combinatorial Theory, Series B, 34(3):239–243, 1983\.
  * DGK [22] Nemanja Draganić, Stefan Glock, and Michael Krivelevich.  Short proofs for long induced paths.  Combinatorics, Probability and Computing, 31(5):870–878, 2022.
  * Dir [52] Gabriel Andrew Dirac.  Some theorems on abstract graphs.  Proceedings of the London Mathematical Society, 3(1):69–81, 1952\.
  * DJK [08] Domingos Dellamonica Jr and Yoshiharu Kohayakawa.  An algorithmic friedman–pippenger theorem on tree embeddings and applications.  The Electronic Journal of Combinatorics, 2008.
  * DKN [22] Nemanja Draganić, Michael Krivelevich, and Rajko Nenadov.  Rolling backwards can move you forward: on embedding problems in sparse expanders.  Transactions of the American Mathematical Society, 375(7):5195–5216, 2022.
  * dlV [86] Wanceslas Fernandez de la Vega.  Induced trees in sparse random graphs.  Graphs and Combinatorics, 2:227–231, 1986.
  * DMC+ [24] Nemanja Draganić, Richard Montgomery, David Munhá Correia, Alexey Pokrovskiy, and Benny Sudakov.  Hamiltonicity of expanders: optimal bounds and application.  ArXiv:2402.06603, 2024.
  * Dra [20] Nemanja Draganić.  Large induced trees in dense random graphs.  ArXiv:2004.02800, 2020.
  * EFRS [78] Paul Erdős, Ralph Faudree, Cecil Rousseau, and Richard Schelp.  The size Ramsey number.  Periodica Mathematica Hungarica, 9(1-2):145–161, 1978.
  * EP [83] Paul Erdős and Zbigniew Palka.  Trees in random graphs.  Discrete Mathematics, 46(2), 1983.
  * ER [60] Paul Erdős and Alfréd Rényi.  On the evolution of random graphs.  Publications Mathematical Institute Hungarian Academiy Sciences, 5:17–61, 1960.
  * Erd [81] Paul Erdős.  On the combinatorial problems which i would most like to see solved.  Combinatorica, 1(1):25–42, 1981.
  * FFP [88] Paul Feldman, Joel Friedman, and Nicholas Pippenger.  Wide-sense nonblocking networks.  SIAM Journal on Discrete Mathematics, 1(2):158–173, 1988.
  * [30] Alan Frieze and Bill Jackson.  Large holes in sparse random graphs.  Combinatorica, 7:265–274, 1987.
  * [31] Alan Frieze and Bill Jackson.  Large induced trees in sparse random graphs.  Journal of Combinatorial Theory, Series B, 42(2):181–195, 1987\.
  * FP [87] Joel Friedman and Nicholas Pippenger.  Expanding graphs contain all small trees.  Combinatorica, 7:71–76, 1987.
  * Fri [90] Alan Frieze.  On the independence number of random graphs.  Discrete Mathematics, 81(2):171–175, 1990.
  * FS [08] Jacob Fox and Benny Sudakov.  Induced Ramsey-type theorems.  Advances in Mathematics, 219(6):1771–1800, 2008.
  * [35] Roman Glebov, D Johannsen, and Michael Krivelevich.  Hitting time appearance of certain spanning trees in the random graph process.  manuscript in preparation.
  * GM [75] Geoffrey Grimmett and Colin McDiarmid.  On colouring random graphs.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 77, pages 313–324. Cambridge University Press, 1975.
  * GRR [00] Ronald Graham, Vojtech Rödl, and Andrzej Ruciński.  On graphs with linear Ramsey numbers.  Journal of Graph Theory, 35(3):176–192, 2000.
  * Hax [01] Penny Haxell.  Tree embeddings.  Journal of Graph Theory, 36(3):121–130, 2001.
  * HK [95] Penny Haxell and Yoshiharu Kohayakawa.  The size-Ramsey number of trees.  Israel Journal of Mathematics, 89:261–274, 1995.
  * HKŁ [95] Penny Haxell, Yoshiharu Kohayakawa, and Tomasz Łuczak.  The induced size-Ramsey number of cycles.  Combinatorics, Probability and Computing, 4(3):217–239, 1995.
  * [41] Zach Hunter and Benny Sudakov.  Induced ramsey problems for trees and graphs with bounded treewidth.  Manuscript in preparation.
  * KD [24] Peter Keevash and Nemanja Draganić.  Long induced paths in expanders.  ArXiv:2402.02256v1, 2024.
  * KLWY [21] Nina Kamčev, Anita Liebenau, David Wood, and Liana Yepremyan.  The size Ramsey number of graphs with bounded treewidth.  SIAM Journal on Discrete Mathematics, 35(1):281–293, 2021.
  * KR [87] Luděk Kučera and Vojtěch Rödl.  Large trees in random graphs.  Commentationes Mathematicae Universitatis Carolinae, 28(1):7–14, 1987.
  * KRSS [11] Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht, and Endre Szemerédi.  Sparse partition universal graphs for graphs of bounded degree.  Advances in Mathematics, 226(6):5041–5065, 2011.
  * Lee [17] Choongbum Lee.  Ramsey numbers of degenerate graphs.  Annals of Mathematics, 185(3):791–829, 2017.
  * ŁP [88] Tomasz Łuczak and Zbigniew Palka.  Maximal induced trees in sparse random graphs.  In Annals of Discrete Mathematics, volume 38, pages 257–265. Elsevier, 1988.
  * LPY [21] Shoham Letzter, Alexey Pokrovskiy, and Liana Yepremyan.  Size-ramsey numbers of powers of hypergraph trees and long subdivisions.  ArXiv:2103.01942, 2021.
  * Łuc [91] Tomasz Łuczak.  Cycles in a random graph near the critical point.  Random Structures & Algorithms, 2(4):421–439, 1991.
  * Mon [19] Richard Montgomery.  Spanning trees in random graphs.  Advances in Mathematics, 356:106793, 2019.
  * Moo [65] John Moon.  On minimal $n$-universal graphs.  Glasgow Mathematical Journal, 7(1):32–33, 1965.
  * Pós [76] Lajos Pósa.  Hamiltonian circuits in random graphs.  Discrete Mathematics, 14(4):359–364, 1976.
  * Ram [28] Frank Ramsey.  On a problem of formal logic.  Proceedings of London Mathematical Society, 48:122–160, 1928.
  * RS [00] Vojtěch Rödl and Endre Szemerédi.  On size Ramsey numbers of graphs with bounded degree.  Combinatorica, 20(2):257–262, 2000.
  * Ruc [87] Andrzej Ruciński.  Induced subgraphs in a random graph.  In North-Holland Mathematics Studies, volume 144, pages 275–296. Elsevier, 1987.
  * Sue [92] Stephen Suen.  On large induced trees and long induced paths in sparse random graphs.  Journal of Combinatorial Theory, Series B, 56(2):250–262, 1992\.
  * Tik [22] Konstantin Tikhomirov.  On bounded degree graphs with large size-Ramsey numbers.  arXiv preprint arXiv:2210.05818, 2022.