\floatsetup

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: {nemanja.draganic,david.munhacanascorreia}@math.ethz.ch. 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: {marc.kaufmann,kalina.petrova,raphaelmario.steiner}@inf.ethz.ch. David Munhá Correia¹¹footnotemark: 1 Kalina Petrova²²footnotemark: 2 Raphael Steiner²²footnotemark: 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 have¹¹1We 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.

(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$ .
(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.²²2The 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.
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.
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)

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.