heightadjust=object, valign=c

#  Size-Ramsey numbers of structurally sparse graphs

Nemanja Draganić  Department of Mathematics, ETH, Zürich, Switzerland.
Research supported in part by SNSF grant 200021_196965.
_Emails_<EMAIL_ADDRESS> Marc
Kaufmann Institute of Theoretical Computer Science, Department of Computer
Science, ETH, Zürich, Switzerland. M.K. was supported by SNSF grant
200021_192079. K.P. was supported by grant no. CRSII5 173721 of the Swiss
National Science Foundation. R.S. was supported by an ETH Zürich Postdoctoral
Fellowship.
_Emails_<EMAIL_ADDRESS>David Munhá Correia11footnotemark: 1 Kalina Petrova22footnotemark: 2 Raphael
Steiner22footnotemark: 2

###### Abstract

Size-Ramsey numbers are a central notion in combinatorics and have been widely
studied since their introduction by Erdős, Faudree, Rousseau and Schelp in
1978. Research has mainly focused on the size-Ramsey numbers of $n$-vertex
graphs with constant maximum degree $\Delta$. For example, graphs which also
have constant treewidth are known to have linear size-Ramsey numbers. On the
other extreme, the canonical examples of graphs of unbounded treewidth are the
grid graphs, for which the best known bound has only very recently been
improved from $O(n^{3/2})$ to $O(n^{5/4})$ by Conlon, Nenadov and Trujić. In
this paper, we study a common generalization of these problems and establish
new bounds on the size-Ramsey numbers in terms of treewidth (which may grow as
a function of $n$). As a special case, this yields a bound of
$\tilde{O}(n^{3/2-1/2\Delta})$ for proper minor-closed classes of graphs. In
particular, this bound applies to planar graphs, addressing a question of
Kamcev, Liebenau, Wood and Yepremyan. Our proof combines methods from
structural graph theory and classic Ramsey-theoretic embedding techniques,
taking advantage of the product structure exhibited by graphs with bounded
treewidth.

##  1 Introduction

The famous theorem of Ramsey states that for every positive integer $n$, there
exists a finite number $N$ such that every complete graph on $N$ vertices
whose edges are colored in red or in blue contains a monochromatic clique of
order $n$ [26]. Motivated by this, we say that a _host_ graph $G$ is
$k$-Ramsey for a graph $H$ if any $k$-coloring of the edges of $G$ yields a
monochromatic copy of $H$, and we write $G\xrightarrow{k}H$.

Given a graph $H$, its size-Ramsey number $\hat{r}^{k}(H)$ is defined as the
smallest number of edges in a graph $G$ such that $G\xrightarrow{k}H$. This
notion measures the minimality of the host graph $G$ in a precise manner, and
was introduced in 1978 by Erdős, Faudree, Rousseau and Schelp [16]. Since
then, it has been extensively studied and in particular in recent years it has
gained a lot of attention.

Intuitively, sparse graphs are a good candidate for having low size-Ramsey
number, but already double stars — trees containing only two non-leaf
vertices, each of degree linear in the size of the graph — have quadratic
size-Ramsey number [16]. Thus, a natural class of graphs to study in this
context is the class of bounded-degree graphs. Among the first instances of
this was the result of Beck [3] who proved that for paths it holds that
$\hat{r}(P_{n})\leq 900n$, answering a $\$100$-dollar question of Erdős.
Furthermore, Friedman and Pippenger [17] proved that bounded-degree trees have
linear size-Ramsey numbers (i.e., bounded from above by a constant times their
order). More recently, it has been shown that graphs with bounded degree and
bounded treewidth exhibit the same behaviour [21, 4], as well as _long_
subdivisions of bounded-degree graphs [13].

Perhaps surprisingly, not all bounded-degree graphs have this behaviour. In
fact, there exist graphs with maximum degree three which serve as
counterexamples, as shown by Rödl and Szemerédi [28]. More concretely, they
constructed cubic graphs $H$ on $n$ vertices fulfilling $\hat{r}(H)\geq c\cdot
n\cdot\log^{\frac{1}{60}}(n)$ for a universal constant $c>0$. Their lower
bound has been improved very recently to $\hat{r}(H)\geq c\cdot n\cdot
e^{c\sqrt{\log(n)}}$ by Tikhomirov [29], modifying their construction by a
clever randomization trick. In spite of these advances, the conjecture of Rödl
and Szemerédi that there exist bounded-degree $n$-vertex graphs $H$ with
$\hat{r}(H)\geq n^{1+\varepsilon}$ for some absolute constant $\varepsilon>0$
remains open.

Turning to general upper bounds, Kohayakawa, Schacht, Rödl and Szemerédi [23]
showed that for graphs $H$ which have maximum degree $\Delta$ it holds that
$\hat{r}(H)=O(n^{2-1/\Delta}\log^{1/\Delta}n)$, leaving a wide gap between the
best known upper and lower bounds. Recently, Allen and Böttcher [1] announced
an improvement of this bound to $\hat{r}(H)=O(n^{2-1/(\Delta-1)+o(1)})$ for
$\Delta\geq 4$. For the case $\Delta=3$, the first and fourth authors [14]
showed that $\hat{r}(H)=O(n^{3/2+o(1)})$. As mentioned above, the class of
bounded-degree graphs with constant treewidth is far better understood, and in
fact it is known that the size-Ramsey numbers of these graphs are linear in
$n$ [4, 21]. Unfortunately, the proofs in both [4] and [21] do not generalize
beyond the setting of constant treewidth. In particular, if one allows the
treewidth of the considered graphs $H$ to grow with $n$, then thus far no
better upper bounds on $\hat{r}(H)$ than the bound of Kohayakawa et al. (which
only takes into account degree bounds, and not the structure of the graphs)
were known [23] . In this paper, we generalize the above-mentioned results to
graph classes of unbounded treewidth. In particular, leveraging the treewidth
gives a substantial improvement over the bound of Kohayakawa et al.

######  Theorem 1.1.

Let $k\in\mathbb{N}$ and let $H$ be an $n$-vertex graph of constant maximum
degree $\Delta$ and treewidth $t=t(n)$. Then

  * •

$\hat{r}_{k}(H)=O(nt\log n)$

  * •

Furthermore, if $t=\Omega(e^{\sqrt{\log n}})$ then we have111We use
$\tilde{O}(f(n))$ to denote all functions which are in $O(f(n)(\log n)^{C})$
for some absolute constant $C>0$. $\hat{r}_{k}(H)=\tilde{O}(nt^{1-1/\Delta})$.

Treewidth is a key parameter in structural graph theory and has served as the
watershed in Robertson and Seymour’s seminal sequence of papers on graph
minors, culminating in what is now known as the Graph Minor Theorem. Tree
decompositions, which are inherently related to treewidth, have enabled
advances in algorithmic graph theory, with many NP-hard problems proving
solvable in polynomial time for entire graph classes whose treewidth is known
to be bounded.

In fact, Theorem 1.1 is a special case of more general results, namely Lemma
3.5 and Lemma 3.6, which we prove in Section 3. Indeed, there we show that any
bounded-degree graph contained in a product of a bounded-degree tree and a
clique of certain size has small size-Ramsey number. Since (as we will prove
in Section 2) graphs of bounded degree and treewidth $t$ are contained in such
a product with certain parameters, Theorem 1.1 will follow.

As the treewidth of many graph classes is well understood, Theorem 1.1 may
provide good upper bounds for the size-Ramsey numbers of graphs in those
classes. One such example are proper minor-closed classes of graphs, for which
it is known [2, 15] that they have treewidth at most $O(\sqrt{n})$, and hence
we have the following consequence of Theorem 1.1.

######  Theorem 1.2.

Let $k\in\mathbb{N}$ and let $\mathcal{G}$ be a proper minor-closed class.
Then for every $n$-vertex graph $G\in\mathcal{G}$ of maximum degree $\Delta$,
we have

$\hat{r}_{k}(G)=\tilde{O}(n^{3/2-\frac{1}{2\Delta}}).$

A natural and well studied class of minor-closed graphs are planar graphs, and
hence the bound above also applies to them. This addresses a question raised
by Kamčev, Liebenau, Wood and Yepremyan [21], who asked for general bounds for
bounded-degree planar graphs. Until recently, the best known bound for the
two-dimensional grid graph on $n$-vertices was $O(n^{3/2})$, which was
improved to $O(n^{5/4})$ by Conlon, Nenadov and Trujić [8]. The only other
bounded-degree planar graphs which were studied are cycles and bounded-degree
trees, which have linear size-Ramsey numbers.

Let us also remark that all our results are of universality type. Namely, in
our proofs we construct a host graph such that we can find all the graphs in
the relevant class within the same color class. Results of this type were also
obtained for size-Ramsey numbers of graphs in other classes [17, 12, 13, 22,
23, 25].

Organization. In Section 2 we prove several results which embed a graph with a
given bound on its treewidth into the product of a bounded-degree tree and a
clique. The results in this section might be of independent interest. In
Section 3 we prove bounds on the size-Ramsey numbers of bounded-degree
subgraphs of products of bounded-degree trees and cliques, which, combined
with the results from Section 2 then allow us to prove our main results. We
decided to defer some of the technical details of the proofs from Section 3 to
the appendix (Section A) to ease the readability and intuitive understanding
of our proofs.

Notation. For simplicity, we employ the following conventions. We omit
rounding of real numbers to nearest integers whenever it is not of vital
importance. For two constants $a,b$, we use $a\ll b$ to indicate that $b$ is
sufficiently large as a function of $a$ for our proofs to work out. For
example, we often use inequality chains like $a\gg b\gg c\gg d$, which also
implies that in particular $a\gg bcd$. We make use of the _strong product_
operator, which is defined as follows. The strong product $G\boxtimes H$ of
graphs $G$ and $H$ is the graph with vertex set $V(G)\times V(H)$ such that
for $v_{1},v_{2}\in V(G)$ and $u_{1},u_{2}\in V(H)$, we have that
$(v_{1},u_{1})$ is adjacent to $(v_{2},u_{2})$ in $G\boxtimes H$ if
$v_{1}=v_{2}$ and $\\{u_{1},u_{2}\\}\in E(H)$, or $\\{v_{1},v_{2}\\}\in E(G)$
and $u_{1}=u_{2}$, or $\\{v_{1},v_{2}\\}\in E(G)$ and $\\{u_{1},u_{2}\\}\in
E(H)$.

##  2 Structural results

In this section, we prove the announced structural lemma for graphs of bounded
treewidth. It says that every bounded-degree $n$-vertex graph $G$ of treewidth
at most $t$ can be embedded as a subgraph into the strong product of a
bounded-degree tree of size $O(n/(t\log n))$ and a clique of size $O(t\log
n)$. In the case that $G$ belongs to a structurally sparse class of graphs,
such as planar graphs or a proper minor-closed class, we can get rid of the
$\log n$ factor in the above estimate, which can be used to further improve
Theorem 1.2 by removing additional hidden logarithmic factors. Evidently, the
significance of this result does not lie in this minor improvement, but rather
in the fact that it is tight (consider, say, the grid graph).

######  Lemma 2.1.

Let $\Delta>0$. There exists $d>0$ depending solely on $\Delta$ such that the
following hold.

  1. (i)

For every $n$-vertex graph $G$ of maximum degree at most $\Delta$ and
treewidth at most $t$ there exists a tree $T$ such that $G\subseteq T\boxtimes
K_{s}$, where $n\geq s=\Theta_{\Delta}(t\log n)$,
$v(T)=O_{\Delta}\big{(}\frac{n}{s}\big{)}$ and $\Delta(T)\leq d$.

  2. (ii)

Let $\mathcal{G}$ be a class of graphs closed under taking subgraphs, and let
$t:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ be an increasing function in
$\Omega(\log x)$ such that every $n$-vertex graph $G\in\mathcal{G}$ has
treewidth at most $t(n)$. Suppose further that there exists a constant
$\alpha>0$ such that $t(\lambda x)\leq\lambda^{\alpha}t(x)$ holds for every
$\lambda,x>0$. Then for every $n$-vertex graph $G\in\mathcal{G}$ of maximum
degree at most $\Delta$ there is a tree $T$ such that $G\subseteq T\boxtimes
K_{s}$, where $n\geq s=\Theta_{\Delta,\alpha}(t(n))$,
$v(T)=O_{\Delta}\big{(}\frac{n}{s}\big{)}$ and $\Delta(T)\leq d$.

We remark that a very similar embedding lemma, without the $\log n$ factor,
has been proved before by Ding and Oporowski [10] and later on improved by
Wood [30]. These results state that every graph $G$ of maximum-degree $\Delta$
and treewidth at most $t$ is contained in $T\boxtimes K_{s}$, where $T$ is
some tree and $s=O(\Delta t)$. However, for our purposes, it is very important
to be able to carefully control both the size and the maximum degree of the
tree $T$. In particular, we need $T$ to have constant degree, and this is not
the case in the results in [10, 30]. Motivated by Lemma 2.1, very recently
Distel and Wood [11] showed a strengthening of it by removing the logarithmic
factor in the first part of Lemma 2.1.

Before moving on to the proof of Lemma 2.1, let us note the following
immediate consequence of it.

######  Corollary 2.2.

Let $\Delta>0$ and let $\mathcal{G}$ be a proper minor-closed class. There
exist constants $c,d>0$ such that every $n$-vertex graph $G\in\mathcal{G}$ of
maximum degree at most $\Delta$ is a subgraph of $T\boxtimes K_{s}$, where
$s\leq c\sqrt{n}$ and $T$ is a tree with $v(T)\leq c\sqrt{n}$ and
$\Delta(T)\leq d$.

  * Proof.

It is well-known [2, 15] that for every proper minor-closed class
$\mathcal{G}$ of graphs, there is a constant $C>0$ such that every $n$-vertex
graph $G\in\mathcal{G}$ has treewidth at most $C\sqrt{n}$. The statement
therefore immediately follows from Lemma 2.1 (ii) by setting $t(x)=C\sqrt{x}$
and $\alpha=\frac{1}{2}$. ∎

We now move on to the proof of Lemma 2.1, which follows closely the arguments
in [6, 5]. A crucial tool to embed a given graph $G$ of treewidth $t$ into the
strong product of a tree and a clique is a repeated application of the
following well-known result from structural graph theory concerning the
existence of so-called _balanced separators_ in graphs of bounded treewidth.

######  Lemma 2.3 (Robertson and Seymour, cf. statement (2.6) in [27]).

Let $G$ be a graph of treewidth at most $t$ and order $n$. Then there exists a
set $S\subseteq V(G)$ of size $|S|\leq t+1$ and a partition of $V(G)\setminus
S$ into sets $A$ and $B$ such that no edge in $G-S$ connects a vertex in $A$
to a vertex in $B$ and such that $|A|,|B|\leq\frac{2}{3}n$.

To prove Lemma 2.1, we first establish an extension of Lemma 2.3 which works
when the graph $G$ comes with a given coloring of its vertices with $k$
colors, and we wish to find a small separator $S$ in the graph such that the
two sides $A$ and $B$ separated by it contain each at most half the vertices
in each color. To find such separators, we make use of the celebrated
necklace-splitting theorem due to Goldberg and West in the following form.

######  Theorem 2.4 (Goldberg and West [20]).

For some $R\subseteq\\{1,\ldots,n\\}$, let $c:R\rightarrow\\{1,\ldots,k\\}$ be
a (partial) $k$-coloring of the first $n$ integers. Then $\\{1,\ldots,n\\}$
can be partitioned into $k+1$ pairwise disjoint intervals
$I_{1},\ldots,I_{k+1}$ such that for some $0\leq r\leq k+1$ it holds that
(denoting $X:=\bigcup_{i=1}^{r}{I_{i}},Y:=\bigcup_{i=r+1}^{k+1}{I_{i}}$)

$\max\\{|X\cap c^{-1}(i)|,|Y\cap
c^{-1}(i)|\\}\leq\left\lceil\frac{|c^{-1}(i)|}{2}\right\rceil$

for $i=1,\ldots,k$.

######  Lemma 2.5.

Let $G$ be a graph and let $t:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ be an
increasing function such that every subgraph of $G$ with $x$ vertices has
treewidth at most $t(x)$.

Then there exists a linear ordering $v_{1},\ldots,v_{n}$ of the vertices in
$G$ and for each $i\in\\{1,\ldots,n\\}$ a set $S(v_{i})\subseteq V(G)$
including $v_{i}$ such that

$|S(v_{i})|\leq\sum_{j=0}^{\lceil\log_{3/2}(n)\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{j}n\right)+1\right)}$

and such that there are no edges between $\\{v_{1},\ldots,v_{i-1}\\}\setminus
S(v_{i})$ and $\\{v_{i+1},\ldots,v_{n}\\}\setminus S(v_{i})$ in $G$.

  * Proof.

We prove the statement by induction on $n$. The claim is trivially true for
$n=1$ by setting $S(v_{1}):=\\{v_{1}\\}$, so moving on suppose that $n\geq 2$
and the claim is true for all subgraphs of $G$ on fewer vertices. Apply Lemma
2.3 to find a set $S\subseteq V(G)$ of size at most $t(n)+1$ and a partition
of $V(G)\setminus S$ into parts $A$ and $B$ with no edges in $G$ between them,
such that $|A|,|B|\leq\frac{2}{3}n$. By the inductive assumption, there exist
linear orderings $v_{1},\ldots,v_{|A|}$ and $w_{1},\ldots,w_{|B|}$ of $A$ and
$B$ and for each $i\in\\{1,\ldots,|A|\\}$ and $j\in\\{1,\ldots,|B|\\}$ sets
$S_{A}(v_{i})$ and $S_{B}(w_{j})$ such that the following hold.
$S_{A}(v_{i})\ni v_{i}$ separates $\\{v_{k}|k<i\\}$ and $\\{v_{k}|k>i\\}$ in
$G[A]$, and $S_{B}(w_{j})\ni w_{j}$ separates $\\{w_{k}|k<j\\}$ and
$\\{w_{k}|k>j\\}$ in $G[B]$, and with $m:=\max\\{|A|,|B|\\}\leq\frac{2}{3}n$
we have

$|S_{A}(v_{i})|,|S_{B}(v_{j})|\leq\sum_{k=0}^{\lceil\log_{3/2}(m)\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{k}m\right)+1\right)}$
$\leq\sum_{k=1}^{\lceil\log_{3/2}(m)+1\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{k}n\right)+1\right)}\leq\sum_{k=1}^{\lceil\log_{3/2}(n)\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{k}n\right)+1\right)}.$

Let $s_{1},\ldots,s_{|S|}$ be an arbitrary linear ordering of $S$, and
consider the following linear order on $V(G)$:
$v_{1},\ldots,v_{|A|},s_{1},\ldots,s_{|S|},w_{1},\ldots,w_{|B|}$. Furthermore
let $S(v_{i}):=S_{A}(v_{i})\cup S$ for $i=1,\ldots,|A|$, $S(s_{k}):=S$ for
$k=1,\ldots,|S|$, and $S(w_{j}):=S_{B}(w_{j})\cup S$ for $j=1,\ldots,|B|$. It
is easily verified that each of these sets separates their predecessors and
successors in the ordering in $G$ and since $|S|\leq t(n)+1=t((2/3)^{0}n)+1$,
each of these sets is of size at most
$\sum_{h=0}^{\lceil\log_{3/2}(n)\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{h}n\right)+1\right)}$.
This concludes the proof. ∎

Using the previous statement and Lemma 2.4, we immediately arrive at the
following corollary.

######  Corollary 2.6.

Let $G$ be a graph given with a (partial) coloring
$c:R\rightarrow\\{1,\ldots,k\\}$ of its vertices for some $R\subseteq V(G)$
and let $t:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ be an increasing function
such that every subgraph of $G$ with $x$ vertices has treewidth at most
$t(x)$. Then there is a set $S\subseteq V(G)$ and a partition $A,B$ of
$V(G)\setminus S$ such that

$|S|\leq
k+k\sum_{i=0}^{\lceil\log_{3/2}(n)\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{i}n\right)+1\right)},$

there are no connections between $A$ and $B$ in $G$, and

$\max\\{|A\cap c^{-1}(i)|,|B\cap c^{-1}(i)|\\}\leq\frac{|c^{-1}(i)|}{2}$

for each $i\in\\{1,\ldots,k\\}$.

  * Proof.

We apply Lemma 2.5 to $G$ to get the linear ordering $v_{1},\ldots,v_{n}$ of
$V(G)$. Next, we apply Theorem 2.4 to the coloring $c(i):=c(v_{i})$. Let
$I_{1},\ldots,I_{r},I_{r+1},\ldots,I_{k},I_{k+1}$ be an interval partition of
$\\{1,\ldots,n\\}$ as guaranteed by the lemma. Let $x_{1},\ldots,x_{k}$ be a
list of $k$ elements in $\\{1,\ldots,n\\}$ such that any two distinct
intervals in $I_{1},I_{2},\ldots,I_{k+1}$ are separated by at least one of
them. We now define $S:=S(x_{1})\cup S(x_{2})\cup\cdots\cup S(x_{k})$, which
by Lemma 2.5 is of size at most
$k\sum_{i=0}^{\lceil\log_{3/2}(n)\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{i}n\right)+1\right)}$,
and let $A:=\\{v_{i}|i\in I_{1}\cup\cdots\cup I_{r}\\}\setminus
S,B:=\\{v_{i}|i\in I_{r+1}\cup\cdots\cup I_{k+1}\\}\setminus S$. It now
follows directly from Lemma 2.5 that there are no edges in $G$ connecting $A$
and $B$ and directly from the properties guaranteed by Theorem 2.4 that
$\max\\{|A\cap c^{-1}(i)|,|B\cap
c^{-1}(i)|\\}\leq\left\lceil\frac{|c^{-1}(i)|}{2}\right\rceil$ for each
$i\in\\{1,\ldots,k\\}$. In order to reduce from the above bound
$\left\lceil\frac{|c^{-1}(i)|}{2}\right\rceil$ to the desired
$\frac{|c^{-1}(i)|}{2}$ for each $i$, we may simply move for each color $i$ a
vertex of that color from either $A$ or $B$ into $S$, thereby increasing the
size of $S$ by at most $k$, and the statement follows. ∎

Using Corollary 2.6 repeatedly, we can now prove the following statement,
which directly implies Lemma 2.1.

######  Lemma 2.7.

Let $G$ be a graph of maximum degree at most $\Delta$ and let
$t:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$ be an increasing function such
that every $x$-vertex subgraph of $G$ has treewidth at most $t(x)$. Let

$k:=\lceil\log_{2}(\Delta)\rceil+2,\,s:=\left\lfloor
k+k\sum_{i=0}^{\lceil\log_{3/2}(n)\rceil}{\left(t\left(\left(\frac{2}{3}\right)^{i}n\right)+1\right)}\right\rfloor.$

Then there exists a binary tree $T$ and a partition $(X_{v})_{v\in V(T)}$ of
$V(G)$ such that $|X_{v}|=2s$ for every non-leaf $v\in V(T)$, $|X_{v}|\leq 2s$
for every leaf $v\in V(T)$, and such that any two adjacent vertices in $G$ are
contained in sets $X_{u},X_{v}$ for vertices $u,v\in V(T)$ at distance at most
$k$ in $T$.

  * Proof.

To enable induction, we prove a slight strengthening of the statement in the
lemma as follows:

#### Claim.

_Given any sequence $C_{1},\ldots,C_{k}$ of disjoint subsets of $V(G)$ such
that $|C_{i}|\leq 2^{i-1}\cdot s$ for each $i$, we can find a tree $T$ and a
partition $(X_{v})_{v\in V(T)}$ as in the lemma with the following additional
property: For each $i=1,\ldots,k$ and every vertex $v$ in $T$ at distance at
least $i$ from the root, we have $X_{v}\cap C_{i}=\varnothing$._

Let us now prove this claim by induction on $v(G)$. It trivially holds true if
$v(G)\leq 2s$, so suppose that $v(G)>2s$ and the claim is satisfied by every
subgraph of $G$ with fewer than $v(G)$ vertices. Interpret the disjoint sets
$C_{1},\ldots,C_{k}$ as the color classes of a partial coloring of $V(G)$, and
apply Corollary 2.6 to find a set $S$ of size at most $s$ in $G$ and a
partition $(A,B)$ of $V(G)\setminus S$ such that $|C_{i}\cap A|,|C_{i}\cap
B|\leq\frac{|C_{i}|}{2}\leq 2^{i-2}\cdot s$ for each $i$. Pick a set $X$ of
size exactly $2s$ in $V(G)$ such that $C_{1}\cup S\subseteq X$ (this is
possible since $|C_{1}|,|S|\leq s$ and $v(G)>2s$). Now, let
$A^{\prime}:=A\setminus X$, $B^{\prime}:=B\setminus X$. For each
$i=1,\ldots,k-1$, define $C_{i}^{A}:=C_{i+1}\cap A^{\prime}$,
$C_{i}^{B}:=C_{i+1}\cap B^{\prime}$. Further, let $C_{k}^{A}:=(N_{G}(X)\cap
A^{\prime})\setminus\bigcup_{i=1}^{k-1}{C_{i}^{A}}$ and
$C_{k}^{B}:=(N_{G}(X)\cap B^{\prime})\setminus\bigcup_{i=1}^{k-1}{C_{i}^{B}}$.
From the above we have $|C_{i}^{A}|,|C_{i}^{B}|\leq 2^{(i+1)-2}s=2^{i-1}s$ for
$i=1,\ldots,k-1$, as well as
$|C_{k}^{A}|,|C_{k}^{B}|\leq|N_{G}(X)|\leq\Delta\cdot 2s\leq 2^{k-1}s$ since
$G$ is of maximum degree at most $\Delta$ and by our choice of $k$.

Therefore, we can apply induction to $G[A^{\prime}]$ with the sets
$C_{1}^{A},\ldots,C_{k}^{A}$ and to $G[B^{\prime}]$ with the sets
$C_{1}^{B},\ldots,C_{k}^{B}$ to find binary trees $T_{A}$ and $T_{B}$, and
partitions $(X_{v})_{v\in V(T_{A})},(X_{v})_{v\in V(T_{B})}$ of $A^{\prime}$
and $B^{\prime}$ satisfying the inductive claim. We now form a binary tree $T$
by adding a new root vertex $r$ and connecting it to the roots of the binary
trees $T_{A}$ and $T_{B}$, and setting $X_{r}:=X$. We claim that this tree and
the partition satisfy the claim. Let us first verify the condition with
respect to the sets $C_{1},\ldots,C_{k}$. For $i=1$, and any vertex $v$ at
distance at least $1$ from $r$ in $T$, we have that $X_{v}$ is disjoint from
$X\supseteq C_{1}$. Further, for $i\in\\{2,\ldots,k\\}$, every vertex $v$ at
distance at least $i$ from $r$ in $T$ has distance at least $i-1$ from the
root in either $T_{A}$ or $T_{B}$, thus implying that $X_{v}$ is disjoint from
$C_{i-1}^{A}=C_{i}\cap A^{\prime}$ respectively $C_{i-1}^{B}=C_{i}\cap
B^{\prime}$, and therefore $X_{v}\cap C_{i}=\varnothing$ in each case.

Hence, all that remains to be verified is that any two adjacent vertices in
$G$ are contained in sets $X_{u},X_{v}$ for vertices $u,v$ at distance at most
$k$ in $T$. So consider any two vertices $u,v$ in $T$ such that there exists
an edge in $G$ with endpoints in $X_{u}$ and $X_{v}$. If $u,v\neq r$ then
either both of $u,v$ are contained in $T_{A}$ or both in $T_{B}$, and then it
follows from the validity of the inductive claim for $T_{A}$ and $T_{B}$ that
$u$ and $v$ are at distance at most $k$ in $T$. Next consider the case $u=r$,
and w.l.o.g. assume $v\in V(T_{A})$. Then $\varnothing\neq X_{v}\cap
N_{G}(X_{u})=X_{v}\cap N_{G}(X)=X_{v}\cap(N_{G}(X)\cap A^{\prime})$, so in
particular $X_{v}$ intersects $C_{k}^{A}$ or at least one of
$C_{1}^{A},\ldots,C_{k-1}^{A}$, let’s say $C_{i}^{A}\cap X_{v}\neq\varnothing$
for some $i\in\\{1,\ldots,k\\}$. But then by our inductive call to
$G[A^{\prime}]$, $v$ has to be at distance at most $i-1$ from the root in
$T_{A}$. But this means that $v$ is at distance at most $i$ from the root $r$
in $T$, showing that $u=r$ and $v$ are at distance at most $i\leq k$ also in
this last case. Thus, $G$ satisfies the inductive assertion with respect to
$C_{1},\ldots,C_{k}$, concluding the proof of the lemma. ∎

We are now ready to show Lemma 2.1.

  * Proof of Lemma 2.1.

We do the proof of both cases (i) and (ii) of the lemma at once. Every
subgraph of $G$ on $x$ vertices has treewidth at most $t(x)$, where we let
$t(x):=t$ for each $x$ if we are in case (i) of the lemma. Let $k$ and $s$ be
defined as in Lemma 2.7 and note that we obtain $s=\Theta_{\Delta}(t\log n)$
in case (i) and

$k(t(n)+1)<s\leq
k+k\sum_{i=0}^{\lceil\log_{3/2}(n)\rceil}{\left(\left(\frac{2}{3}\right)^{\alpha
i}t(n)+1\right)}$ $\leq
k+\frac{k}{1-(2/3)^{\alpha}}t(n)+k(\lceil\log_{3/2}(n)\rceil+1)=O_{\Delta,\alpha}(t(n))+O_{\Delta}(\log
n)=O_{\Delta,\alpha}(t(n)),$

hence $s=\Theta_{\Delta,\alpha}(t(n))$ in case (ii).

We can now apply Lemma 2.7 to find a binary tree $T$ and a partition
$(X_{v})_{v\in T}$ of the vertex set of $G$ such that $|X_{v}|=2s$ for every
non-leaf $v$ of $T$, $|X_{v}|\leq 2s$ for every leaf $v$ of $T$, and such that
whenever $X_{u}$ and $X_{v}$ have a connecting edge in $G$, then $u$ and $v$
are at distance at most $k=\lceil\log_{2}(\Delta)\rceil+2$ in $T$. Note that
the number of non-leaves in $T$ is at most $\frac{n}{2s}$, and since a binary
tree of size at least $3$ has at most one more leaf than non-leaf, we find
that $v(T)\leq\frac{n}{s}+1$. Furthermore, we can see from the above that $G$
is a subgraph of $T^{k}\boxtimes K_{2s}$, where $T^{k}$ is the graph on the
same vertex set as $T$ in which two vertices are adjacent iff they are at
distance at most $k$ from each other in $T$. Notice that since $T$ is a binary
tree, it is not hard to show that $T^{k}\subseteq T^{\prime}\boxtimes
K_{2^{k}}$ where $T^{\prime}$ is a tree such that $v(T^{\prime})\leq
v(T)\leq\frac{n}{s}+1$ and $\Delta(T^{\prime})\leq 1+2^{k}=:d$. All in all, we
find that $G\subseteq(T^{\prime}\boxtimes K_{2^{k}})\boxtimes K_{2s}\simeq
T^{\prime}\boxtimes K_{2^{k+1}s}$. Since $2^{k+1}s=\Theta_{\Delta}(s)$, the
assertion of the lemma in both cases now follows from the above asymptotic
estimates of $s$. ∎

##  3 Proof of main result

In this section we introduce some tools that we need, and give the proofs of
our main results. We start with the main result from [4], which states that
graphs with constant treewidth and constant degree have linear size-Ramsey
numbers, and moreover, that there exists a host graph for this class of graphs
which also has constant maximum degree.

######  Theorem 3.1 (Corollary 2 in [4]).

For any positive integers $k,\Delta,t$, and for every $n$ large enough, there
exists a graph $G$ with $O(n)$ vertices and constant maximum degree such that
for every $n$-vertex graph $H$ of maximum degree $\Delta$ and treewidth at
most $t$, it holds that $G\rightarrow_{k}H$.

The theorem above is stated in [4] without the maximum degree condition on
$G$, but the construction in [4] clearly satisfies it.

###  3.1 Regularity method

Similarly to previous work on size-Ramsey numbers, to find monochromatic
subgraphs in our host graph, we make use of the celebrated _sparse regularity
method_ (for a detailed exposition of which we refer the reader to [19]).
Instead of working with regular pairs as usual, it is enough for our purposes
to only have lower bounds on the density of subgraphs, as expressed in the
following definition.

######  Definition 3.2.

Let $\alpha,\varepsilon>0$ and $0<p\leq 1$. For a graph $G=(V,E)$ and disjoint
sets $X,Y\subseteq V$, we say that $(X,Y)$ is _$(\varepsilon,\alpha,p)$
-dense_ if for any $X^{\prime}\subseteq X,Y^{\prime}\subseteq Y$ with
$|X^{\prime}|\geq\varepsilon|X|$ and $|Y^{\prime}|\geq\varepsilon|Y|$, we have

$d_{G}(X^{\prime},Y^{\prime})\geq(\alpha-\varepsilon)p.$

To be able to apply the sparse regularity method, we need our host graph to
have somewhat ‘uniformly’ distributed edges, typically captured by the concept
of $(\lambda,p)$-uniformity as follows.

######  Definition 3.3.

A graph $G=(V,E)$ is $(\lambda,p)$-uniform if for all disjoint $U,W\subseteq
V$ with $|U|,|W|\geq\lambda|V|$, we have $(1-\lambda)p\leq
d_{G}(U,W)\leq(1+\lambda)p$. If $G$ is bipartite with bipartition $V=A\cup B$,
then we say that $G$ is $(\lambda,p)$-uniform if the same holds for all
$U\subseteq A$ and $W\subseteq B$ of size at least $\lambda|A|$ and
$\lambda|B|$ respectively.

The next lemma, which we will use in the proofs of Lemmas 3.5 and 3.6, allows
us to find certain useful structure in colored blow-ups of bounded-degree
graphs. Namely, it turns out one can choose a small fraction of the vertices
in each part of the blow-up in such a way that the bipartite graph between
each pair of these subparts has at least one color with the lower-regularity
properties captured by Definition 3.2 and some minimum density.

######  Lemma 3.4 (Lemma 2.3 in [8]).

For every $k,\Delta\geq 2$ and $\varepsilon>0$, there exists $\lambda>0$ such
that the following holds for every $p\in(0,1]$. Let $H$ be a graph on at least
two vertices with $\Delta(H)\leq\Delta$ and let $\Gamma$ be obtained by
replacing every $x\in V(H)$ with an independent set $V_{x}$ of sufficiently
large order $n$ and every $xy\in E(H)$ by a $(\lambda,p)$-uniform bipartite
graph between $V_{x}$ and $V_{y}$. Then, for every $k$-colouring of the edges
of $\Gamma$, there exists a $k$-colouring $\phi$ of the edges of $H$ and, for
every $x\in V(H)$, a subset $U_{x}\subseteq V_{x}$ of order $|U_{x}|=\lambda
n$ such that $(U_{x},U_{y};E_{\phi(xy)})$ is
$(\varepsilon,\frac{1}{2k},p)$-dense for each $xy\in H$ where
$E_{\phi(xy)}\subseteq E_{\Gamma}$ stands for the edges of colour $\phi(xy)$
between $U_{x}$ and $U_{y}$ in $\Gamma$.

###  3.2 Key lemmas and proof of Theorem 1.1

As announced in the introduction, here we prove Theorem 1.1. To do so, we will
show the following two stronger lemmas, each of which implies one of the two
statements in Theorem 1.1. Both of them give bounds on the size-Ramsey number
of bounded-degree graphs which are contained in a product of a bounded-degree
tree and a clique of certain size. We first state the two lemmas, and show how
Theorem 1.1 is implied. In the next subsection, we give a proof of the first
lemma, which relies on the proof of the classic lemma for embedding graphs
into regular partitions. We are succinct with the details, as the embedding
lemma is by now a standard tool (for an in-depth survey of it and other
foundational regularity tools, see [24]), and only minor modifications are
necessary for our application.

After that, we give a proof of the second lemma, which relies on the ideas
used for the first result, and on the embedding machinery developed in [23],
with several changes needed to adapt their method to our setting. We present
those changes in the appendix.

######  Lemma 3.5.

Let $\Delta,d,k$ be positive integers and let $H$ be an $n$-vertex graph with
$\Delta(H)\leq\Delta$, such that $H\subset T\boxtimes K_{s}$ for some $s=s(n)$
and a tree $T$ with $\Delta(T)\leq d$ and $v(T)=\tau=\tau(n)$. Then
$\hat{r}_{k}(H)=O(\tau s^{2})$.

######  Lemma 3.6.

Let $\Delta,d,k$ be positive integers and let $H$ be an $n$-vertex graph with
$\Delta(H)\leq\Delta$, such that $H\subset T\boxtimes K_{s}$ for some
$s=\Omega(e^{\sqrt{\log{n}}})$ and a tree $T$ with $\Delta(T)\leq d$ and
$v(T)=\tau=\tau(n)$. Then $\hat{r}_{k}(H)=O(\tau s^{2}(\frac{\log
s}{s})^{1/\Delta})$.

  * Proof of Theorem 1.1.

Let $H$ be an $n$-vertex graph of maximum degree $\Delta$ and treewidth
$t=t(n)$. By Lemma 2.1, we know that $H\subseteq T\boxtimes K_{s}$ for
$s=\Theta(t\log n)$ and $v(T)=O(n/s)$, with $\Delta(T)\leq d=d(\Delta)$. Now,
by Lemma 3.5, the size-Ramsey number of $H$ is $O(ns)=O(nt\log n)$, which
gives the first part of the theorem.

For the second part, assume $t=\Omega(e^{\sqrt{\log{n}}})$. Note that by Lemma
3.6 and since $s=\Theta(t\log n)=\Omega(e^{\sqrt{\log{n}}})$, we have
$\hat{r}(H)=O(ns(\frac{\log s}{s})^{1/\Delta})=\tilde{O}(nt^{1-1/\Delta})$, as
required. ∎

###  3.3 Proof of Lemma 3.5

In this section, we give the proof of our first key lemma. We build our host
graph in a way that is convenient for the structure $T\boxtimes K_{s}$ we know
our graph $H$ has. Namely, we take a graph $\mathcal{R}$ that is Ramsey for a
constant blow-up of $T$ and blow it up by a factor of roughly $s$. We then
make use of Lemma 3.4 to get colorful lower-regular pairs within each random
bipartite graph, thus yielding an auxiliary coloring of $\mathcal{R}$. Next,
using that we picked $\mathcal{R}$ to be Ramsey for a constant blow-up of $T$,
we find a monochromatic copy of the latter in the auxiliary coloring, which
corresponds to a monochromatic $T$-shaped structure of lower-regular pairs in
our host graph. We can then use an approach similar to the embedding lemma to
embed $H$ into that monochromatic structure, being guided by the containment
of $H$ in $T\boxtimes K_{s}$ to map each vertex to an appropriate set.

  * Proof of Lemma 3.5.

Set $C^{-1}\ll\lambda\ll\varepsilon\ll k^{-1},\Delta^{-1},d^{-1}$. Let
$F=T\boxtimes K_{\Delta+1}$ and note that $F$ has treewidth at most
$2\Delta+2$ by the definition of treewidth. Let $\mathcal{R}$ be the graph
given by Theorem 3.1 which is $k$-Ramsey for $F$ and which has
$O(v(F))=O(\tau)$ vertices and constant maximum degree. The host graph for $H$
which we will consider is $G=\mathcal{R}\boxtimes K_{Cs}$. Note that $G$ has
$O(\tau s^{2})$ edges. For each $x\in V(\mathcal{R})$, denote the copy of
$K_{Cs}$ corresponding to $x$ by $V_{x}$. Consider an arbitrary $k$-coloring
of the edges of $G$.

We apply Lemma 3.4 with $p=1$ and $\lambda$ to the graph $\Gamma:=G$, which is
a blow-up of $\mathcal{R}$. Hence, we get a coloring of the edges of
$\mathcal{R}$ and, for each $x\in V(\mathcal{R})$, a subset $U_{x}\subseteq
V_{x}$ of size $\lambda Cs$, such that for every edge $\\{x,y\\}$ in
$\mathcal{R}$, the edges between $U_{x}$ and $U_{y}$ form an
$(\varepsilon,\frac{1}{2k},1)$-dense pair in the color of the edge $\\{x,y\\}$
(meaning that the density between every two sets $X\subseteq U_{x}$ and
$Y\subseteq U_{y}$ of sizes $|X|\geq\varepsilon|U_{x}|$ and
$|Y|\geq\varepsilon|U_{y}|$ is at least $\frac{1}{2k}-\varepsilon$).

Now, since $\mathcal{R}$ is $k$-Ramsey for $F$, there is a monochromatic copy
of $F$ in $\mathcal{R}$, which in turn means that for every edge $\\{x,y\\}$
of that copy, the pair $U_{x}$ and $U_{y}$ forms a
$(\varepsilon,\frac{1}{2k},1)$-dense pair in the same color, say red. As a
last step before describing the embedding process, for each $v\in V(T)$,
denote with $H_{v}$ the subgraph of $H$ which lives inside of the copy of
$K_{s}$ that corresponds to the vertex $v$ (recall that $H\subseteq T\boxtimes
K_{s}$). Since $H$ has maximum degree $\Delta$, it is $(\Delta+1)$-partite, so
denote by $H_{v}^{1},\ldots,H_{v}^{d+1}$ one such partition of $H_{v}$, for
each $v\in V(T)$. To summarize, we now want to embed $H\subseteq T\boxtimes
K_{s}$ into the red subgraph of $G$ which is obtained from $T\boxtimes
K_{\Delta+1}\boxtimes K_{\lambda Cs}$ by replacing the complete bipartite
graphs between the relevant copies of $K_{\lambda Cs}$ by
$(\varepsilon,\frac{1}{2k},1)$-dense pairs.

The embedding of $H$ into the found red subgraph of $G$ is done by a standard
procedure, which is a variant of the well-known embedding lemma. Briefly, for
each $v\in V(T)$, we will want to embed $H_{v}$ into $v\boxtimes
K_{\Delta+1}\boxtimes K_{\lambda Cs}$, so that each $H_{v}^{i}$ is embedded
into its own copy of $K_{\lambda Cs}$ in $v\boxtimes K_{\Delta+1}\boxtimes
K_{\lambda Cs}$. This embedding can be done vertex by vertex, crucially
maintaining the following invariant. For each vertex $x\in V(H)$ which has
been assigned to the copy $U$ of $K_{\lambda Cs}$ but has not yet been
embedded, we consider the ‘candidate set’ $C_{x}$ that consists of all the
vertices in $U$ that are in the common neighbourhood of all already embedded
neighbours of $x$ in $H$. While embedding $H$, we ensure that for each such
$x$, the size of the candidate set $C_{x}$ is at least
$(\frac{1}{4k})^{i}|U|$, where $i$ is the number of neighbours of $x$ in $H$
which are already embedded at the observed point of the embedding process.
When it is time for vertex $x$ to be embedded, we choose a vertex $y\in C_{x}$
for that purpose, in such a way that $y$ has enough neighbours in the
candidate set of each neighbour $x^{\prime}$ of $x$ in $H$ yet to be embedded,
in order to preserve the aforementioned invariant. This is possible because,
due to the lower-regular properties of the graph between $C_{x}$ and
$C_{x^{\prime}}$, at most $\varepsilon\lambda Cs$ of the vertices in $C_{x}$
have degree less than $\frac{1}{4k}|C_{x^{\prime}}|$ into $C_{x^{\prime}}$.
Additionally, at most $s$ many vertices in $C_{x}$ are already taken by
vertices previously embedded in $U$, leaving us with at least

$|C_{x}|-\Delta\varepsilon\lambda
Cs-s\geq\Big{(}\frac{1}{4k}\Big{)}^{\Delta}\lambda Cs-\Delta\varepsilon\lambda
Cs-s\gg 1$

viable candidates for the embedding of $x$, where we used that
$\Delta(H)\leq\Delta$ and $(\frac{1}{4k})^{\Delta}\gg\varepsilon$. Thus, we
can continue doing this until we embed the whole graph $H$. For more details,
we refer the reader to [7] where such an embedding lemma is proven; the
difference here is that we have more than a constant number of large cliques
in which we want to embed, but the proof is essentially the same.∎

###  3.4 Proof of Lemma 3.6

We make use of the following result, which allows us to embed any bounded-
degree subgraph of a blow-up of a bounded-degree graph $\mathcal{R}$ into a
certain blow-up of $\mathcal{R}$ where the bipartite graphs between the parts
are lower-regular pairs as in Definition 3.2. Although here we only apply the
lemma below with $\mathcal{R}$ being a tree, we state it in this more general
form, as it might be of independent interest and may prove to be useful in
other settings which deal with embedding bounded-degree graphs.

######  Lemma 3.7.

Let $\Delta,d,\rho^{-1}\ll\varepsilon^{-1}\ll C^{\prime}\ll C$ and $n$ be
large enough. Let $s=\Omega(e^{\sqrt{\log{n}}})$ and $\frac{n}{s}\leq\tau\leq
n$. Set $p:=C\big{(}\frac{\log{s}}{s}\big{)}^{1/\Delta}$ and
$\tilde{\Delta}:=\Delta^{4}+2\Delta+1$. Then w.h.p. $G\sim
G(\tau\tilde{\Delta}C^{\prime}s,p)$ is such that the following holds. Let $H$
be an $n$-vertex graph of maximum degree $\Delta$ that is a subgraph of
$\mathcal{R}\boxtimes K_{s}$ for some $\tau$-vertex graph $\mathcal{R}$ with
$\Delta(\mathcal{R})\leq d$. Let $J:=\mathcal{R}\boxtimes K_{\tilde{\Delta}}$
and $F\subseteq G$ be a graph with vertex set $V(F)=\bigcup_{x\in V(J)}F_{x}$
such that $|F_{x}|=C^{\prime}s$ for each $x\in V(J)$ and edge set consisting
of an $(\varepsilon,\rho,p)$-dense bipartite graph between $F_{x}$ and $F_{y}$
for each $xy\in E(J)$. Then $H$ can be embedded in $F$.

The proof of Lemma 3.7 mostly follows the approach from [23], with some
changes needed for our setting. We defer it to the appendix.

We are now ready to present the proof of our second key lemma. It makes use of
the same main ideas as the first one, except that to get the tighter bound,
the complete bipartite graphs between the sets of the host graph are now
replaced by random graphs with smaller than constant density $p$. This drop in
density then requires a much more careful treatment of the embedding process
of $H$, for which the embedding lemma no longer suffices. This is where Lemma
3.7 proves to be helpful.

  * Proof of Lemma 3.6.

Let $H$ be as given above. We shall show that there exists a graph $G$ with
$O(\tau s^{2-1/\Delta}\log^{1/\Delta}s)$ many edges such that
$G\rightarrow_{k}H$.

It will be convenient to define the following constants. Let
$\tilde{\Delta}:=\Delta^{4}+2\Delta+1$ and let

$\Delta,d,k\ll d^{\prime}\ll\varepsilon^{-1}\ll C^{\prime}\ll C.$

Let $p=C\big{(}\frac{\log{s}}{s}\big{)}^{1/\Delta}$. Let $\lambda$ be as given
by Lemma 3.4 with $k:=k$, $\varepsilon:=\varepsilon$, and
$\Delta:=d^{\prime}$.

Let $\mathcal{R}$ be the graph that is $k$-Ramsey for all
$\tau\tilde{\Delta}$-vertex graphs of maximum degree $\tilde{\Delta}(d+1)$ and
maximum treewidth $2\tilde{\Delta}$ given by Theorem 3.1. In particular,
$\mathcal{R}\rightarrow_{k}T\boxtimes K_{\tilde{\Delta}}$, since by the
definition of treewidth, $T\boxtimes K_{\tilde{\Delta}}$ has treewidth at most
$2\tilde{\Delta}$. Note that $\mathcal{R}$ has $O(\tau)$ vertices and constant
maximum degree, say $d^{\prime}$. We define our _host graph_ $G$ to be
obtained by replacing each $v\in V(\mathcal{R})$ with an independent set
$V_{v}$ on $\lambda^{-1}C^{\prime}s$ vertices and each edge $uv\in
E(\mathcal{R})$ with a random bipartite graph between $V_{u}$ and $V_{v}$ in
which each edge is added independently at random with probability $p$.

Now consider an arbitrary colouring of the edges of $G$ in $k$ colours. We
will show that $H$ can be embedded into one of the colour classes of $G$. By a
standard application of Chernoff bounds and a union bound, with high
probability each random bipartite graph between $V_{u}$ and $V_{v}$ with
$uv\in E(\mathcal{R})$ is $(\lambda,p)$-uniform. We fix an outcome of $G$ for
which this is the case. In particular, this also implies that $e(G)=O(\tau
s^{2-1/\Delta}\log^{1/\Delta}s)$.

We can now apply Lemma 3.4 with $\Gamma:=G$, $H:=\mathcal{R}$,
$n:=\lambda^{-1}C^{\prime}s$, and $p:=p$. This yields a $k$-colouring $\phi$
of the edges of $\mathcal{R}$ and, for every $x\in V(\mathcal{R})$, a subset
$U_{x}\subseteq V_{x}$ of size $|U_{x}|=\lambda|V_{x}|=C^{\prime}s$ such that
for each $xy\in E(\mathcal{R})$, the graph $(U_{x},U_{y};E_{\phi(xy)})$ is
$(\varepsilon,\frac{1}{2k},p)$-dense, where $E_{\phi(xy)}\subseteq E_{G}$ are
the edges in colour $\phi(xy)$.

Next, note that by Theorem 3.1, the $k$-colouring $\phi$ of the edges of
$\mathcal{R}$ contains a monochromatic copy of $T\boxtimes
K_{\tilde{\Delta}}=:J$. This implies that $G$ contains a monochromatic
subgraph $F$ with vertex set $V(F)=\bigcup_{x\in V(J)}F_{x}$ with
$|F_{x}|=C^{\prime}s$ for each $x\in V(J)$ and edge set consisting of an
$(\varepsilon,\frac{1}{2k},p)$-dense bipartite graph between $F_{x}$ and
$F_{y}$ for each $xy\in E(J)$.

We can now apply Lemma 3.7 with $\mathcal{R}:=T$ and $\rho:=\frac{1}{2k}$,
concluding that the graph $F$ contains $H$ as a subgraph. Since the copy of
$F$ in $G$ was monochromatic, this concludes the proof of the lemma. ∎

#### Acknowledgments

We thank David Wood for asking for the bounds on the size-Ramsey number of
bounded-degree planar graphs, which led to this paper [31].

##  Appendix A Appendix

Here we give the proof of Lemma 3.7, which roughly follows [23]. We begin by
establishing certain useful ‘uniformity’ properties, which allow us to proceed
with the embedding later. First we define two classes of ‘bad’ tripartite
graphs, $\mathcal{B}^{I}_{p}$ and $\mathcal{B}^{II}_{p}$, where density of
pairs $(X,Y),(Y,Z)$ is not inherited on one- respectively two-sided
neighborhoods.222The definition slightly deviates from Definition 13 in [23],
where the pairs $(X,Y)$ and $(Y,Z)$ are both $(\varepsilon,\alpha,p)$-dense.
Here, for technical reasons, we include the more general case of
$(\eta,\alpha,p)$-dense pairs $(X,Y)$ whereby $\eta$ can differ from
$\varepsilon$.

######  Definition A.1.

Let integers $m_{1},m_{2},m_{3}$ and reals
$\alpha,\varepsilon^{\prime},\varepsilon,\mu>0$, $\eta>0$, and $0<p\leq 1$ be
given.

  1. 1.

Let
$\mathcal{B}^{I}_{p}(m_{1},m_{2},m_{3},\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)$
be the family of tripartite graphs with vertex set $X\dot{\cup}Y\dot{\cup}Z$,
where $|X|=m_{1}$, $|Y|=m_{2}$, and $|Z|=m_{3}$, satisfying

    1. (a)

$(X,Y)$ is a $(\eta,\alpha,p)$-dense pair,

    2. (b)

$(Y,Z)$ is a $(\varepsilon,\alpha,p)$-dense pair, and

    3. (c)

there exists $X^{\prime}\subseteq X$ with $|X^{\prime}|\geq\mu|X|$ such that
for every $x\in X^{\prime}$ the pair $(N(x)\cap Y,Z)$ is not
$(\varepsilon^{\prime},\alpha,p)$-dense.

  2. 2.

Let
$\mathcal{B}^{II}_{p}(m_{1},m_{2},m_{3},\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)$
be the family of tripartite graphs with vertex set $X\dot{\cup}Y\dot{\cup}Z$,
where $|X|=m_{1}$, $|Y|=m_{2}$, and $|Z|=m_{3}$, satisfying

    1. (a)

$(X,Y)$ and $(X,Z)$ are $(\eta,\alpha,p)$-dense pairs,

    2. (b)

$(Y,Z)$ is a $(\varepsilon,\alpha,p)$-dense pair, and

    3. (c)

there exists $X^{\prime}\subseteq X$ with $|X^{\prime}|\geq\mu|X|$ such that
for every $x\in X^{\prime}$ the pair $(N(x)\cap Y,N(x)\cap Z)$ is not
$(\varepsilon^{\prime},\alpha,p)$-dense.

Graphs that do not contain large subgraphs — induced or not — from the two
above ‘bad’ families are then said to have a denseness property
$\mathcal{D}^{\Delta}_{N,p}$, which we make precise in the next definition.

######  Definition A.2.

For integers $N$ and $\Delta\geq 2$ and reals
$\alpha,\gamma,\varepsilon^{\prime},\varepsilon,\mu,\eta>0$ and $0<p\leq 1$ we
say that a graph $G=(V,E)$ with $V=[N]$ has the _denseness property_
$\mathcal{D}^{\Delta}_{N,p}(\gamma,\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)$,
if $G$ contains no member from

$B^{I}_{p}(m^{I}_{1},m^{I}_{2},m^{I}_{3},\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)\cup
B^{II}_{p}(m^{II}_{1},m^{II}_{2},m^{II}_{3},\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)$

with $m^{I}_{1},m^{I}_{3}\geq\gamma p^{\Delta-1}N$ and
$m_{2}^{I},m_{1}^{II},m_{2}^{II},m_{3}^{II}\geq\gamma p^{\Delta-2}N$ as a (not
necessarily induced) subgraph.

The following key technical lemma which is Corollary 16 in [23] (and follows
by repeatedly applying Proposition 15 therein) guarantees that random graphs
$G(N,p)$ enjoy this denseness property at various parameter scales, whenever
$p\gg(\frac{\log N}{N})^{\frac{1}{\Delta}}$. It will not be enough for our
purposes that this fails to hold with any probability $o(1)$. However,
performing the calculations explicitly allows us to bound the failure
probability precisely. The other adjustments in the proof will stem from the
changes in the definition of the ‘bad’ graphs.

######  Lemma A.3 (Corollary 16 in [23]).

For all integers $\Delta,\Delta^{\prime}\geq 2$ and all reals
$\alpha,\mu,\gamma,\varepsilon^{*}>0$, there exist $C>1$,
$\eta=\eta(\Delta,\alpha,\mu)$, and
$\varepsilon_{0},\ldots,\varepsilon_{\Delta^{\prime}}$ satisfying
$0<\varepsilon_{0}\leq\ldots\leq\varepsilon_{\Delta^{\prime}}\leq\varepsilon^{*}$
such that if $p>C(\log{N}/N)^{1/\Delta}$, then
$Pr[G(N,p)\in\cap_{k=1}^{\Delta^{\prime}}\mathcal{D}^{\Delta}_{N,p}(\gamma,\alpha,\varepsilon_{k},\varepsilon_{k-1},\mu,\eta)]\geq
1-N^{-\Theta(Np^{\Delta-2})}$.

  * Proof.

The proof is almost the same as that of Corollary 16 in [23], which can be
summarized roughly as follows. Restricting to the case of one-sided regularity
inheritance, one first considers the special case of a bad graph $T$ where the
two parts $X$ and $Z$ are of fixed size, namely only a $p$-fraction of the
size of $Y$ (the more general case can be reduced to this one). The bipartite
subgraphs $T[X,Y]$ and $T[Y,Z]$ are quite dense by assumption. Now consider
the violating set $X^{\prime}\subset X$, whose members $x\in X^{\prime}$ all
fail to produce $(\varepsilon^{\prime},\alpha,p)$-dense pairs $(N_{T}(x)\cap
Y,Z)$. We restrict our attention to $X^{\prime\prime}\subseteq X^{\prime}$
such that each $x\in X^{\prime\prime}$ has ‘large’ degree into $Y$. Because
$T[X,Y]$ is $(\eta,\alpha,p)$-dense, $X^{\prime\prime}$ contains at least half
of the vertices in $X^{\prime}$. Now one can show that each such vertex $x$
produces a set $Y^{\prime}_{x}\subset N_{T}(x)\cap Y$ of size
$\frac{\varepsilon^{\prime}\alpha pm}{2}$ which, together with $Z$ produces a
pair $(Y^{\prime}_{x},Z)$ of density strictly less than
$\alpha-\varepsilon^{\prime}$. Any superset $Y_{x}$ of $Y^{\prime}_{x}$ in $Y$
with size $\frac{\alpha pm}{2}$ then produces a violating pair, that is, the
pair $(Y_{x},Z)$ is not $(\varepsilon^{\prime},\alpha,p)$-dense. By repeating
this procedure for all $x\in X^{\prime\prime}$, we could produce an entire
family of violating pairs, which is unlikely to occur in $G(N,p)$. The latter
can be proven by a union bound via counting the ways of choosing the vertices
in the involved sets $X^{\prime\prime},Y,Z$ and the edges in the bipartite
graph $T[Y,Z]$ as well as the choices of the sets $Y_{x}$, which are limited
by sparse regularity inheritance from $T[Y,Z]$ (cf. [18] Theorem 3.6).

In what follows we note the necessary changes to Section 3.3 [23].

    * –

In the statement of Proposition 15, after
$\varepsilon=\varepsilon(\Delta,\alpha,\varepsilon^{\prime},\mu)>0$, add
”there exists $\eta=\eta(\Delta,\alpha,\mu)>0$” and change

$Pr[G(N,p)\in\mathcal{D}^{\Delta}_{N,p}(\gamma,\alpha,.\varepsilon_{k},\varepsilon_{k-1},\mu)]=1-o(1)$

to

$Pr[G(N,p)\in\mathcal{D}^{\Delta}_{N,p}(\gamma,\alpha,\varepsilon_{k},\varepsilon_{k-1},\mu,\eta)]\geq
1-N^{-\Theta(Np^{\Delta-2})}.$

    * –

In the proof of Corollary 16, add the argument $\eta$ to
$\mathcal{D}^{\Delta}_{N,p}(\gamma,\alpha,\varepsilon_{k},\varepsilon_{k-1},\mu)$.

    * –

Change the definition of $\hat{\mathcal{D}}^{\Delta}_{N,p}$ to include $\eta$
as an argument, in agreement with $\mathcal{D}^{\Delta}_{N,p}$.

    * –

In Proposition 17, add ”for each $0<\eta<\frac{\mu}{100},\frac{\alpha}{100}$”
and change the probability condition to
$Pr[G(N,p)\in\hat{\mathcal{D}}^{\Delta}_{N,p}(\gamma,\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)]\geq
1-N^{-\Theta(Np^{\Delta-2})}$. In particular, $\eta<\frac{\mu}{100}$ ensures
that $|X^{\prime\prime}|$ is large enough, see the change below on the lower
bound at the top of page 5052.

    * –

In the proof of Proposition 17:

      * *

Choose $C$, which was originally set to
$C=(\frac{4}{\gamma})^{\frac{1}{\Delta}}$, to be, say, $100$ times larger.
This will ensure the desired rate of decay later on in the proof, where the
failure probability is estimated by a bound where $p$, which depends linearly
on $C$, enters as $p^{2}$ in the exponent. See also the change on page 5051
indicated below.

      * *

Add $\eta$ as an argument to $\mathcal{B}^{I}_{p}$ and $\mathcal{B}^{II}_{p}$
everywhere since $T[X,Y]$ is $(\eta,\alpha,p)$-dense according to Definition
A.1 instead of $(\varepsilon,\alpha,p)$-dense as in [23].

      * *

On page 5050, ”Because of the assumption on $T$, the bipartite subgraphs
$T[X,Y]$ and $T[Y,Z]$ of $T$ contain at least $(\alpha-\varepsilon)p^{2}m^{2}$
edges each” — this continues to hold for $T[Y,Z]$ but is no longer true of
$T[X,Y]$, instead it contains at least $(\alpha-\eta)p^{2}m^{2}$ edges.

      * *

On page 5050, ”From the $(\varepsilon,\alpha,p)$-denseness …” towards the
bottom of the page changes to ”From the $(\eta,\alpha,p)$-denseness …” and
$|X^{\prime\prime}|\geq(1-\varepsilon/\mu)|X^{\prime}|$ changes to
$|X^{\prime\prime}|\geq(1-\eta/\mu)|X^{\prime}|$.

      * *

On page 5051, we get that the probability that $T[X^{\prime\prime},Y,Z]$
appears in $G(N,p)$ is at most $N^{-\Theta(Np^{\Delta-2})}$ as a result of the
new choice of $C$.

      * *

On top of page 5052, it is no longer true that $T[X,Y]$ and $T[X,Z]$ have at
least $(\alpha-\varepsilon)pm^{2}$ edges each, they have instead at least
$(\alpha-\eta)pm^{2}$ edges each.

      * *

On top of page 5052, in the lower bound for $|X^{\prime\prime}|$, we get
instead $(1-2\eta/\mu)|X^{\prime}|\geq|X^{\prime}|/2$, from the
$(\eta,\alpha,p)$-denseness of $T[X,Y]$ and $T[X,Z]$.

      * *

On page 5052, we get that the probability that a graph from
$\mathcal{B}_{p}^{II}(m,\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)$ is
contained in $G(n,p)$ is at most $N^{-\Theta(Np^{\Delta-2})}$.

    * –

In the proof of Proposition 15:

      * *

Change the third sentence to ”Indeed, roughly speaking, we show that each
’bad’ tripartite graph
$T\in\mathcal{B}_{p}^{II}(m_{1},m_{2},m_{3},\alpha,\varepsilon^{\prime},\varepsilon,\mu,\eta)$
with arbitrary $m_{1},m_{2},m_{3}\geq m$ contains a subgraph
$\hat{T}\in\mathcal{B}_{p}^{II}(m,\alpha,\varepsilon^{\prime}/2,\hat{\varepsilon},\mu/4,\hat{\eta})$
for some appropriate $\hat{\varepsilon}$ and $\hat{\eta}$”.

      * *

In Claim 18, add $\hat{\eta}$ to the list of given positive reals, add ”there
exists $\eta=\eta(\hat{\eta},\alpha,\mu)$”, and add $\eta$ as an argument to
$\mathcal{B}_{p}^{II}(m_{1},m_{2},m_{3},\alpha,\varepsilon^{\prime},\varepsilon,\mu)$
and $\hat{\eta}$ as an argument to
$\mathcal{B}_{p}^{II}(m,\alpha,\varepsilon^{\prime}/2,\hat{\varepsilon},\mu/4)$.

      * *

In the paragraph after Claim 18, add ”Pick
$\hat{\eta}<\frac{\mu}{400},\frac{\alpha}{400}$ for the application of Claim
18”, and add $\hat{\eta}$ as an argument to $\mathcal{B}^{I}_{p}$ and
$\mathcal{B}^{II}_{p}$; also change the probability to
$1-N^{-\Theta(Np^{\Delta-2})}$.

    * –

In the proof of Claim 18:

      * *

Add $\hat{\eta}$ to the list of given constants, and take
$\eta:=\min\\{\frac{\alpha}{400},\frac{\mu}{400},\varepsilon_{0}(\alpha,\beta,\hat{\eta})\\}$.

      * *

On page 5053, in the definition of $T=(X\dot{\cup}Y\dot{\cup}Z,E_{T})$, add
$\eta$ as an argument to $\mathcal{B}_{p}^{II}$.

      * *

On page 5053, replace $\varepsilon$ with $\eta$ everywhere in the sentence
”Owing to the choice of $\varepsilon$ …” (we can do this since
$\eta<\frac{\mu}{100}$).

      * *

On the bottom of page 5053, change the last sentence of the penultimate
paragraph to ”We shall show that with positive probability $\hat{T}$ is from
$\mathcal{B}_{p}^{II}(m,\alpha,\varepsilon^{\prime}/2,\hat{\varepsilon},\mu/4,\hat{\eta})$.

      * *

In the last paragraph of page 5053, replace $\hat{\varepsilon}$ with
$\hat{\eta}$ when it comes to pairs $(\hat{X},\hat{Y})$ and
$(\hat{X},\hat{Z})$.

      * *

On the bottom of page 5054, add $\hat{\eta}$ as an argument to
$\mathcal{B}_{p}^{II}(m,\alpha,\varepsilon^{\prime}/2,\hat{\varepsilon},\mu/4)$.

∎

Let $G=(V,E)$ be a graph and $k\geq 1$ be an integer. We define an auxiliary
bipartite graph $\Gamma(k,G)=(\binom{V}{k}\dot{\cup}V,E_{\Gamma(k,G})$ by

$(K,v)\in E_{\Gamma(k,G)}\Longleftrightarrow\\{w,v\\}\in E(G)\text{ for all
}w\in K.$

The next definition and lemma will help us conclude that if $G$ is the random
graph $G(N,p)$, then $\Gamma(k,G)$ has no ”dense parts”.

######  Definition A.4.

Let integers $N$ and $k\geq 1$ and reals $\xi>0$ and $0<p\leq 1$ be given. A
graph $G=(V,E)$ with $V=[N]$ has the _congestion property_
$\mathscr{C}^{k}_{N,p}(\xi)$ if for every $U\subseteq V$ and every family
$\mathcal{F}_{k}\subseteq\binom{V\setminus U}{k}$ of pairwise disjoint
$k$-sets with

  * •

$|\mathcal{F}_{k}|\leq\xi N$ and

  * •

$|U|\leq|\mathcal{F}_{k}|$

we have

$e_{\Gamma(k,G)}(\mathcal{F}_{k},U)\leq p^{k}|\mathcal{F}_{k}||U|+6\xi
Np^{k}|\mathcal{F}_{k}|.$

Similarly to the denseness property from Lemma A.3, we will require better
control over the probability that a graph fails to have the congestion
property than the original phrasing of Corollary 12 in [23]. We will hence
adjust the proof accordingly.

######  Lemma A.5 (Corollary 12 in [23]).

For every integer $\Delta\geq 1$ and real $\xi>0$, there exists $C>1$ such
that if $p>C(log{N}/N)^{1/\Delta}$, then
$Pr[G(N,p)\in\cap_{k=1}^{\Delta}\mathscr{C}_{N,p}^{k}(\xi)]=1-e^{-100\log^{2}{N}}$.

  * Proof.

The proof is almost the same as that of Corollary 12 in [23]. In what follows
we note the necessary changes in Section 3.2.

    * –

In the statement of Proposition 11, change $o(1)$ to $e^{-200\log^{2}{N}}$.

    * –

At the end of the analysis for Case 1 in the proof of Proposition 11, note
that the probability of the bad event can in fact be upper bounded by
$e^{-2N}$.

    * –

At the end of Case 2 in the proof of Proposition 11, one can upper bound the
probability of the bad event by $e^{-400\log^{2}{N}}$, for $C$ large enough.

∎

We are now ready to prove Lemma 3.7, which we restate here for convenience of
the reader. See 3.7

  * Proof of Lemma 3.7.

We begin the proof by setting the constants. This will allow for the
application of Lemmas A.3 and A.5 at the necessary level. In particular, the
subgraphs of our host graph will have denseness and congestion properties
which still hold after taking union bounds. The second step will consist of
preparing our graph $H$ for its embedding. Here we use the assumption that $H$
is a subgraph of $\mathcal{R}\boxtimes K_{s}$. We first partition the vertices
of $H$ according to the copy of $K_{s}$, indexed by the vertices of
$\mathcal{R}$, into which they are mapped. This ordered partition is then
refined using a coloring (of the third power of $H^{3}$), ensuring that no two
vertices at distance at most $3$ with respect to $H$ are mapped to the same
class. The actual embedding of $H$ into $F$ is then constructed inductively,
maintaining at each step $\ell$ for every not yet embedded vertex $z$ of $H$ a
large enough candidate set $C_{\ell}(z)$ which takes into account all the
already embedded neighbors of $z$, and ensuring that the candidate sets for
pairs of not yet embedded vertices $z,z^{\prime}$ that are neighbors in $H$
have candidate sets $C_{\ell}(z),C_{\ell}(z^{\prime})$ which induce an
appropriately regular pair in $F$. Given a vertex $y\in H$ and a candidate set
$C_{\ell}(y)$, a naive embedding of $y$ into it will not work, as previously
embedded vertices from the same class may have exhausted the set. Instead, we
use Hall’s condition to find one distinct vertex in $C_{\ell}(y)$ for each $y$
in the current vertex class of $H$ simultaneously.

Notation and Constants. We first fix some notation. In $J=\mathcal{R}\boxtimes
K_{\tilde{\Delta}}$, for each $x\in V(\mathcal{R})$, we denote by $J_{x}$ the
copy of $K_{\tilde{\Delta}}$ that corresponds to $x$, and by $\mathbf{F}_{x}$
the copy of $K_{\tilde{\Delta}}\boxtimes K_{C^{\prime}s}$ in $F$ that
corresponds to $J_{x}$.

Next, we choose the constants. Let $\varepsilon_{0}:=\varepsilon$,
$\mu:=\frac{1}{4\Delta^{2}}$, $\xi:=\frac{1}{(d+1)\tilde{\Delta}C^{\prime}}$
and $\gamma:=\frac{1}{(2/\rho)^{\Delta-1}3\tilde{\Delta}}$. Let $\eta$ be as
given by Lemma A.3 applied with $\Delta:=\Delta$, $\alpha:=\rho$, $\mu:=\mu$
and

$0<\varepsilon_{0}\leq\ldots\leq\varepsilon_{2\Delta}\leq\varepsilon^{*}:=\min\\{\frac{\rho}{6\tilde{\Delta}},\eta\\}.$

be as given by Lemma A.3 applied with $\Delta:=\Delta$,
$\Delta^{\prime}:=2\Delta$, $\alpha:=\rho$, $\mu:=\mu$, $\gamma:=\gamma$. The
value of $\varepsilon^{*}$ ensures in particular that in the embedding which
we will construct step by step, the candidate sets for not yet embedded
vertices are large enough. The choice of $\gamma$ will ensure that the
candidate sets are large enough to form dense pairs. The choice of $\xi$ will
enable us to verify Hall’s condition.

For each distinct $x,y,z\in V(\mathcal{R})$ such that $xy,yz\in
E(\mathcal{R})$, apply Lemma A.3 with $\Delta:=\Delta$,
$\Delta^{\prime}:=2\Delta$, $\alpha:=\rho$, $\mu:=\mu$, $\gamma:=\gamma$,
$\varepsilon^{*}:=\varepsilon^{*}$ and $N:=3\tilde{\Delta}C^{\prime}s$ to
$F[\mathbf{F}_{x}\cup\mathbf{F}_{y}\cup\mathbf{F}_{z}]$, which is a subgraph
of $G(N,p)$. By a union bound over all at most $O(t)$ such triples $x,y,z\in
V(\mathcal{R})$, we conclude that w.h.p. for each $xy,yz\in E(\mathcal{R})$,
we have
$F[\mathbf{F}_{x}\cup\mathbf{F}_{y}\cup\mathbf{F}_{z}]\in\cap_{k=1}^{2\Delta}\mathcal{D}^{\Delta}_{N,p}(\gamma,\rho,\varepsilon_{k},\varepsilon_{k-1},\mu,\eta)$,
since

$O(t)s^{-\Theta(sp^{\Delta-2})}=O(n)e^{-\Theta(sp^{\Delta-2}\log{s})}=O(n)e^{-\Theta(s^{2/\Delta}\log^{(2\Delta-2)/\Delta}{s})}=O(n)e^{-\omega(\log{n})}=o(1).$

From now on we condition on this being the case.

Similarly, for each $x\in V(\mathcal{R})$, we apply Lemma A.5 with
$\Delta:=\Delta$, $\xi:=\xi$ and
$N:=\big{(}\mathsf{deg}_{\mathcal{R}}(x)+1\big{)}\tilde{\Delta}C^{\prime}s$ to
$F[\bigcup_{y\in N_{\mathcal{R}}(x)}\mathbf{F}_{y}\cup\mathbf{F}_{x}]$, which
we can do since it is a subgraph of $G(N,p)$. We next apply a union bound over
all $t$ such vertices $x\in V(\mathcal{R})$, to show that the probability that
for some $x\in V(\mathcal{R})$, we have $F[\bigcup_{y\in
N_{\mathcal{R}}(x)}\mathbf{F}_{y}\cup\mathbf{F}_{x}]\notin\cap_{k=1}^{\Delta}\mathscr{C}_{N,p}^{k}(\xi)$
is at most

$te^{-100\log^{2}(2\tilde{\Delta}C^{\prime}s)}\leq ne^{-100\log^{2}{s}}\leq
ne^{-100\log^{2}(\Omega(e^{\sqrt{\log{n}}}))}\leq ne^{-25\log{n}}=o(1).$

From here on we condition on this event not occurring.

Preparation of $H$. We start by preparing $H$ for the embedding. For this,
consider an embedding $\psi:H\rightarrow\mathcal{R}\boxtimes K_{s}$. We
partition $V(H)$ into classes $\\{S_{x}\\}_{x\in V(\mathcal{R})}$ with $v\in
S_{x}$ for $x\in V(\mathcal{R})$ if $\psi(v)$ belongs to the copy of $K_{s}$
in $\mathcal{R}\boxtimes K_{s}$ that corresponds to $x$. We denote
$H_{x}:=H[S_{x}]$. Let $q$ be an arbitrary ”root” of $\mathcal{R}$ and
consider a breadth-first ordering of $V(\mathcal{R})$ starting from $q$,
namely $q=x_{1},\ldots,x_{t}$. We will embed $S_{x}$ into $\mathbf{F}_{x}$ for
each $x=x_{1},\ldots,x_{t}$ in this order. For each $x\in V(\mathcal{R})$, let
$p_{1}(x),\ldots,p_{d_{x}}(x)$ be the ”parents” of $x$, namely those of its
neighbours that come before $x$ in the order $x_{1},\ldots,x_{t}$. Note that
$0\leq d_{x}\leq d$. With slight abuse of notation, denote
$S_{p(x)}:=\bigcup_{i=1}^{d_{x}}S_{p_{i}(x)}$.

Consider the third power $H^{3}$ of $H$, that is, $uv\in E(H^{3})$ if and only
if $u\neq v$ and there is a path between $u$ and $v$ in $H$ consisting of at
most $3$ edges. Note that
$\Delta(H^{3})\leq\Delta+\Delta(\Delta-1)+\Delta(\Delta-1)^{2}=\Delta^{3}-\Delta^{2}+\Delta$
and therefore $\chi(H^{3})\leq\Delta^{3}-\Delta^{2}+\Delta+1$. Fix some $x\in
V(\mathcal{R})$ and let $f_{x}$ be a $\Delta^{3}-\Delta^{2}+\Delta+1$-vertex
colouring of $H^{3}[S_{x}]$. Then $f_{x}$ partitions $S_{x}$ into
$\Delta^{3}-\Delta^{2}+\Delta+1$ classes such that if two vertices $u,v$ are
in the same class, they have distance at least $4$ in $H$, and so there are no
edges between $N_{H}(u)$ and $N_{H}(v)$. Next, we refine this partition
depending on the ”left-degrees” of the vertices. We say that $u,v\in S_{x}$
are equivalent if $f_{x}(u)=f_{x}(v)$ and

$|N_{H}(u)\cap\Big{(}\\{w\in S_{x}:f_{x}(w)<f_{x}(u)\\}\cup
S_{p(x)}\Big{)}|=|N_{H}(v)\cap\Big{(}\\{w\in S_{x}:f_{x}(w)<f_{x}(v)\\}\cup
S_{p(x)}\Big{)}|.$

Note that vertices of $S_{x}$ will be embedded in order of increasing colour
according to $f_{x}$. Thus, two vertices in $S_{x}$ are equivalent if they
have the same colour by $f_{x}$ and the same number of neighbours that will be
embedded before them. This equivalence relation partitions $S_{x}$ into at
most $(\Delta^{3}-\Delta^{2}+\Delta+1)(\Delta+1)=\tilde{\Delta}$ many classes.
Denote the partition classes by $W^{x}_{1},\ldots,W^{x}_{\tilde{\Delta}}$,
some of which may be empty, and let $g_{x}:S_{x}\rightarrow[\tilde{\Delta}]$
be the corresponding partition function, that is, for $w\in S_{x}$, we have
$g_{x}(w)=j$ if and only if $w\in W^{x}_{j}$. Note that
$W^{x}_{1},\ldots,W^{x}_{\tilde{\Delta}}$ are ordered in increasing order of
$f_{x}$. Each $W^{x}_{i}$ will be embedded into a different $F_{y}$ with $y\in
J_{x}$, but for simplicity we now rename these vertex classes so that we can
treat all of them at the same time.

Set $Q:=t\tilde{\Delta}$. Then let $W_{1},\ldots,W_{Q}$ be obtained by
concatenating the sequences
$(W^{x_{1}}_{1},\ldots,W^{x_{1}}_{\tilde{\Delta}}),$
$\ldots,(W^{x_{t}}_{1},\ldots,W^{x_{t}}_{\tilde{\Delta}})$ in this order, and
again let $g:V(H)\rightarrow[Q]$ be the corresponding partition function, that
is, $g(w)=j$ if and only if $w\in W_{j}$ for $w\in V(H)$. Thus, if
$g(u)=g(v)$, then

$|N_{H}(u)\cap\\{w\in V(H):g(w)<g(u)\\}|=|N_{H}(v)\cap\\{w\in
V(H):g(w)<g(v)\\}|.$

Let $u\in V(H)$ and $\ell\leq g(u)$. Then we define the _left-degree_ of $u$
with respect to $g$ and $\ell$ as

$\mathsf{ldeg}^{\ell}_{g}(u):=|N_{H}(u)\cap\\{w\in V(H):g(w)\leq\ell\\}|.$

Inductively embedding $H$ into $F$. We proceed to embed $H$ into $F$. For
this, we first relabel the vertex classes $\\{F_{y}\\}_{y\in V(J)}$ by
ordering them as $F_{1},\ldots,F_{Q}$, where in the order $x_{1},\ldots,x_{t}$
of $V(\mathcal{R})$ that we fixed above, for each $x_{i}$ we have that
$\\{F_{y}\\}_{y\in J_{x_{i}}}$ are relabelled as
$F_{(i-1)\tilde{\Delta}+1},\ldots,F_{i\tilde{\Delta}}$ (in arbitrary order).
We will proceed by induction, embedding $W_{i}$ into $F_{i}$ for each
$i=1,\ldots,Q$. Note that even though $J$ is not a complete graph, due to the
fact that $H$ is a subgraph of $\mathcal{R}\boxtimes K_{s}$ and the way we
picked $W_{1},\ldots,W_{Q}$ and $F_{1},\ldots,F_{Q}$, we have that if $u\in
W_{i}$ and $v\in W_{j}$ and $uv\in E(H)$, then there is an
$(\varepsilon_{0},\rho,p)$-dense bipartite graph between $F_{i}$ and $F_{j}$.

Throughout our embedding, we make sure that the following statement
$(\mathcal{S}_{\ell})$ holds for $\ell=0,1,\ldots,Q$:

$\displaystyle(\mathcal{S}_{\ell})$ $\displaystyle\text{ There exists a
partial embedding }\phi_{\ell}\text{ of }H[\cup_{j=1}^{\ell}W_{j}]\text{ into
}F[\cup_{j=1}^{\ell}F_{j}]\text{ such that for every }$ $\displaystyle
z\in\cup_{j=\ell+1}^{Q}W_{j}\text{ there exists a candidate set
}C_{\ell}(z)\subseteq V(F)\text{ given by }$ $\displaystyle\text{(a)
}C_{\ell}(z)=\cap\\{N_{F}(\phi_{\ell}(x)):x\in N_{H}(z)\text{ and
}g(x)\leq\ell\\}\cap F_{g(z)},$ satisfying $\displaystyle\text{(b)
}|C_{\ell}(z)|\geq\Big{(}\frac{\rho
p}{2}\Big{)}^{\mathsf{ldeg}^{\ell}_{g}(z)}m\text{, where
}m=|F_{g(z)}|=C^{\prime}s,\text{ and}$ $\displaystyle\text{(c) for every edge
}\\{z,z^{\prime}\\}\in E(H)\text{ with }g(z),g(z^{\prime})>\ell\text{ the pair
}(C_{\ell}(z),C_{\ell}(z^{\prime}))\text{ is }$ $\displaystyle\hskip
17.07182pt(\varepsilon_{\mathsf{ldeg}_{g}^{\ell}(z)+\mathsf{ldeg}_{g}^{\ell}(z^{\prime})},\rho,p)\text{-dense
in }F.$

The inductive statement $(\mathcal{S}_{\ell})$ tells us that the first $\ell$
classes $W_{1},\ldots,W_{\ell}$ of $H$ can be embedded into
$F_{1}\cup\ldots\cup F_{\ell}$ in such a way that for every not yet embedded
vertex $z\in W_{\ell+1}\cup\ldots\cup W_{Q}$, there is a large enough
candidate set $C_{\ell}(z)$ that consists of the intersection of $F_{g(z)}$
and the neighbourhoods of all already embedded neighbours of $z$. The third
condition of $(\mathcal{S}_{\ell})$ additionally ensures that all pairs of
candidate sets inherit regularity.

Note that from $(\mathcal{S}_{Q})$ it follows that $H$ can be embedded into
$F$, which means that showing that
$(\mathcal{S}_{0}),\ldots,(\mathcal{S}_{Q})$ hold completes the proof of Lemma
3.7. We next prove that $(\mathcal{S}_{\ell})$ holds for $\ell=0,1,\ldots,Q$
by induction.

Basis of the induction: $\ell=0$. We then have that $\phi_{0}$ is the empty
embedding and $C_{0}(z)=F_{g(z)}$ for every $z\in V(H)$ by (a). This implies
that property (b) also holds, as $|C_{0}(z)|=m$ and
$\mathsf{ldeg}^{0}_{g}(z)=0$. Property (c) holds since, as mentioned above,
for each $zz^{\prime}\in E(H)$, there is an $(\varepsilon_{0},\rho,p)$-dense
graph between $F_{g(z)}=C_{0}(z)$ and $F_{g(z^{\prime})}=C_{0}(z^{\prime})$.

Induction step: $\ell\rightarrow\ell+1$. Suppose that $(\mathcal{S}_{\ell})$
holds for some $\ell<Q$. We will now extend $\phi_{\ell}$ to an embedding
$\phi_{\ell+1}$ that satisfies (a), (b), and (c) to show that
$(\mathcal{S}_{\ell+1})$ holds. We do this in the following way. Firstly, for
each $y\in W_{\ell+1}$, we identify a subset $C(y)\subseteq C_{\ell}(y)$ such
that if $y$ is embedded into some vertex from $C(y)$, then for every ”right-
neighbour” $z$ of $y$ in $H$, the candidate set
$C_{\ell+1}(z):=C_{\ell}(z)\cap N_{F}(\phi_{\ell+1}(y))$ will be such that
properties (b) and (c) will still hold.

However, since if $\mathsf{ldeg}^{\ell}_{g}\geq 1$, we have
$|C(y)|\leq|C_{\ell}(y)|=o(s)\ll|W_{\ell+1}|$, we cannot greedily pick an
embedding of each $y$ into $C(y)$, as this way some $C(y)$ may be entirely
occupied by other embeddings before we get to embed it. Thus, in a second step
we will use Hall’s condition to find distinct representatives for
$\\{C(y):y\in W_{\ell+1}\\}$, and then we will set $\phi_{\ell+1}(y)$ to be
the representative of $C(y)$. We now describe these two steps in detail.

Let $y\in W_{\ell+1}$, and set

$N_{H}^{\ell+1}(y):=\\{z\in N_{H}(y):g(z)>\ell+1\\}.$

We say that $v\in C_{\ell}(y)$ is _bad_ (that is, it will not be in $C(y)$) if
there is some vertex $z\in N_{H}^{\ell+1}(y)$ such that the set $N_{F}(v)\cap
C_{\ell}(z)$ does not satisfy condition (b) or (c) of $(\mathcal{S}_{\ell+1})$
and therefore cannot become $C_{\ell+1}(z)$.

We start by focusing on (b) of $(\mathcal{S}_{\ell+1})$. Let $z\in
N_{H}^{\ell+1}(y)$. We know by (c) of $(\mathcal{S}_{\ell})$ that
$(C_{\ell}(y),C_{\ell}(z))$ is an
$(\varepsilon_{\mathsf{ldeg}_{g}^{\ell}(y)+\mathsf{ldeg}_{g}^{\ell}(z)},\rho,p)$-dense
pair. Thus, there are at most
$\varepsilon_{\mathsf{ldeg}_{g}^{\ell}(y)+\mathsf{ldeg}_{g}^{\ell}(z)}|C_{\ell}(y)|\leq\varepsilon_{2\Delta}|C_{\ell}(y)|$
vertices $v$ in $C_{\ell}(y)$ such that

$|N_{F}(v)\cap
C_{\ell}(z)|<\Big{(}\rho-\varepsilon_{\mathsf{ldeg}_{g}^{\ell}(y)+\mathsf{ldeg}_{g}^{\ell}(z)}\Big{)}p|C_{\ell}(z)|.$

Considering all $z\in N_{H}^{\ell+1}(y)$ in the same way, it follows that for
all but at most $\Delta\varepsilon_{2\Delta}|C_{\ell}(y)|$ vertices $v\in
C_{\ell}(y)$, the following holds for all $z\in N_{H}^{\ell+1}(y)$:

$|N_{F}(v)\cap
C_{\ell}(z)|\geq\Big{(}\rho-\varepsilon_{2\Delta}\Big{)}p|C_{\ell}(z)|$
$\geq\Big{(}\rho-\varepsilon_{2\Delta}\Big{)}p\Big{(}\frac{\rho
p}{2}\Big{)}^{\mathsf{ldeg}^{\ell}_{g}(z)}|F_{g(z)}|\geq\Big{(}\frac{\rho
p}{2}\Big{)}^{\mathsf{ldeg}_{g}^{\ell+1}(z)}|F_{g(z)}|,$

where for the penultimate inequality we used condition (b) of
$(\mathcal{S}_{\ell})$ and the final inequality follows from our choice of
$\varepsilon^{*}\geq\varepsilon_{2\Delta}$.

Next, we consider property (c) of $(\mathcal{S}_{\ell+1})$. Let
$e=\\{z,z^{\prime}\\}$ with $g(z),g(z^{\prime})>\ell+1$ and with at least one
of $z,z^{\prime}$ in $N_{H}^{\ell+1}(y)$. The number of these edges is at most
$\Delta(\Delta-1)<\Delta^{2}$. Let $\tilde{y},\tilde{z},\tilde{z}^{\prime}\in
V(\mathcal{R})$ be such that
$F_{g(y)}\subseteq\mathbf{F}_{\tilde{y}},F_{g(z)}\subseteq\mathbf{F}_{\tilde{z}},F_{g(z^{\prime})}\subseteq\mathbf{F}_{\tilde{z}^{\prime}}$,
and let $j:=\mathsf{ldeg}^{\ell}_{g}(z)+\mathsf{ldeg}^{\ell}_{g}(z^{\prime})$.
If $z,z^{\prime}\in N_{H}^{\ell}(y)$, we have

$\max\\{\mathsf{ldeg}_{g}^{\ell}(y),\mathsf{ldeg}_{g}^{\ell}(z),\mathsf{ldeg}_{g}^{\ell}(z^{\prime})\\}\leq\Delta-2,$

because each of $y,z,z^{\prime}$ has at least two neighbours in
$W_{\ell+1}\cup\ldots\cup W_{Q}$. Property (b) of $(\mathcal{S}_{\ell})$ then
implies

$\min\\{|C_{\ell}(y),C_{\ell}(z),C_{\ell}(z^{\prime})|\\}\geq\Big{(}\frac{\rho
p}{2}\Big{)}^{\max\\{\mathsf{ldeg}_{g}^{\ell}(y),\mathsf{ldeg}_{g}^{\ell}(z),\mathsf{ldeg}_{g}^{\ell}(z^{\prime})\\}}C^{\prime}s\geq\gamma
p^{\Delta-2}3\tilde{\Delta}C^{\prime}s,$

by our choice of $\gamma$. Since either $\tilde{y}=\tilde{z}$ or
$\tilde{y}\tilde{z}\in E(\mathcal{R})$ (and the same holds for
$\tilde{z},\tilde{z}^{\prime}$ and $\tilde{y},\tilde{z}^{\prime}$), we know
that
$F[\mathbf{F}_{\tilde{y}}\cup\mathbf{F}_{\tilde{z}}\cup\mathbf{F}_{\tilde{z}^{\prime}}]$
is a subgraph of some graph in
$\mathcal{D}_{3\tilde{\Delta}C^{\prime}s,p}^{\Delta}(\gamma,\rho,\varepsilon_{j+1},\varepsilon_{j},\mu,\eta)$.
Thus, there are at most $\mu|C_{\ell}(y)|$ vertices $v$ in $C_{\ell}(y)$ such
that $\big{(}N_{F}(v)\cap C_{\ell}(z),N_{F}(v)\cap
C_{\ell}(z^{\prime})\big{)}$ is not $(\varepsilon_{j+1},\rho,p)$-dense.

Suppose now that only one of $z,z^{\prime}$ is in $N_{H}^{\ell+1}(y)$, say
$z\in N_{H}^{\ell+1}(y)$ and $z^{\prime}\notin N_{H}^{\ell+1}(y)$. Then we
have

$\max\\{\mathsf{ldeg}^{\ell}_{g}(y),\mathsf{ldeg}^{\ell}_{g}(z^{\prime})\\}\leq\Delta-1\text{
and }\mathsf{ldeg}_{g}^{\ell}(z)\leq\Delta-2.$

Therefore, analogously to above,

$\min\\{|C_{\ell}(y)|,|C_{\ell}(z^{\prime})|\\}\geq\gamma
p^{\Delta-1}3\tilde{\Delta}C^{\prime}s\text{ and }|C_{\ell}(z)|\geq\gamma
p^{\Delta-2}3\tilde{\Delta}C^{\prime}s.$

Again, since either $\tilde{y}=\tilde{z}$ or $\tilde{y}\tilde{z}\in
E(\mathcal{R})$ (and the same holds for $\tilde{z},\tilde{z}^{\prime}$),
$F[\mathbf{F}_{\tilde{y}}\cup\mathbf{F}_{\tilde{z}}\cup\mathbf{F}_{\tilde{z}^{\prime}}]$
is a subgraph of some graph in
$\mathcal{D}_{3\tilde{\Delta}C^{\prime}s,p}^{\Delta}(\gamma,\rho,\varepsilon_{j+1},\varepsilon_{j},\mu,\eta)$.
Thus, there are at most $\mu|C_{\ell}(y)|$ vertices $v\in C_{\ell}(y)$ such
that $\big{(}N_{F}(v)\cap C_{\ell}(z),C_{\ell}(z^{\prime})\big{)}$ is not
$(\varepsilon_{j+1},\rho,p)$-dense.

Note that in both cases,
$\mathsf{ldeg}^{\ell+1}_{g}(z)+\mathsf{ldeg}^{\ell+1}_{g}(z^{\prime})\geq\mathsf{ldeg}^{\ell}_{g}(z)+\mathsf{ldeg}^{\ell}_{g}(z^{\prime})+1=j+1$,
and so any pair that is $(\varepsilon_{j+1},\rho,p)$-dense is also
$(\varepsilon_{\mathsf{ldeg}^{\ell+1}_{g}(z)+\mathsf{ldeg}^{\ell+1}_{g}(z^{\prime})},\rho,p)$-dense.
For some fixed $v\in C_{\ell}(y)$, set $\hat{C}_{\ell}(z)=C_{\ell}(z)\cap
N_{F}(v)$ if $z\in N_{H}^{\ell+1}(y)$ and $\hat{C}_{\ell}(z)=C_{\ell}(z)$ if
$z\notin N_{H}^{\ell+1}(y)$, and define $\hat{C}_{\ell}(z^{\prime})$ in the
same way.

What we have shown so far is that there are at least

$(1-\Delta\varepsilon_{2\Delta}-\Delta^{2}\mu)|C_{\ell}(y)|$

vertices $v\in C_{\ell}(y)$ with the properties

(b’) $\displaystyle|N_{H}(v)\cap C_{\ell}(z)|\geq\Big{(}\frac{\rho
p}{2}\Big{)}^{\mathsf{ldeg}_{g}^{\ell+1}(z)}|F_{g(z)}|\text{ for each }z\in
N_{H}^{\ell+1}(y)\text{ and}$ (c’)
$\displaystyle\big{(}\hat{C}_{\ell}(z),\hat{C}_{\ell}(z^{\prime})\big{)}\text{
is
}(\varepsilon_{\mathsf{ldeg}^{\ell+1}_{g}(z)+\mathsf{ldeg}^{\ell+1}_{g}(z^{\prime})},\rho,p)\text{-dense
for all edges }\\{z,z^{\prime}\\}\text{ of }H\text{ with }$ $\displaystyle
g(z),g(z^{\prime})>\ell+1\text{ and }\\{z,z^{\prime}\\}\cap
N_{H}^{\ell+1}(y)\neq\varnothing.$

Denote the vertices in $C_{\ell}(y)$ that satisfy (b’) and (c’) by $C(y)$. For
all $y,y^{\prime}\in W_{\ell+1}$, since $g(y)=g(y^{\prime})=\ell$, and by our
choice of the partition $W_{1},\ldots,W_{Q}$, we have that
$\mathsf{ldeg}_{g}^{\ell}(y)=\mathsf{ldeg}_{g}^{\ell}(y^{\prime})$. Let

$k=\mathsf{ldeg}_{g}^{\ell}(y)\text{ for some }y\in W_{\ell+1}$

and note that $0\leq k\leq\Delta$. Then by our choice of $\mu$ and
$\varepsilon_{2\Delta}\leq\varepsilon^{*}$ and from condition (b) of
$(\mathcal{S}_{\ell})$, we have

$|C(y)|\geq(1-\Delta\varepsilon_{2\Delta}-\Delta^{2}\mu)|C_{\ell}(y)|\geq(1-\Delta\varepsilon_{2\Delta}-\Delta^{2}\mu)\Big{(}\frac{\rho
p}{2}\Big{)}^{k}C^{\prime}s\geq\frac{\rho^{k}}{2^{k+1}}p^{k}C^{\prime}s.$

This finishes the first part of our inductive step.

Next, we move to the second part, in which we show that distinct
representatives for the system $\big{(}C(y)\big{)}_{y\in W_{\ell+1}}$ exist.
For this, we use Hall’s condition [9], which tells us that in a bipartite
graph with bipartitions $X$ and $Y$, there is a perfect matching if for every
$X^{\prime}\subseteq X$, it holds that $|N(X)|\geq|X|$. Thus, in our case it
is enough to show that for every $Y\subseteq W_{\ell+1}$, it holds that

$|Y|\leq\Big{|}\bigcup_{y\in Y}C(y)\Big{|}.$

In case $1\leq|Y|\leq\rho^{k}p^{k}C^{\prime}s/2^{k+1}$, the above holds due to
our lower bound on each $|C(y)|$.

Now let $Y\subseteq W_{\ell+1}$ be a set with
$|Y|>\rho^{k}p^{k}C^{\prime}s/2^{k+1}$. As mentioned above, for each $y\in
W_{\ell+1}$, we have $\mathsf{ldeg}_{g}^{\ell}(y)=k$, so there is a $k$-tuple
$K(y)=\\{u_{1}(y),\ldots,u_{k}(y)\\}=N_{H}(y)\setminus N_{H}^{\ell+1}(y)$ of
neighbours of $y$ that are already embedded. Moreover, since we chose the
partition $W_{1},\ldots,W_{Q}$ in such a way that the distance in $H$ between
any two vertices in the same class $W_{i}$ is at least $4$, we have that for
every $y,y^{\prime}\in W_{\ell+1}$, the sets $K(y)$ and $K(y^{\prime})$ are
disjoint. Therefore, the sets of already embedded vertices $\phi_{\ell}(K(y))$
and $\phi_{\ell}(K(y^{\prime}))$ are disjoint too, and so
$\mathcal{F}_{k}=\\{\phi_{\ell}(K(y)):y\in Y\\}\subseteq\binom{V(F)}{k}$ is a
family of disjoint sets of size $k$ in $V(F)$. Furthermore,

$C(y)\subseteq\bigcap_{v\in\phi(K(y))}N_{F}(v).$

Set

$U=\bigcup_{y\in Y}C(y)\subseteq F_{\ell+1},$

and observe that if $F_{\ell+1}\subseteq\mathbf{F}_{\tilde{y}}$ for some
$\tilde{y}\in V(\mathcal{R})$, then $U\subseteq\mathbf{F}_{\tilde{y}}$ and

$\mathcal{F}_{k}\subseteq\binom{(\bigcup^{d_{\tilde{y}}}_{i=1}\mathbf{F}_{p_{i}(\tilde{y})}\dot{\cup}\mathbf{F}_{\tilde{y}})\setminus
U}{k}.$

Assume for contradiction that

$|U|<|Y|=|\mathcal{F}_{k}|.$

Since we conditioned on $\mathscr{G}:=F[\bigcup_{\tilde{n}\in
N_{\mathcal{R}}(\tilde{y})}\mathbf{F}_{\tilde{n}}\dot{\cup}\mathbf{F}_{\tilde{y}}]\in\mathscr{C}^{k}_{(\mathsf{deg}_{\mathcal{R}}(\tilde{y})+1)\tilde{\Delta}C^{\prime}s,p}(\xi)$,
and we have $|\mathcal{F}_{k}|\leq|W_{\ell+1}|\leq
s\leq\xi(\mathsf{deg}_{\mathcal{R}}(\tilde{y})+1)\tilde{\Delta}C^{\prime}s$,
it follows that

$e_{\Gamma(k,\mathscr{G})}(\mathcal{F}_{k},U)\leq
p^{k}|\mathcal{F}_{k}||U|+6\xi(\mathsf{deg}_{\mathcal{R}}(\tilde{y})+1)\tilde{\Delta}C^{\prime}sp^{k}|\mathcal{F}_{k}|.$

From our lower bound on $|C(y)|$ above, it follows that

$e_{\Gamma(k,\mathscr{G})}(\mathcal{F}_{k},U)\geq\frac{\rho^{k}}{2^{k+1}}p^{k}C^{\prime}s|\mathcal{F}_{k}|.$

The last two inequalities together with $C^{\prime}\gg\Delta,\rho^{-1},d$
imply that

$\Big{|}\bigcup_{y\in
Y}C(y)\Big{|}=|U|\geq\Big{(}\frac{\rho^{k}}{2^{k+1}}-6(\mathsf{deg}_{\mathcal{R}}(\tilde{y})+1)\xi\tilde{\Delta}\Big{)}C^{\prime}s\geq
s\geq|W_{\ell+1}|\geq|Y|,$

which contradicts our assumption that $|U|<|Y|=|\mathcal{F}_{k}|$. This shows
that Hall’s condition $|Y|\leq|U|$ holds, as desired. Therefore, there is a
system of representatives for $\big{(}C(y)\big{)}_{y\in W_{\ell+1}}$. In other
words, there is an injective function $\psi:W_{\ell+1}\rightarrow\cup_{y\in
W_{\ell+1}}C(y)$ such that $\psi(y)\in C(y)$ for each $y\in W_{\ell+1}$.

We can now extend $\phi_{\ell}$ to get $\phi_{\ell+1}$ and define
$C_{\ell+1}(z)$ for $z\in\cup_{j=\ell+2}^{Q}$. Firstly, let

$\phi_{\ell+1}(w)=\begin{cases}\phi_{\ell}(w),&\text{if
}w\in\cup_{j=1}^{\ell}W_{j},\\\ \psi(w),&\text{if }w\in
W_{\ell+1}.\end{cases}$

Since all pairs of vertices in $W_{\ell+1}$ are at distance at least $4$, each
$z\in\cup_{j=\ell+2}^{Q}W_{j}$ has no more than one neighbour in $W_{\ell+1}$.
Thus, for each such $z\in\cup_{j=\ell+2}^{Q}W_{j}$ we can set

$C_{\ell+1}(z)=\begin{cases}C_{\ell}(z),&\text{if }N_{H}(z)\cap
W_{\ell+1}=\varnothing,\\\ C_{\ell}(z)\cap N_{F}(\phi_{\ell+1}(y)),&\text{if
}N_{H}(z)\cap W_{\ell+1}=\\{y\\}.\end{cases}$

We now verify that $\phi_{\ell+1}$ and $C_{\ell+1}(z)$ for each
$z\in\cup_{j=\ell+2}^{Q}W_{j}$ satisfy $(\mathcal{S}_{\ell+1})$.

From property (a) of $(\mathcal{S}_{\ell})$ together with $\phi_{\ell+1}(y)\in
C(y)\subseteq C_{\ell}(y)$ for every $y\in W_{\ell+1}$ and the fact that
$\psi$ is injective, it follows that $\phi_{\ell+1}$ is a partial embedding of
$H[\bigcup_{j=1}^{\ell+1}W_{j}]$ into $F[\bigcup_{j=1}^{\ell+1}F_{j}]$.

We now check that parts (a) and (b) of $(\mathcal{S}_{\ell+1})$ hold. Fix some
$z\in\bigcup_{j=\ell+2}^{Q}W_{j}$. In case $N_{H}(z)\cap
W_{\ell+1}=\varnothing$, we have $C_{\ell+1}(z)=C_{\ell}(z)$ and
$\mathsf{ldeg}_{g}^{\ell+1}(z)=\mathsf{ldeg}_{g}^{\ell}(z)$, so (a) and (b) of
$(\mathcal{S}_{\ell+1})$ are satisfied for that $z$. Now suppose $N_{H}(z)\cap
W_{\ell+1}=\\{y\\}$ (recall that this is the only other possible case). Since
we defined $C_{\ell+1}(z)=C_{\ell}(z)\cap N_{F}(\phi_{\ell+1}(y))$, property
(a) of $(\mathcal{S}_{\ell+1})$ holds for $z$ in this case. Furthermore, by
our choice $\phi_{\ell+1}(y)\in C(y)$ and by (b’), it follows that property
(b) of $(\mathcal{S}_{\ell+1})$ is satisfied.

Lastly, we check property (c) of $(\mathcal{S}_{\ell+1})$. Fix an edge
$zz^{\prime}$ of $H$ such that $z,z^{\prime}\in\bigcup_{j=\ell+2}^{Q}W_{j}$.
There are three cases to consider, based on the size of $N_{H}(z)\cap
W_{\ell+1}$ and $N_{H}(z^{\prime})\cap W_{\ell+1}$ (recall that each of them
has size either $0$ or $1$). Suppose first $N_{H}(z)\cap
W_{\ell+1}=\varnothing$ and $N_{H}(z^{\prime})\cap W_{\ell+1}=\varnothing$.
Then we have $\mathsf{ldeg}^{\ell}_{g}(z)=\mathsf{ldeg}^{\ell+1}_{g}(z)$ and
$\mathsf{ldeg}^{\ell}_{g}(z^{\prime})=\mathsf{ldeg}^{\ell+1}_{g}(z^{\prime})$,
as well as $C_{\ell}(z)=C_{\ell+1}(z)$ and
$C_{\ell}(z^{\prime})=C_{\ell}(z^{\prime})$, so part (c) of
$(\mathcal{S}_{\ell+1})$ follows directly from part (c) of
$(\mathcal{S}_{\ell})$. Next, suppose $N_{H}(z)\cap W_{\ell+1}=\\{y\\}$ and
$N_{H}(z^{\prime})\cap W_{\ell+1}=\varnothing$. Then property (c’) together
with the definition of $C_{\ell+1}(z)$ and $C_{\ell+1}(z^{\prime})$ imply part
(c) of $(\mathcal{S}_{\ell+1})$. Finally, suppose $N_{H}(z)\cap
W_{\ell+1}=\\{y\\}$ and $N_{H}(z^{\prime})\cap W_{\ell+1}=\\{y^{\prime}\\}$.
Then it must be the case that $y=y^{\prime}$, since otherwise $y$ and
$y^{\prime}$ would be two distinct vertices in $W_{\ell+1}$ connected by a
path of length $3$ in $H$, namely the path $yzz^{\prime}y^{\prime}$, and this
is impossible by our choice of $W_{1},\ldots,W_{Q}$. Then in this case also,
part (c) of $(\mathcal{S}_{\ell+1})$ follows from (c’) and our choice of
$C_{\ell+1}(z)$ and $C_{\ell+1}(z^{\prime})$.

We have shown that (a), (b), and (c) of $(\mathcal{S}_{\ell+1})$ hold. This
finishes the induction step and the proof of Lemma 3.7. ∎

## References

  * [1] Peter Allen and Julia Böttcher.  Partition universality for graphs of bounded degeneracy and degree.  arXiv preprint arXiv:2211.15819, 2022.
  * [2] Noga Alon, Paul D. Seymour, and Robin Thomas.  A separator theorem for nonplanar graphs.  Journal of the American Mathematical Society, 3(4):801–808, 1990\.
  * [3] József Beck.  On size Ramsey number of paths, trees, and circuits. I.  Journal of Graph Theory, 7(1):115–129, 1983.
  * [4] 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\.
  * [5] Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, and Arnold L. Rosenberg.  Universal graphs for bounded-degree trees and planar graphs.  SIAM Journal on Discrete Mathematics, 2(2):145–155, 1989.
  * [6] Fan R.K. Chung.  Separator theorems and their applications.  Paths, Flows, and VLSI-Layout, 1990.
  * [7] Václav Chvatál, Vojtech Rödl, Endre Szemerédi, and William Thomas Trotter Jr.  The Ramsey number of a graph with bounded maximum degree.  Journal of Combinatorial Theory, Series B, 34(3):239–243, 1983\.
  * [8] David Conlon, Rajko Nenadov, and Miloš Trujić.  On the size-Ramsey number of grids.  Combinatorics, Probability and Computing, pages 1–7, 2022.
  * [9] Reinhard Diestel.  Matching Covering and Packing, pages 35–58.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2017.
  * [10] Guoli Ding and Bogdan Oporowski.  Some results on tree decompositions of graphs.  Journal of Graph Theory, 20(4):481–499, 1995.
  * [11] Marc Distel and David R Wood.  Tree-partitions with bounded degree trees.  arXiv preprint arXiv:2210.12577, 2022.
  * [12] Nemanja Draganić, Michael Krivelevich, and Rajko Nenadov.  The size-Ramsey number of short subdivisions.  Random Structures & Algorithms, 59(1):68–78, 2021.
  * [13] Nemanja Draganić, Michael Krivelevich, and Rajko Nenadov.  Rolling backwards can move you forward: on embedding problems in sparse expanders.  Trans. Am. Math. Soc., 375(7):5195–5216, 2022.
  * [14] Nemanja Draganić and Kalina Petrova.  Size-Ramsey numbers of graphs with maximum degree three.  arXiv preprint arXiv:2207.05048, 2022.
  * [15] Zdeněk Dvořák and Sergey Norin.  Treewidth of graphs with balanced separations.  Journal of Combinatorial Theory, Series B, 137:137–144, 2019.
  * [16] Paul Erdős, Ralph J. Faudrée, Cecil C. Rousseau, and Richard H. Schelp.  The size Ramsey number.  Period. Math. Hungar., 9(1-2):145–161, 1978.
  * [17] Joel Friedman and Nicholas Pippenger.  Expanding graphs contain all small trees.  Combinatorica, 7:71–76, 1987.
  * [18] Stefanie Gerke, Yoshiharu Kohayakawa, Vojtěch Rödl, and Angelika Steger.  Small subsets inherit sparse $\varepsilon$-regularity.  Journal of Combinatorial Theory, Series B, 97(1):34–56, 2007.
  * [19] Stefanie Gerke and Angelika Steger.  The sparse regularity lemma and its applications.  In BCC, pages 227–258, 2005.
  * [20] Charles H. Goldberg and Douglas B. West.  Bisection of circle colorings.  SIAM Journal on Algebraic Discrete Methods, 6(1):93–106, 1985.
  * [21] Nina Kamčev, Anita Liebenau, David R. Wood, and Liana Yepremyan.  The size Ramsey number of graphs with bounded treewidth.  SIAM Journal on Discrete Mathematics, 35(1):281–293, 2021.
  * [22] Yoshiharu Kohayakawa, Troy Retter, and Vojtěch Rödl.  The size Ramsey number of short subdivisions of bounded degree graphs.  Random Structures & Algorithms, 54(2):304–339, 2019.
  * [23] 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.
  * [24] János Komlós, Ali Shokoufandeh, Miklós Simonovits, and Endre Szemerédi.  The regularity lemma and its applications in graph theory.  Theoretical Aspects of Computer Science: Advanced Lectures, pages 84–112, 2002.
  * [25] Choongbum Lee.  Ramsey numbers of degenerate graphs.  Annals of Mathematics, 185(3):791–829, 2017.
  * [26] Frank P. Ramsey.  On a problem of formal logic.  Proc. London Math. Soc, 30(4):264–286, 1929.
  * [27] Neil Robertson and Paul D. Seymour.  Graph minors. II. Algorithmic aspects of tree-width.  Journal of Algorithms, 7(3):309–322, 1986.
  * [28] Vojtěch Rödl and Endre Szemerédi.  On size Ramsey numbers of graphs with bounded degree.  Combinatorica, 20:257–262, 02 2000.
  * [29] Konstantin Tikhomirov.  On bounded degree graphs with large size-Ramsey numbers.  arXiv preprint arXiv:2210.05818, 2022.
  * [30] David R. Wood.  On tree-partition-width.  European Journal of Combinatorics, 30(5):1245–1253, 2009.
  * [31] David R. Wood.  Presentation at the open problem session of the _Third Southwestern German Workshop on Graph Theory_ , University of Heidelberg, 2022\.