2. Preliminaries

Throughout the paper $\log$ denotes the natural logarithm. We assume that the order n of all graphs tends to infinity and therefore is sufficiently large whenever necessary. Our graph-theoretic notation is standard. In particular, given a graph G its vertex set is denoted by V(G) and its edge set by E(G). Let $A,B\subseteq V$ be disjoint vertex sets. We denote the number of edges between A and B by e(A,B). For a vertex $v \in V(G)$ we write $N_G(v)$ for the neighbourhood of v in G and $N_G(v,A)\;:\!=\; N_G(v) \cap A$ for the neighbourhood of v restricted to A. Finally, let $\deg_G(v) \;:\!=\; |N_G(v)|$ be the degree of v in G. For the sake of readability, we do not make any effort to optimise the constants in our theorems and proofs.

2.1. The sparse regularity method

Now we introduce some definitions and results of the regularity method as well as related tools that are essential in our proofs. In particular, we state a minimum degree version of the sparse regularity lemma (Lemma 9) and the sparse blow-up lemma (Lemma 13). Both lemmas use the concept of regular pairs. Let $G= (V,E)$ be a graph, $\varepsilon, d >0$ , and $p \in (0,1]$ . Moreover, let $X,Y \subseteq V$ be two disjoint nonempty sets. The p-density of the pair (X,Y) is defined as

\begin{equation*}d_{G,p}(X,Y) \;:\!=\; \frac{e_G(X,Y)}{p|X||Y|}\,.\end{equation*}

We now define regular, and super-regular, pairs. Note that what we are calling ‘regulaR ^′ is sometimes referred to as ‘lower-regulaR ^′ by contrast with ‘fully-regulaR ^′ (sometimes just called ‘regulaR ^′) pairs in which an upper bound on p-densities is also imposed. It is immediate from the definition of the latter that a fully-regular pair is also lower-regular, with the same parameters; the converse is false.

Definition 6 (regular pairs, fully-regular pairs, super-regular pairs). The pair (X,Y) is called $(\varepsilon,d,p)_G$ -regular if for every $X'\subseteq X$ and $Y'\subseteq Y$ with $|X'|\geq \varepsilon|X|$ and $|Y'|\geq \varepsilon |Y|$ we have $d_{G,p}(X',Y') \geq d- \varepsilon$ . It is called $(\varepsilon,d,p)_G$ -regular if there is some $d'\ge d$ such that for every $X'\subseteq X$ and $Y'\subseteq Y$ with $|X'|\geq \varepsilon|X|$ and $|Y'|\geq \varepsilon |Y|$ we have $\big|d_{G,p}(X',Y')-d'\big| \le \varepsilon$ .

If (X,Y) is $(\varepsilon,d,p)_G$ -regular, and in addition we have

\begin{align*} |N_G(x,Y)| &\geq (d-\varepsilon)\max\big(p|Y|,\deg_\Gamma(x,Y)/2\big)\quad\text{and}\\ |N_G(y,X)| &\geq (d-\varepsilon)\max\big(p|X|,\deg_\Gamma(y,X)/2\big)\end{align*}

for every $x \in X$ and $y \in Y$ , then the pair (X,Y) is called $(\varepsilon,d,p)_G$ -super-regular.

A direct consequence of the definition of $(\varepsilon,d,p)$ -regular pairs is the following proposition about the sizes of neighbourhoods in regular pairs.

Proposition 7 Let (X,Y) be $(\varepsilon, d,p)$ -regular. Then there are less than $\varepsilon |X|$ vertices $x\in X$ with $|N(x,Y)| < (d-\varepsilon)p|Y|$ .

The following proposition is another immediate consequence of Definition 6. It states that an $(\varepsilon,d,p)$ -regular pair is still regular if only a linear fraction of its vertices is removed.

Proposition 8 Let (X,Y) be $(\varepsilon, d,p)$ -regular and suppose $X'\subseteq X$ and $Y' \subseteq Y$ satisfy $|X'| \geq \mu |X|$ and $|Y'|\geq \nu |Y|$ with some $\mu, \nu >0$ . Then (X’,Y’) is $(\frac{\varepsilon}{\min\{\mu,\nu\}},d,p)$ -regular.

In order to state the sparse regularity lemma, we need some more definitions. A partition ${\mathcal V} = \{V_i\}_{i\in\{0,\ldots,r\}}$ of the vertex set of G is called an $(\varepsilon,p)_G$ -regular partition of V(G) if $|V_0|\leq \varepsilon |V(G)|$ and $(V_i,V_{i^{\prime}})$ forms an $(\varepsilon,0,p)_G$ -fully-regular pair for all but at most $\varepsilon\binom{r}{2}$ pairs $\{i,i^{\prime}\}\in \binom{[r]}{2}$ . It is called an equipartition if $|V_i| = |V_{i^{\prime}}|$ for every $i,i^{\prime}\in[r]$ . The partition ${\mathcal V}$ (or the pair $(G,{\mathcal V})$ ) is called $(\varepsilon,d,p)_G$ -regular on a graph R with vertex set [r] if $(V_i, V_{i^{\prime}})$ is $(\varepsilon,d,p)_G$ -regular for every $\{i,i^{\prime}\}\in E(R)$ . The graph R is referred to as the $(\varepsilon,d,p)_G$ -reduced graph of ${\mathcal V}$ , the partition classes $V_i$ with $i \in [r]$ as clusters and $V_0$ as the exceptional set. We also say that ${\mathcal V}$ (or the pair $(G,{\mathcal V})$ ) is $(\varepsilon,d,p)_G$ -super-regular on a graph R ^′ with vertex set [r] if $(V_i, V_{i^{\prime}})$ is $(\varepsilon,d,p)_G$ -super-regular for every $\{i,i^{\prime}\}\in E(R')$ .

Analogously to Szemerédi’s regularity lemma for dense graphs, the sparse regularity lemma, proved by Kohayakawa [Reference Kohayakawa10], Kohayakawa and Rödl [Reference Kohayakawa and Rödl11] and Scott [Reference Scott16], asserts the existence of an $(\varepsilon,p)$ -regular partition of constant size of any sparse graph. We state a minimum degree version of this lemma, whose proof can be found in the appendix of [Reference Allen, Böttcher, Ehrenmüller and Taraz1].

Lemma 9 (Minimum degree version of the sparse regularity lemma). For each $\varepsilon >0$ , each $\alpha \in [0,1]$ , and $r_0\geq 1$ there exists $r_1\geq 1$ with the following property. For any $d\in[0,1]$ , any $p>0$ , and any n-vertex graph G with minimum degree $\alpha p n$ such that for any disjoint $X,Y\subset V(G)$ with $|X|,|Y|\ge\tfrac{\varepsilon n}{r_1}$ we have $e(X,Y)\le \big(1+\tfrac{1}{1000}\varepsilon^2\big)p|X||Y|$ , there is an $(\varepsilon,p)_G$ -regular equipartition of V(G) with $(\varepsilon,d,p)_G$ -reduced graph R satisfying $\delta(R) \geq (\alpha-d-\varepsilon)|V(R)|$ and $r_0 \leq|V(R)| \leq r_1$ .

We will need the following version of the sparse regularity lemma (see e.g. [Reference Allen, Böttcher, Ehrenmüller and Taraz1, Lemma 29] for a proof), allowing for a partition equitably refining an initial partition with parts of very different sizes. Given a partition $ V(G)=V_1\,{\cup\mkern-12.5mu\cdot\mkern5mu} \cdots {\cup\mkern-12.5mu\cdot\mkern5mu}\,V_s $ , we say a partition $\{V_{i,j}\}_{i\in[s],j\in[t]}$ is an equitable $(\varepsilon,p)$ -regular refinement of $\{V_i\}_{i\in[s]}$ if $|V_{i,j}|=|V_{i,j^{\prime}}|\pm 1$ for each $i\in[s]$ and $j,j^{\prime}\in[t]$ , and there are at most $\varepsilon s^2t^2$ pairs $(V_{i,j},V_{i^{\prime},\kern0.5pt j^{\prime}})$ which are not $(\varepsilon,0,p)$ -fully-regular.

Lemma 10 (Refining version of the sparse regularity lemma) For each $\varepsilon>0$ and $s\in\mathbb{N}$ there exists $t_1\geq 1$ such that the following holds. Given any graph G, suppose $V_1\,\cup\mkern-12.5mu\cdot\mkern5mu \cdots \cup\mkern-12.5mu\cdot\mkern5mu\,V_s$ is a partition of V(G). Suppose that $e(V_i)\le 3p|V_i|^2$ for each $i\in[s]$ , and $e(V_i,V_{i^{\prime}})\le 2p|V_i||V_{i^{\prime}}|$ for each $i\neq i^{\prime}\in[s]$ . Then there exist sets $V_{i,0}\subset V_i$ for each $i\in[s]$ with $|V_{i,0}|<\varepsilon|V_i|$ , and an equitable $(\varepsilon,p)$ -regular refinement $\{V_{i,j}\}_{i\in[s],j\in[t]}$ of $\{V_i\setminus V_{i,0}\}_{i\in[s]}$ for some $t\le t_1$ .

A key ingredient in the proof of our main theorem is the so-called sparse blow-up lemma established in [Reference Allen, Böttcher, Hàn, Kohayakawa and Person2]. Given a subgraph $G \subseteq \Gamma =G(n,p)$ with $p \gg (\log n/n)^{1/\Delta}$ and an n-vertex graph H with maximum degree at most $\Delta$ with vertex partitions ${\mathcal V}$ and ${\mathcal W}$ , respectively, the sparse blow-up lemma guarantees under certain conditions a spanning embedding of H in G which respects the given partitions. In order to state this lemma we need some definitions.

Let G and H be graphs on n vertices with partitions ${\mathcal V}=\{V_i\}_{i\in[r]}$ of V(G) and ${\mathcal W}=\{W_i\}_{i\in[r]}$ of V(H). We say that ${\mathcal V}$ and ${\mathcal W}$ are size-compatible if $|V_i|=|W_i|$ for all $i\in[r]$ . If there exists an integer $m \geq 1$ such that $m \leq|V_i| \leq \kappa m$ for every $i\in [r]$ , then we say that $(G,{\mathcal V})$ is $\kappa$ -balanced. Given a graph R on r vertices, we call $(H,{\mathcal W})$ an R-partition if for every edge $\{x,y\}\in E(H)$ with $x\in W_i$ and $y\in W_{i^{\prime}}$ we have $\{i,i^{\prime}\}\in E(R)$ . The following definition allows for image restrictions in the sparse blow-up lemma.

Definition 11 (Restriction pair). Let $\varepsilon,d>0$ , $p \in [0,1]$ , and let R be a graph on r vertices. Furthermore, let G be a (not necessarily spanning) subgraph of $\Gamma = G(n,p)$ and let H be a graph given with vertex partitions ${\mathcal V}= \{V_i\}_{i\in[r]}$ and ${\mathcal W} = \{W_i\}_{i\in[r]}$ , respectively, such that $(G,{\mathcal V})$ and $(H,{\mathcal W})$ are size-compatible R-partitions. Let ${\mathcal I}=\{I_x\}_{x\in V(H)}$ be a collection of subsets of V(G), called image restrictions, and ${\mathcal J}=\{J_x\}_{x\in V(H)}$ be a collection of subsets of $V(\Gamma)\setminus V(G)$ , called restricting vertices. For each $i\in [r]$ we define $R_i\subseteq W_i$ to be the set of all vertices $x \in W_i$ for which $I_x \neq V_i$ . We say that ${\mathcal I}$ and ${\mathcal J}$ are a $(\rho,\zeta,\Delta,\Delta_J)$ -restriction pair if the following properties hold for each $i\in[r]$ and $x\in W_i$ .

1. (RP1) We have $|R_i|\leq\rho|W_i|$ .

2. (RP2) If $x\in R_i$ , then $I_x\subseteq \bigcap_{u\in J_x} N_\Gamma(u, V_i)$ is of size at least $\zeta(dp)^{|J_x|}|V_i|$ .

3. (RP3) If $x\in R_i$ , then $|J_x|+\deg_H(x)\leq\Delta$ and if $x\in W_i\setminus R_i$ , then $J_x=\varnothing$ .

4. (RP4) Each vertex in V(G) appears in at most $\Delta_J$ of the sets of ${\mathcal J}$ .

5. (RP5) We have $\big|\bigcap_{u\in J_x} N_\Gamma(u, V_i)\big| = (p\pm\varepsilon p)^{|J_x|}|V_i|$ .

6. (RP6) If $x\in R_i$ , for each $xy\in E(H)$ with $y\in W_j$ ,

   \begin{equation*}\text{the pair }\quad\Big( V_i \cap \bigcap_{u\in J_x}N_\Gamma(u), V_j \cap \bigcap_{v\in J_y}N_\Gamma(v)\Big)\quad\text{ is $(\varepsilon,d,p)_G$-regular.}\end{equation*}

The sparse blow-up lemma needs not all pairs in the reduced graph R to be super-regular, but only those in a subgraph R ^′ of R. This, however, is only possible if a good proportion of H is embedded to the pairs in R ^′. The following definition of buffer-sets makes this requirement precise. Moreover, we need certain regularity inheritance properties for the pairs in R ^′.

Definition 12 ( $(\vartheta, R')$ -buffer, regularity inheritance) Let R and R ^′ be graphs on vertex set [r] with $R'\subset R$ . Suppose that $(H,{\mathcal W})$ is an R-partition and that $(G,{\mathcal V})$ is a size-compatible $(\varepsilon,d,p)_G$ -regular partition with reduced graph R. We say that the family $\widetilde{\mathcal{W}}=\{\widetilde{W}_i\}_{i\in[r]}$ of subsets $\widetilde{W}_i\subseteq W_i$ is an $(\vartheta,R')$ -buffer for H if

1. i. $|\widetilde{W}_i|\geq\vartheta |W_i|$ for all $i\in[r]$ , and

2. ii. for each $i\in[r]$ and each $x\in\widetilde{W}_i$ , the first and second neighbourhood of x go along R ^′, i.e., for each $\{x,y\},\{y,z\}\in E(H)$ with $y\in W_j$ and $z\in W_k$ we have $\{i,j\}\in E(R')$ and $\{j,k\}\in E(R')$ .

We say $(G,{\mathcal V})$ has one-sided inheritance on R ^′ if for every $\{i,j\}, \{j,k\}\in E(R')$ and every $v\in V_i$ the pair $\big(N_\Gamma(v, V_j),V_k\big)$ is $(\varepsilon,d,p)_G$ -regular. We say $(G,{\mathcal V})$ has two-sided inheritance on R ^′ for $\widetilde{\mathcal{W}}$ if for each $i,j,k \in V(R')$ such that there is a triangle $x_ix_jx_k$ in H with $x_i\in \widetilde{W}_i$ , $x_j\in W_j$ , and $x_k\in W_k$ the following holds. For every $v\in V_i$ the pair $\big(N_\Gamma(v, V_j),N_\Gamma(v, V_k)\big)$ is $(\varepsilon,d,p)_G$ -regular.

Now we can finally state the sparse blow-up lemma.

Lemma 13 (Sparse blow-up lemma [Reference Allen, Böttcher, Hàn, Kohayakawa and Person2, Lemma 1.21]). For each $\Delta$ , $\Delta_{R'}$ , $\Delta_J$ , $\vartheta,\zeta, d>0$ , $\kappa>1$ there exist $\varepsilon_{{BL}},\rho>0$ such that for all $r_1$ there is a $C_{BL}\;such\;that\;for\;p \geq C_{BL}(\log n/n)^{1/\Delta}$ the random graph $\Gamma=G_{n,p}$ asymptotically almost surely satisfies the following.

Let R be a graph on $r\le r_1$ vertices and let $R'\subseteq R$ be a spanning subgraph with $\Delta(R')\leq \Delta_{R'}$ . Let H and $G\subseteq \Gamma$ be graphs given with $\kappa$ -balanced, size-compatible vertex partitions ${\mathcal W}=\{W_i\}_{i\in[r]}$ and ${\mathcal V}=\{V_i\}_{i\in[r]}$ with parts of size at least $m\geq n/(\kappa r_1)$ . Let ${\mathcal I}=\{I_x\}_{x\in V(H)}$ be a family of image restrictions, and ${\mathcal J}=\{J_x\}_{x\in V(H)}$ be a family of restricting vertices. Suppose that

1. (BUL1) $\Delta(H)\leq \Delta$ , for every edge $\{x,y\}\in E(H)$ with $x\in W_i$ and $y\in W_j$ we have $\{i,j\}\in E(R)$ and $\widetilde{\mathcal{W}}=\{\widetilde{W}_i\}_{i\in[r]}$ is an $(\vartheta,R')$ -buffer for H,

2. (BUL2) $(G,{\mathcal V})$ is $(\varepsilon_{BL},d,p)_G$ -regular on R, $(\varepsilon_{{BL}},d,p)_G$ -super-regular on R ^′, has one-sided inheritance on R ^′, and two-sided inheritance on R ^′ for $\widetilde{\mathcal{W}}$ ,

3. (BUL3) ${\mathcal I}$ and ${\mathcal J}$ form a $(\rho,\zeta,\Delta,\Delta_J)$ -restriction pair.

Then there is an embedding $\phi\colon V(H)\to V(G)$ such that $\phi(x)\in I_x$ for each $x\in H$ .

Observe that in the blow-up lemma for dense graphs, proved by Komlós et al. [Reference Komlós, Sárközy and Szemerédi12], one does not need to explicitly ask for one- and two-sided inheritance properties since they are always fulfilled by dense regular partitions. This is, however, not true in general in the sparse setting. The following two lemmas will be very useful whenever we need to redistribute vertex partitions in order to achieve some regularity inheritance properties.

Lemma 14 (One-sided regularity inheritance [Reference Allen, Böttcher, Hàn, Kohayakawa and Person2]). For each $\varepsilon_{{OSRIL}}, {\alpha_{{OSRIL}}} >0$ there exist $\varepsilon_0 >0$ and $C >0$ such that for any $0 < \varepsilon < \varepsilon_0$ and $0 < p <1$ asymptotically almost surely $\Gamma=G(n,p)$ has the following property. For any disjoint sets X and Y in $V(\Gamma)$ with $|X|\geq C\max\big(p^{-2}, p^{-1} \log n\big)$ and $|Y|\geq C p^{-1} \log n$ , and any subgraph G of $\Gamma[X,Y]$ which is $(\varepsilon, {\alpha_{{OSRIL}}},p)_G$ -regular, there are at most $C p^{-1}\log (en/|X|)$ vertices $z \in V(\Gamma)$ such that $(X \cap N_{\Gamma}(z),Y)$ is not $ (\varepsilon_{{OSRIL}},\alpha_{{OSRIL}},p)_G $ -regular.

Lemma 15 (Two-sided regularity inheritance [Reference Allen, Böttcher, Hàn, Kohayakawa and Person2]). For each ${\varepsilon_{TSRIL}},{\alpha_{TSRIL}}>0$ there exist $\varepsilon_0>0$ and $C >0$ such that for any $0<\varepsilon<\varepsilon_0$ and $0<p<1$ , asymptotically almost surely $\Gamma=G_{n,p}$ has the following property. For any disjoint sets X and Y in $V(\Gamma)$ with $|X|,|Y|\ge C\max\{p^{-2},p^{-1}\log n\}$ , and any subgraph G of $\Gamma[X,Y]$ which is $(\varepsilon,{\alpha_{{TSRIL}}},p)_G$ -regular, there are at most $C\max\{p^{-2},p^{-1}\log (en/|X|)\}$ vertices $z \in V(\Gamma)$ such that $\big(X\cap N_\Gamma(z),Y\cap N_\Gamma(z)\big)$ is not $(\varepsilon_{{TSRIL}},{\alpha_{{TSRIL}}},p)_G$ -regular.

Finally, we need a statement about random subpairs of regular pairs (which is used to prove Lemma 15).

Corollary 16 ([7, Corollary 3.8]) For any d, $\beta$ , $\varepsilon'>0$ there exist $\varepsilon_0>0$ and C such that for any $0<\varepsilon<\varepsilon_0$ and $0<p<1$ , if (X,Y) is an $(\varepsilon,d,p)$ -regular pair in a graph G, then the number of pairs $X'\subseteq X$ and $Y'\subseteq Y$ with $|X'|=w_1\ge C/p$ and $|Y'|=w_2\ge C/p$ such that (X^′,Y^′) is an $(\varepsilon',d,p)$ -regular pair in G is at least $(1-\beta^{\min(w_1,w_2)})\binom{|X|}{w_1}\binom{|Y|}{w_2}$ .

2.2. Concentration inequalities

We close this section with two of Chernoff’s bounds for random variables that follow a binomial (Theorem 18) and a hypergeometric distribution (Theorem 19), respectively, and the following useful observation. Roughly speaking, it states that a.a.s. nearly all vertices in G(n,p) have approximately the expected number of neighbours within large enough subsets (for a proof see e.g. [Reference Allen, Böttcher, Ehrenmüller and Taraz1, Proposition 18]).

Proposition 17 For each $\varepsilon>0$ there exists a constant $C >0$ such that for every $0<p<1$ asymptotically almost surely $\Gamma=G(n,p)$ has the property that for any sets $X,Y\subset V(\Gamma)$ with $|X|\ge {Cp}^{-1}\log n$ and $|Y|\ge Cp^{-1}\log (en/|X|)$ the following holds.

1. a. If X and Y are disjoint, then $e(X,Y)=(1\pm\varepsilon)p|X||Y|$ .

2. b. We have $e(X)\le 2p|X|^2$ .

3. c. At most $C p^{-1} \log (en/|X|)$ vertices $v \in V(\Gamma)$ satisfy $\big||N_{\Gamma}(v,X)| - p |X|\big| > \varepsilon p |X|$ .

We use the following version of Chernoff’s Inequalities (see e.g. [Reference Janson, Łuczak and Rucinski9, Chapter 2] for a proof).

Theorem 18 (Chernoff’s Inequality, [Reference Janson, Łuczak and Rucinski9]). Let X be a random variable which is the sum of independent Bernoulli random variables. Then we have for $\varepsilon\leq 3/2$

\begin{equation*}\mathbb{P}\big[|X-\mathbb{E}[X]| > \varepsilon \mathbb{E}[X]\big] < 2e^{-\varepsilon^2\mathbb{E}[X]/3}\,.\end{equation*}

Furthermore, if $t\ge 6\mathbb{E}[X]$ then we have

\begin{equation*}\mathbb{P}\big[X\ge\mathbb{E}[X]+t\big]\le e^{-t}\,.\end{equation*}

Finally, let N, m, and s be positive integers and let S and $S' \subseteq S$ be two sets with $|S| = N$ and $|S'| = m$ . The hypergeometric distribution is the distribution of the random variable X that is defined by drawing s elements of S without replacement and counting how many of them belong to S ^′. It can be shown that Theorem 18 still holds in the case of hypergeometric distributions (see e.g. [Reference Janson, Łuczak and Rucinski9], Chapter 2 for a proof) with $\mathbb{E}[X]= ms/N$ .

Theorem 19 (Hypergeometric inequality, [Reference Janson, Łuczak and Rucinski9]). Let X be a random variable is hypergeometrically distributed with parameters N, m, and s. Then for any $\varepsilon>0$ and $t\ge\varepsilon ms/N$ we have

\begin{equation*}\mathbb{P}\big[|X - ms/N| > t \big] < 2e^{-\varepsilon^2t/3}\,.\end{equation*}

We require the following technical lemma, which is a consequence of the hypergeometric inequality stated in Theorem 19.

Lemma 20 For each $\varepsilon^+_0,d^+>0$ there exists $\varepsilon^+>0$ , and for each $\varepsilon,d>0$ there exists $\varepsilon^->0,$ such that for each $\eta>0$ and $\Delta$ there exists C such that the following holds for each $p>0$ .

Let $W\subset [n]$ , let $t\le 100n^{\Delta+1}$ , and let $T_1,\ldots,T_t$ be subsets of W. Let G be a graph on W. For each $i\in[t]$ let $(X_i,Y_i)$ be a pair which is either $(\varepsilon^+,d^+,p)_G$ -regular, or $(\varepsilon^-,d,p)_G$ -regular (respectively), and which satisfies $m|X_i|/|W|,m|Y_i|/|W|\ge 2Cp^{-1}\log n$ .

For each $m\le |W|$ there is a set $S\subset W$ of size m such that for each $i\in[t]$

\begin{equation*}|T_i\cap S|=\tfrac{m}{|W|}|T_i|\pm \big(\eta|T_i|+C\log n\big)\,,\end{equation*}

and the pair $\big(X_i\cap S,Y_i\cap S\big)$ is $\big(\varepsilon^+_0,d^+,p\big)$ -regular, or $(\varepsilon,d,p)$ -regular (respectively).

Proof. Given $\varepsilon^+_0,d^+$ , let $\varepsilon^+$ be returned by Corollary 16 for input $d^+$ , $\beta=\tfrac12$ and $\varepsilon^+_0$ . Given $\varepsilon,d$ , let $\varepsilon^-$ be returned by Corollary 16 for input d, $\beta=\tfrac12$ and $\varepsilon$ . Let $C\ge 30\eta^{-2}\Delta$ be large enough for these applications of Corollary 16.

Observe that for each i, the size of $T_i\cap S$ is hypergeometrically distributed. By Theorem 19, for each i we have

\begin{equation*}\mathbb{P}\big[|T_i\cap S|\neq \tfrac{m}{|W|}|T_i|\pm \big(\eta|T_i|+C\log n\big)\big]<2e^{-\eta^2C\log n/3}<\frac{2}{n^{2+\Delta}}\,,\end{equation*}

so taking the union bound over all $i\in[t]$ we conclude that the probability of failure is at most $2t/n^{2+\Delta}\le 200/n\to 0$ as $n\to\infty$ , as desired.

To obtain the second property, observe that Theorem 19 also implies that we have $|X_i\cap S|,|Y_i\cap S|\ge Cp^{-1}\log n$ for each $i\in[t]$ with probability tending to one as $n\to\infty$ . Conditioning on the size of $|X_i\cap S|$ , the set $X_i\cap S$ is a uniformly distributed subset of $X_i$ of size $|X_i\cap S|$ , and the same applies to $Y_i\cap S$ . Now Corollary 16 says that, conditioning on $|X_i\cap S|,|Y_i\cap S|\ge Cp^{-1}\log n$ , the probability that $\big(X_i\cap S,Y_i\cap S\big)$ fails to have the desired regularity in G is at most $2^{-Cp^{-1}\log n}$ , and taking a union bound over the choices of i the result follows.

3. Main technical result and main lemmas

We deduce Theorem 5 from the following technical result (corresponding results also appear in the predecessor papers [Reference Allen, Böttcher, Ehrenmüller and Taraz1, Reference Böttcher, Schacht and Taraz4]). This result is more general in that it allows for an extra colour, zero, in the colouring of H, provided that this colour does not appear too often.

The basic proof strategy for this theorem is analogous to the proof strategy for [Reference Allen, Böttcher, Ehrenmüller and Taraz1, Theorem 23]. Eventually, we will apply the sparse blow-up lemma, Lemma 13, to embed most of H into G, and we need to obtain the necessary conditions for this lemma. The difficulty is that, whatever regular partition of G we take, there may be some exceptional vertices which are ‘badly behaved’ with respect to this partition. Our first main lemma, the following Lemma for G, states that there is a partition with only few such vertices, which we collect in a set $V_0$ . These vertices will be dealt with in a pre-embedding stage before the application of the sparse blow-up lemma.

For the application of the sparse blow-up lemma the following two graphs $B^k_r$ and $K^k_r$ , which we shall find as subgraphs of the reduced graph of G, are essential. Let $r, k \geq 1$ and let $B^k_r$ be the backbone graph on kr vertices. That is, we have

\begin{equation*}V(B^k_r) \;:\!=\; [r] \times [k]\end{equation*}

and for every $j \neq j^{\prime} \in [k]$ we have $\{(i,j),(i^{\prime},\kern0.5pt j^{\prime})\} \in E(B^k_r)$ if and only if $|i-i^{\prime}|\le1$ . Let $K^k_r \subseteq B^k_r$ be the spanning subgraph of $B^k_r$ that is the disjoint union of r complete graphs on k vertices given by the following components: the complete graph $K^k_r[\{(i,1),\ldots, (i,k)\}]$ is called the i-th component of $K^k_r$ for each $i\in [r]$ .

A vertex partition ${\mathcal V}' = \{V_{i,j}\}_{i\in[r],j\in[k]}$ is called k-equitable if $\big||V_{i,j}| -|V_{i,j^{\prime}}|\big|\leq 1$ for every $i\in [r]$ and $j,j^{\prime}\in[k]$ . Similarly, an integer partition $\{n_{i,j}\}_{i\in[r],j\in[k]}$ of n (meaning that $n_{i,j} \in \mathbb Z_{\geq 0}$ for every $i\in [r],j\in[k]$ and $\sum_{i\in[r]j\in[k]} n_{i,j} = n$ ) is k-equitable if $|n_{i,j}-n_{i,j^{\prime}}| \leq 1$ for every $i\in[r]$ and $j,j^{\prime}\in[k]$ .

The Lemma for G then guarantees a k-equitable partition for G whose reduced graph $R^k_r$ contains a copy of the backbone graph $B^k_r$ , is super-regular on $K^k_r\subset B^k_r$ , and satisfies certain regularity inheritance properties.

The next step is to find a partition of H which more or less matches that of G. This partition of H defines an assignment of the vertices of H to the clusters of G. In other words, we assign the vertices in V(H) indices (i,j) of the partition ${\mathcal V}$ , such that about $|V_{i,j}|$ vertices are assigned (i,j) and all edges of H are assigned to edges of $R^k_r$ . In fact, the lemma states further that most edges of H are assigned to edges of $K^k_r$ , and only those incident to vertices of a small set of special vertices X may be assigned to other edges of $R^k_r$ .

Our next lemma concerns the pre-embedding stage, in which we cover the vertices in $V_0\subset V(G)$ with vertices of H. For this purpose we use the vertices of H whose neighbourhood contains only s colours. Let x be one of these vertices, let H ^′ be the subgraph of H induced on all vertices of distance at most $s+1$ from x (including x), and let T be the set of those vertices in H ^′ of distance exactly $s+1$ from x. We cover a vertex v of $V_0$ by embedding x onto v, and we also embed all other vertices in the corresponding H ^′ which are not in T. This creates image restrictions on the vertices of G to which we can embed the vertices in T. For the application of Lemma 13, we need that these image restrictions satisfy certain conditions, and that this pre-embedding preserves the super-regularity of the remaining partition of G. For achieving the latter, we take a random induced subgraph G ^′ of G containing roughly $\mu n$ vertices, and perform the pre-embedding in G ^′ only. In each cluster of G, the subgraph G ^′ selects roughly a $\mu$ -fraction of the vertices, and the induced partitions on G ^′ and on $G-V({G^{\,\prime}})$ are also super-regular. The next lemma states that we can also obtain suitable image restrictions for the vertices in T while performing the pre-embedding in G ^′.

This lemma is a main difference to the proof in [Reference Allen, Böttcher, Ehrenmüller and Taraz1] and is the place where we need that the neighbourhood of every vertex in G has a certain density of $K_s$ ’s. Another difference to our proof strategy that this lemma creates, is that it selects a clique $\{q_1,\ldots,q_k\}$ in R, which might not be one of the cliques of the chosen $K_r^k\subseteq R$ , and the vertices of T are assigned to the corresponding clusters in G (that is, the image restriction of $y\in T$ is a subset of the cluster $V_{q_j}$ to which it is assigned). This assignment may well differ from the assignment given by the Lemma for H, so in our proof of Theorem 22 we need to adapt to this difference by reassigning some more H-vertices.

After the pre-embedding stage, we want to apply the sparse blow-up lemma to embed the remainder of H. However, the sizes of the clusters $V_{i,j}$ from Lemma 23 do not quite match the sizes of the sets $X_{i,j}$ from Lemma 24. Also, Lemma 25 embeds some vertices, creating a little further imbalance, and we need to slightly alter the mapping f from Lemma 24 to accommodate these pre-embedded vertices. The next lemma allows us to change the sizes of the clusters $V_{i,j}$ slightly to match the partition of H, without destroying the properties of the partition of G and of the pre-embedded vertices we worked to achieve.

After applying Lemma 26 it remains only to check that the conditions of Lemma 13 are met to complete the embedding of H and thus the proof of Theorem 22.

4. Proof of the pre-embedding lemma

Before outlining how this proof works in general, let us briefly explain how it would work in a simple case. If all vertices of H ^′ are adjacent to the root x (as would be the case, for example, if H is a $K_k$ -factor), then the set T is empty, and hence most of the properties we need are vacuously true. We just have to find an embedding of H ^′ to G ^′ extending $x\to v$ . We apply the Sparse Regularity Lemma to $N_{{G^{\,\prime}}}(v)$ , and (since there are many copies of $K_s$ in that neighbourhood) we are guaranteed to find s clusters $W'_{\!\!1},\dots,W'_{\!\!s}$ among which every pair is $(\nu_0,d',p)$ -regular. Here $\nu_0$ is a regularity parameter which is small compared to $1/v(H')$ but quite a lot larger than the $\varepsilon$ regularity we get from the Lemma for G; and d ^′ is roughly d. We now use a standard sparse regularity vertex-by-vertex embedding method. That is, we begin by assigning to each vertex $y\in V(H')\setminus\{x\}$ a candidate set $W'_{\!\!\rho(y)}$ . By construction, all candidate sets are reasonably large, and if y and y ^′ are adjacent in H ^′ then their candidate sets form a $(\nu_0,d',p)$ -regular pair. This is the initial setup.

We now embed vertices one at a time: when we embed a vertex y, we insist on embedding it to its current candidate set, and we then update the candidate sets of its neighbours by intersecting them with $N_{G}(y)$ . We can do this in such a way that the two properties mentioned above are maintained, i.e. all candidate sets are reasonably large and adjacent vertices’ candidate sets form a regular pair (with a regularity parameter which is not necessarily as small as $\nu_0$ , but does not get too much larger). To show this is possible, we use the definition of a regular pair, plus the regularity inheritance Lemmas 14 and 15. The argument that we can do this—i.e. given a collection of reasonably large candidate sets with the above regularity properties, we can embed one more vertex to its candidate set and maintain that our remaining vertices have reasonably large candidate sets with the regularity properties—is given in Claim 2 below.

The difficulty comes when T is not empty. What we want to do is to obtain a similar initial setup: the neighbours of x in H ^′ should be given candidate sets as before, while the vertices in T should be given candidate sets chosen from $\{V_{q_1},\dots,V_{q_k}\}$ , where $V_1,\dots,V_r$ is the ambient regular partition with reduced graph R supplied to the lemma, and $q_1,\dots,q_k$ form some clique in R. The remaining vertices should somehow be given candidate sets such that (as above) every vertex has a reasonably large candidate set, and adjacent vertices have candidate sets which form $(\nu_0,d',p)$ -regular pairs. If we can do this, then using the above mentioned Claim 2 repeatedly to embed $V(H')\setminus T$ will automatically give all the required properties for the vertices in T.

The reason why getting this initial setup is tricky is that the only way we can ensure that the Sparse Regularity Lemma gives us a regular partition consistent with the ambient partition is to apply the refining version, Lemma 10, with clusters of the ambient partition as the input. Ideally, we would simply input the ambient partition and $N_{{G^{\,\prime}}}(v)$ as the sets to refine. We would then get a fine partition with a corresponding fine $(\nu,d',p)$ -reduced graph. As above, we would be able to find $W'_{\!\!1},\dots,W'_{\!\!s}$ contained in $N_{{G^{\,\prime}}}(v)$ which form a clique in the fine reduced graph which are candidate sets for the neighbours of x. In addition, from the minimum degree condition it follows that any k vertices in the fine reduced graph have a common neighbour which is contained in some part of the ambient partition, and we can use this to greedily find candidate sets for the vertices of H ^′ further from x until finally we can assign candidate sets for the vertices of T which are contained in the ambient partition.

This ideal strategy fails for the following reason. The fine partition will have too many parts: that is, a part of the fine partition contained in any $V_i$ will be a very tiny (much smaller than $\varepsilon$ ) fraction of $V_i$ , and hence the candidate sets for vertices of T will not be sufficiently large for ( P4’). The reason that this occurs is that the number of parts into which we split $V_i$ depends on the number of parts of the input partition we give to Lemma 10, which in turn depends on $\varepsilon$ (and these dependencies are not in our favour).

What we therefore do is to fix a number $\ell$ of parts of the ambient partition, and a set L of $\ell$ parts, where $\ell$ is not too large (in particular it is tiny compared to $\varepsilon^{-1}$ ) and we use Lemma 10 with input only the $V_i$ with $i\in L$ and $N_{{G^{\,\prime}}}(v)$ . This breaks the above undesired dependency in our constant choices. In order to make the argument go through, however, we need $\bigcup_{i\in L}V_i$ to ‘witness’ the minimum degree of G. It turns out that if $\ell$ is not too small, then choosing L uniformly at random works for this latter purpose. We justify this in Claim 1.

Proof of Lemma 25. First, we fix all constants that we need throughout the proof. Let $\Delta, k\geq 2$ and $\unicode[Times]{x03B3}, d>0$ be given. Recall $d\le\tfrac{\unicode[Times]{x03B3}}{32}$ by assumption of the lemma. Let $d' = \min(\tfrac12d, 10^{-5k}\unicode[Times]{x03B3})$ and choose $\xi= 10^{-6}2^{-k}\unicode[Times]{x03B3}$ and an integer

\begin{equation*}\ell=\max\big(1000\xi^{-6}\log\xi^{-1},100\cdot 2^k\unicode[Times]{x03B3}^{-1}\big)\,.\end{equation*}

Let $\nu^{\ast}_{\Delta-1,\Delta-1}=\nu^{\ast}_{i,\Delta}=\nu^{\ast}_{\Delta,i}=\tfrac{1}{100\Delta}8^{-\Delta}d'^{\Delta}$ for $i \in [\Delta]$ . For each $(i,j) \in\{0, \dots, \Delta-1\}^2\setminus\{(\Delta-1,\Delta-1)\}$ in reverse lexicographic order, we choose $\nu^{\ast}_{i,j}\le\nu^{\ast}_{i+1,j},\nu^{\ast}_{i,j+1},\nu^{\ast}_{i+1,j+1}$ not larger than the $\varepsilon_0$ returned by Lemma 14 for both input $\nu^{\ast}_{i+1,j}$ and d ^′, and for input $\nu^{\ast}_{i,j+1}$ and d ^′, and not larger than the $\varepsilon_0$ returned by Lemma 15 for input $\nu^{\ast}_{i+1,j+1}$ and d ^′. Choose $\nu_0=\min\big(\nu^{\ast}_{0,0},\tfrac{d'}{2},10^{-5}\unicode[Times]{x03B3}\big)$ . Now, Lemma 10 with input $\nu_0^2/(16\ell^2)$ and $2\ell$ returns $t_1$ .

Set $\zeta= \big(\tfrac{d'}{4}\big)^\Delta /4 t_1$ . Given $\varepsilon'$ , let $\varepsilon^{\ast\ast}_{\Delta} = \varepsilon'$ and for every $i \in (\Delta-1, \dots,1,0)$ , let $\varepsilon^{\ast\ast}_{i}\le\varepsilon^{\ast\ast}_{i+1}$ be returned by Lemma 14 with input $\varepsilon_{{OSRIL}}= \varepsilon^{\ast\ast}_{i+1}$ and $\alpha_{OSRIL} = d$ . Next, let $\varepsilon^{\ast}_{\Delta-1,\Delta-1}=\varepsilon'$ and $\varepsilon^{\ast}_{i,\Delta}=\varepsilon^{\ast}_{\Delta,i}=1$ for $i \in [\Delta]$ . For each $(i,j) \in\{0, \dots, \Delta-1\}^2\setminus\{(\Delta-1,\Delta-1)\}$ in reverse lexicographic order, we choose $\varepsilon^{\ast}_{i,j}\le\varepsilon^{\ast}_{i+1,j},\varepsilon^{\ast}_{i,j+1},\varepsilon^{\ast}_{i+1,j+1}$ not larger than the $\varepsilon_0$ returned by Lemma 14 for both input $\varepsilon^{\ast}_{i+1,j}$ and d, and for input $\varepsilon^{\ast}_{i,j+1}$ and d, and not larger than the $\varepsilon_0$ returned by Lemma 15 for input $\varepsilon^{\ast}_{i+1,j+1}$ and d.

We choose $\varepsilon_0 \leq \varepsilon^{\ast\ast}_0, \varepsilon^{\ast}_{0,0}, \frac{\nu_0}{2t_1}$ small enough such that $(1+\varepsilon_0)^{\Delta} \leq 1+\varepsilon'$ and $(1-\varepsilon_0)^{\Delta} \geq 1-\varepsilon'$ . Given $r\ge 10^5\unicode[Times]{x03B3}^{-1}$ , $\varepsilon$ with $0<\varepsilon\le\varepsilon_0$ , and $\mu > 0$ , let C be a large enough constant for all of the above calls to Lemmas 14 and 15, and for Proposition 17 with input $\varepsilon_0$ . Finally, we choose $C^{\ast}=10^{10\Delta}d'^{-\Delta}\ell t_1r\mu^{-1}$ .

Let $\Gamma = G(n,p)$ with $p \geq C^{\ast} {(\log n/n)}^{1/\Delta}$ . Then $\Gamma$ satisfies a.a.s. the properties stated in Lemma 14, Lemma 15, Proposition 17 and Lemma 10 with the parameters specified above. We assume from now on that $\Gamma$ satisfies these good events and has these properties. Let G ^′, $v\in V({G^{\,\prime}})$ , G, $\{V_i\}_{i\in \{0, \ldots, r\}}$ , H ^′, $x \in V(H')$ , the k-colouring $\rho$ of V(H ^′), and the $(\varepsilon,d,p)$ -reduced graph R, be as in the statement of the lemma. Since $\varepsilon\le\varepsilon_0$ , R is also an $(\varepsilon_0,d,p)$ -reduced graph.

To be able to apply Lemma 10 we need to choose a suitable subset of the clusters $\{V_i\}_{i\in \{0, \ldots, r\}}$ of bounded size. As the clusters $\{V_i\}_{i\in \{0, \ldots, r\}}$ might be of different sizes and we will want to have a minimum degree condition on the reduced graph, we will consider a weighted version of this degree that takes the cluster sizes into account.

Claim 1. There exists $L \subset [r]$ of size $\ell$ such that $R^\ast\;:\!=\;R[L]$ satisfies the following weighted minimum degree condition, where $V^\ast = \bigcup_{i \in L} V_i$ .

\begin{equation*} \forall i \in L: \sum_{j \in N_R(i) \cap L} \frac{|V_j|}{|V^\ast|} \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{5}\right)\,. \end{equation*}

Additionally, we have that

\begin{equation*} W\;:\!=\; \left\{ w \in N_{G^{\kern1pt\prime}}(v): |N_{G^{\,\prime}}(w) \cap V^\ast| \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{5}\right)p|V^\ast \cap V({G^{\,\prime}})| \right\} \end{equation*}

has size at least $(1 - \xi) |N_{{G^{\,\prime}}}(v)|$ and there are at least $\frac12 \unicode[Times]{x03B3} p^{\binom{s+1}{2}}{(\mu n)}^s$ copies of $K_s$ in W.

Proof. We choose a subset $L \subset [r]$ of size $\ell$ uniformly at random. First, we will transfer the minimum degree of G to the reduced graph and show that with high probability the minimum degree is preserved on the chosen clusters. Recall that G satisfies a minimum degree of $\delta(G) \ge (\frac{k-1}{k} + \unicode[Times]{x03B3})pn$ and that the cluster sizes satisfy

(1) \begin{equation} \frac{4n}{r} \ge |V_i| \ge \frac{n}{4r} \ge Cp^{-1} \log n\,.\end{equation}

Without loss of generality, we may assume that no $V_i$ forms an irregular pair with more than $\sqrt{\varepsilon}$ of the clusters, otherwise, add it to $V_0$ , which over all clusters increases the size of $V_0$ by at most $4\sqrt{\varepsilon}n$ . Fix $i \in [r]$ . Proposition 17 applied to the edges between $V_i$ and $V_0$ implies that

\begin{equation*} e(V_i, V_0) \le 2p (\varepsilon + 4\sqrt{\varepsilon})n |V_i| \quad \text{and} \quad e(V_i) \le 2p {|V_i|}^2 \le 2p \frac{16}{r}n |V_i|\,.\end{equation*}

Also, we can bound the number of edges from $V_i$ to other clusters that are in pairs which are not dense or $(\varepsilon,p)$ -regular by

\begin{equation*} e\Big(V_i, \bigcup_{j \in R \setminus N_R(i)} V_j\Big) \le dpn |V_i| + 2p \cdot 4\sqrt{\varepsilon} n |V_i|\,.\end{equation*}

Putting the above together, we obtain that

\begin{equation*} e\Big(V_i, \bigcup_{j \in N_R(i)} V_j\Big) \ge \left(\frac{k-1}{k} + \unicode[Times]{x03B3} - 2\varepsilon - 16\sqrt{\varepsilon} - d - \frac{32}{r}\right)pn |V_i|\,.\end{equation*}

As, again by Proposition 17, the number of edges between any $V_i$ and $V_j$ is at most $(1+\varepsilon_0)|V_i||V_j|$ , we get that

\begin{equation*} \sum_{j \in N_R(i)} \frac{|V_j|r}{|V(G)|} \ge \left(\frac{k-1}{k} + \unicode[Times]{x03B3} - 2\varepsilon - 16\sqrt{\varepsilon} - d - \frac{32}{r}\right) {(1+\varepsilon_0)}^{-1} r \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{2} \right) r\,.\end{equation*}

By the size conditions on the clusters, the relative sizes $w_j \;:\!=\; \frac{|V_j|r}{|V(G)|}$ take values in $(\frac 14,4)$ . We now consider

\begin{equation*} w'_{\!\!j} = \xi \left\lfloor {w_j}/{\xi} \right\rfloor,\end{equation*}

the discretisation of $w_j$ into steps of size $\xi$ . Of these discretised weights, we will ignore those that occur fewer than $\xi^2 r$ times. We lose at most a factor of $4\xi$ due to the discretisation as all weights are at least $\frac 14$ . Also weights in $(\frac 14,4)$ occurring fewer than $\xi^2 r$ times contribute at most $16 \xi r$ to the sum, so we get the lower bound

\begin{equation*} \sum_{j \in N_R(i)} w'_{\!\!j} \ge \left(1-4\xi\right) \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{2} \right) r - 16 \xi r \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{3} \right) r\,.\end{equation*}

We can now apply the hypergeometric inequality (Theorem 19) to all possible rounded weight values separately. For any $j \in [r]$ the probability that j is in L is $\ell/r$ and so for a given density in $(\frac 14, 4)$ , which occurs, say, $\theta r$ times, the probability that this density is chosen fewer than $(1-\xi)\theta\ell$ times is at most $2e^{-\xi^2 \cdot \xi \theta \ell/3} \le 2e^{-\xi^5 \ell/3}$ . This implies by the union bound that with probability at most $4\xi^{-1} 2e^{-\xi^5 \ell/3}$ we do not have

(2) \begin{equation} \sum_{j \in N_R(i) \cap L} w_j \ge (1-\xi)\left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{3} \right) \frac{\ell}{r} r \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{4} \right) \ell\,.\end{equation}

So by the union bound the expected number of vertices in $R^\ast$ that do not satisfy (2) is at most $\ell 8 \xi^{-1} e^{-{\xi^5 \ell}/{3}}<1/10$ , where the inequality is by choice of $\ell$ . By Markov’s inequality, the probability that there is any such vertex in $R^\ast$ is thus at most $1/10$ . By the same discretisation of $w_j$ and application of the hypergeometric inequality to the discretised weights, we can also deduce that

(3) \begin{equation} |V^\ast| = \frac{|V(G)|}{r} \sum_{i \in L} w_i = (1 \pm 100\xi) \frac{\ell}{r} \sum_{i \in [r]} w_i = (1 \pm 100\xi) (1 \pm \varepsilon) \frac{\ell |V(G)|}{r}\end{equation}

with probability at least $9/10$ . Putting (2) and (3) together implies that with probability at least $8/10$ the first claimed statement holds.

For the claim, we also require that the minimum degree condition of the vertices in $N_{{G^{\,\prime}}}(v)$ carries over to the chosen clusters for most vertices. Fix w in $N_{{G^{\,\prime}}}$ . For $j \in [r]$ we consider the weighted p-density, which may take values in (0,5), defined by

\begin{equation*} {d}_{w,j} = {d}_{G,p}(\{w\},V_j \cap V({G^{\,\prime}})) \frac{|V_j \cap V({G^{\,\prime}})|r}{|V({G^{\,\prime}})|}\,.\end{equation*}

Accounting for the exceptional set $V_0$ with Proposition 17, the minimum degree condition on G ^′ of $(\frac{k-1}{k} + {\unicode[Times]{x03B3}})p|V({G^{\,\prime}})|$ implies that these weighted p-densities satisfy

\begin{equation*} \sum_{j \in [r]} {d}_{w,j} \ge \left(\frac{k-1}{k} + {\unicode[Times]{x03B3}} - 2\varepsilon\right)r \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{2}\right)r\,.\end{equation*}

Similarly to before, we consider ${d'}_{w,i} = \xi \lfloor {{d}_{w,i}}/{\xi} \rfloor$ , the discretisation of ${d}_{w,i}$ into steps of size $\xi$ . Of these discretised weighted densities, we ignore those that occur fewer than $\xi^2 r$ times and those that are smaller than $\sqrt{\xi}$ . The small densities contribute at most $\sqrt{\xi}r$ to the sum and we lose a factor of at most $\sqrt{\xi}$ due to the discretisation for larger values. Also weights in $(\sqrt{\xi},5)$ occurring fewer than $\xi^2 r$ times contribute at most $25\xi r$ to the sum, so we get the lower bound

\begin{equation*} \sum_{i \in [r]} {d'}_{w,i} \ge (1 - \sqrt{\xi}) \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{2} - \sqrt{\xi} - 25 \xi\right)r \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{3}\right)r\,.\end{equation*}

Applying the hypergeometric inequality to all density values separately as before, we get that for any $w \in N_{{G^{\,\prime}}}(v)$ with probability at most $5\xi^{-1} 2e^{-\xi^5 \ell/3} \ge \xi / 10$ we do not have

(4) \begin{equation} \sum_{i \in L} {d'}_{w,i} \ge \left( 1 - \xi\right) \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{3}\right) \frac{\ell}{r} r \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{4}\right) \frac{\ell}{r} r\,.\end{equation}

So the expected number of vertices in $N_{{G^{\,\prime}}}(v)$ not satisfying (4) is at most $\xi |N_{{G^{\,\prime}}}(v)| / 10$ . By Markov’s inequality, with probability at least $9/10$ at most a fraction $\xi$ of vertices in $N_{{G^{\,\prime}}}(v)$ violate (4). And in particular all vertices satisfying (4) have at least

\begin{equation*} (1 - 100\xi) (1 - \varepsilon) \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{4}\right) (1 - \varepsilon) \mu p|V^\ast| \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{5}\right)p|V^\ast \cap V({G^{\,\prime}})|\end{equation*}

neighbours in $V^\ast \cap V({G^{\,\prime}})$ if (3) holds. So indeed with probability at least $7/10$ the first two claimed statements hold, so assume we chose L such that they do.

For the claim it only remains to show the lower bound on the number of cliques in W. It follows, by inductively building up cliques, from the assumption in the lemma that any $t \le \Delta$ vertices of G ^′ have at most $2 p^t \mu n$ common neighbours in G ^′, that v and each $w \in N_{{G^{\,\prime}}}(v)$ are contained in at most

\begin{equation*} \prod_{t=2}^{s} 2 p^t \mu n = p^{\binom{s+1}{2}-1} {(2\mu n)}^{s-1}\end{equation*}

copies of $K_{s+1}$ . Since $|W|\ge (1-\xi)|N_{{G^{\,\prime}}}(v)|$ , the number of copies of $K_s$ which are in $N_{{G^{\,\prime}}}(v)$ but not W is at most $\xi|N_{{G^{\,\prime}}}(v)|\cdot p^{\binom{s+1}{2}-1}(2\mu n)^{s-1}$ . Since $|N_{{G^{\,\prime}}}(v)|\le 2\mu pn $ , and $N_{{G^{\,\prime}}}(v)$ contains at least $\unicode[Times]{x03B3} p^{\binom{s+1}{2}}(\mu n)^s$ copies of $K_s$ , there are at least

\begin{equation*} \unicode[Times]{x03B3} p^{\binom{s+1}{2}}{(\mu n)}^s - \xi \cdot2\mu pn\cdot p^{\binom{s+1}{2}-1} {(2\mu n)}^{s-1} \ge \tfrac12 \unicode[Times]{x03B3} p^{\binom{s+1}{2}} {(\mu n)}^s\end{equation*}

copies of $K_s$ in W.

Let $\{W_i\}_{i \in [\ell]}$ be an arbitrary equipartition of W into $\ell$ parts (so that the fine partition we are about to obtain has enough parts in W). We apply Lemma 10 to G ^′ with the $2\ell$ -part initial partition $\{ (V_i \cap V({G^{\,\prime}})) \setminus W \}_{i\in L} \cup \{W_i\}_{i \in [\ell]}$ and input parameter $\nu_0^2/(16\ell^2)$ . This returns a partition refining each of these sets into $1\le t\le t_1$ clusters $\{V_{i,j}\}_{i\in L,j\in[t]}\cup\{W_{i,j}\}_{i\in[\ell],j\in[t]}$ together with small exceptional sets $\{V_{i,0}:i\in L\}\cup\{ W_{i,0}: i\in[\ell]\}$ . From the definition of a regular refinement, there are at most $\tfrac{\nu_0^2}{16\ell^2}\cdot(2\ell t)^2$ irregular pairs in this partition, and in particular at most $\nu_0 t$ of the clusters form an irregular pair with more than $\nu_0 t$ of the clusters. Include the vertices of all those clusters in the exceptional sets, which now make up a fraction of at most $2 \nu_0$ of the vertices.

We now want to obtain s clusters $W'_{\!\!1},\dots,W'_{\!\!s}$ in ${\{W_{i,j}\}}_{i \in [\ell],j \in [t]}$ that are pairwise $(\nu_0, d', p)$ -regular. Assume for a contradiction that no such clusters exist. So each $K_k$ in W must either contain an edge meeting an exceptional set $W_{i,0}$ , one which does not lie in a $(\nu_0, d', p)$ -regular pair or one that is contained completely in some set $W_{i,j}$ for $i\in[\ell]$ and $j\in[t]$ . Note that we have for all $i \in [\ell]$ and $j \in [t]$ that

\begin{equation*} |W_{i,j}| \ge \frac{1}{2 \ell t_1} |W| \ge \frac{\mu np}{4\ell t_1} \ge Cp^{-1} \log n\,.\end{equation*}

So we may apply Proposition 17 to bound the number of edges within and between clusters. Using the upper bound on common neighbourhoods in G ^′ given in the lemma statement to bound the number of edges meeting the exceptional sets, we obtain that deleting at most

\begin{equation*} 2 \nu_0 |W| 2p^2 \mu n + 2p(\nu_0 + d') {|W|}^2 + \ell 2p {(|W|/\ell)}^2 \le (8\nu_0 + 8\nu_0 + 8d' + {2}/{\ell}) p^3 \mu^2 n^2\end{equation*}

edges would remove all cliques from W. Again by the upper bound on common neighbourhoods in G ^′ given in the lemma any of these edges is contained in at most

\begin{equation*} \prod_{t=3}^{s} 2 p^t \mu n = p^{\binom{s+1}{2}-3} {(2\mu n)}^{s-2}\end{equation*}

copies of $K_{s+1}$ together with v. So there would be at most

\begin{equation*} (16\nu_0 + 8d' + {2}/{\ell}) p^3 \mu^2 n^2 p^{\binom{s+1}{2}-3} {(2\mu n)}^{s-2} < \tfrac12 \unicode[Times]{x03B3} p^{\binom{s+1}{2}} {(\mu n)}^s\end{equation*}

copies of $K_s$ in W, a contradiction. It follows that there are some s clusters in W which are pairwise $(\nu_0,d',p)$ -regular. Let $W'_{\!\!1},\dots,W'_{\!\!s}$ in ${\{W_{i,j}\}}_{i \in [\ell],j \in [t]}$ be pairwise $(\nu_0, d', p)$ -regular.

Because the vertices of W each have at least $\big(\tfrac{k-1}{k}+\tfrac{\unicode[Times]{x03B3}}{5}\big)p|V^*\cap V({G^{\,\prime}})|$ G ^′-neighbours in $V^*$ , the number of edges leaving each cluster $W'_{\!\!i}$ to $V^*$ is at least $|W'_{\!\!i}|\big(\tfrac{k-1}{k}+\tfrac{\unicode[Times]{x03B3}}{5}\big)p|V^*\cap V({G^{\,\prime}})|$ . By Proposition 17, and because at most $\nu_0t$ irregular pairs leave $W'_{\!\!i}$ , at most $(1+\varepsilon_0)p|W'_{\!\!i}|\nu_0|V^*\cap V({G^{\,\prime}})|$ of these edges lie in irregular pairs. By definition, at most $d'p|W'_{\!\!i}||V^*\cap V({G^{\,\prime}})|$ of these edges lie in pairs of relative density less than d ^′. Thus the remaining edges lie in $(\nu_0,d',p)$ -regular pairs, and there are at least $|W'_{\!\!i}|\big(\tfrac{k-1}{k}+\tfrac{\unicode[Times]{x03B3}}{6}\big)p|V^*\cap V({G^{\,\prime}})|$ of these edges. Since the number of edges between $W'_{\!\!i}$ and any given $V_{i^{\prime},\kern0.5pt j^{\prime}}$ is at most $(1+\varepsilon_0)p|W'_{\!\!i}||V_{i^{\prime},\kern0.5pt j^{\prime}}|$ by Proposition 17, we obtain

(5) \begin{equation} \sum_{V_{i^{\prime},\kern0.5pt j^{\prime}}:\, (W'_{\!\!i}, V_{i^{\prime},\kern0.5pt j^{\prime}})\text{ is }(\nu_0, d', p)-\text{regular}} \frac{|V_{i^{\prime},\kern0.5pt j^{\prime}}|}{|V^\ast \cap V({G^{\,\prime}})|} \ge \left(\frac{k-1}{k} + \frac{\unicode[Times]{x03B3}}{8}\right)\,.\end{equation}

Now we can choose the clusters into which we will embed the vertices of H ^′. We choose sequentially

\begin{equation*} (q_{s+1},j_{s+1}),\dots,(q_{k+1},j_{k+1}) \in L \times [t]\end{equation*}

such that for each $1\le i\le s$ and each $s+1\le i^{\prime}\le k+1$ , the pair $\big(W'_{\!\!i},V_{q_{i^{\prime}},j_{i^{\prime}}}\cap V({G^{\,\prime}})\big)$ is $(\nu_0,d',p)$ -regular, and for each $s+1\le i^{\prime}<i^{\prime}\le k+1$ the pair $(q_{i}',q_{i^{\prime}})$ is an edge of $R^*$ . This is possible by (5) and Claim 1, which give a weighted minimum degree condition that implies that for any k clusters (in W or $V^*$ or a mixture) there is a cluster in $V^*$ which satisfies the given condition with respect to all k clusters.

We then choose pairs $(q_{s},j_{s}),\dots,(q_{1},j_{1})$ in that order sequentially such that for each $a \in \{s, \dots, 1\}$ the clusters

\begin{equation*} W'_{\!\!1},\dots,W'_{\!\!a-1}, V_{q_{a},j_{a}},V_{q_{a+1},j_{a+1}},\dots,V_{q_{k+1},j_{k+1}}\end{equation*}

satisfy the same condition, i.e. for each $1\le i\le a$ and each $a+1\le i^{\prime}\le k+1$ , the pair $\big(W'_{\!\!i},V_{q_{i^{\prime}},j_{i^{\prime}}}\cap V({G^{\,\prime}})\big)$ is $(\nu_0,d',p)$ -regular, and for each $a+1\le i^{\prime}<i^{\prime}\le k+1$ the pair $(q_{i}',q_{i^{\prime}})$ is an edge of $R^*$ . Note that by choice of $\varepsilon_0$ , if $(q_{i^{\prime}},q_{i^{\prime}})$ is an edge of $R^*$ then the pair $\big(V_{q_{i^{\prime}},j_{i^{\prime}}}\cap V({G^{\,\prime}})\setminus W,V_{q_{i^{\prime}},j_{i^{\prime}}}\cap V({G^{\,\prime}})\setminus W\big)$ is $(\nu_0,d',p)$ -regular in G ^′. For convenience, we let $V'_i\;:\!=\;V_{q_i,j_i}\cap V({G^{\,\prime}})\setminus W$ for each $1\le i\le k+1$ .

We will embed $H'-(\{x\}\cup T)$ into the chosen clusters, i.e. $W'_{\!\!1},\dots,W'_{\!\!s},V'_{\!\!1},\dots,V'_{\!\!k+1}$ , using the regularity embedding strategy mentioned above. We will need to embed some vertices of H ^′ which are not neighbours of x into the sets $W'_{\!\!i}$ . For this to work, each such vertex u needs to have at most $\Delta-3$ neighbours which we embed before u, and the aim of the next arguments is to assign vertices of H ^′ to clusters, and put an order on V(H ^′), which ensures this.

Recall that $\rho$ is a proper k-colouring of H ^′ which uses only s colours on N(x). Reordering the colours if necessary, let us assume $\rho$ uses only colours in [s] on N(x). We define a proper $(k+1)$ -vertex colouring $\rho':V(H') \to [k+1]$ inductively as follows. Initially, we set $\rho'(w)=\rho(w)$ for all w in H ^′. Let

\begin{equation*} U_{\rho^{\prime}} = \bigcup_{i=2}^{s} \left\{ w \in N^i(x): \rho'(w) \le s-i+1 \right\},\end{equation*}

where $N^i(x)$ refers to the vertices at distance i from x. If $U_{\rho^{\prime}}$ contains a vertex w with no neighbour in ${\rho'}^{-1}(i)$ for some $\rho'(w)+1\le i\le k+1$ , we set $\rho'(w)=i$ (if there are several such i, we choose one arbitrarily). We repeat this step until $U_{\rho^{\prime}}$ contains no such vertices. Since the colour of any given vertex only increases through this process, the recolouring procedure must terminate eventually. The resulting $\rho'$ has the following property: if u is any vertex with $d(x,u)\ge 2$ and $d(x,u)+\rho'(u)\le s+1$ , then u has a neighbour in each of the colour classes $\rho'(u)+1,\dots,k+1$ . In particular, since $\rho'(u)\le s-1$ (as otherwise $d(x,u)+\rho'(u)\le s+1$ is impossible), and since $s\le k-1$ by assumption of the lemma, u has a neighbour in each of the colour classes $k-1$ , k and $k+1$ . Observe that no vertex in these colour classes is in $U_{\rho^{\prime}}$ by definition.

Note that the colouring remains unchanged on N(x) and the vertices at distance $s+1$ from x. We define an order $<_{\rho^{\prime}}$ on $V(H')\setminus \{x\}$ by putting first all the vertices of $U_{\rho^{\prime}}$ in an arbitrary order, then the remaining vertices of $V(H')\setminus (T\cup\{x\})$ in an arbitrary order, and finally the vertices of T in an arbitrary order. With the colouring $\rho'$ defined as above, this gives us, for all u at distance at least two from x with $\rho'(u) + d(x,u) \le s+1$ :

(6) \begin{equation} |\text{pred}_{<_{\rho^{\prime}}}(u) \cap N(u)| = |\{u': u' <_{\rho^{\prime}} u, u' \in N(u)\}| \le \Delta - 3\,.\end{equation}

Now we can assign the vertices of H ^′ to clusters. For $u \in V(H')$ , let

\begin{equation*} V_u = V_{q_{\rho^{\prime}(u)}} \quad \text{and} \quad C_u = \begin{cases} W'_{\!\!\rho^{\prime}(u)} & \text{if } \rho'(u) + d(x,u) \le s+1 \\ V_{q_{\rho^{\prime}(u)},j_{\rho^{\prime}(u)}} & \text{otherwise}.\\ \end{cases}\end{equation*}

We now iteratively embed the vertices of H ^′ in the order specified above respecting the assignments to clusters. The following claim, which we prove by induction on the number of embedded vertices, encapsulates the conditions we maintain through this embedding. Here, as in the statement of the lemma, we set $\Pi(u)=\phi\big(N_{H'}(u)\cap {\mathrm{Dom}}(\phi)\big)$ , and recall that T is the vertices in H ^′ at distance exactly $s+1$ from v.

Proof. We prove the claim inductively, starting with $z=0$ and $\phi$ the empty embedding. We first check that the claimed properties hold for this embedding. ( I1) is true vacuously. Since $\Pi(u)=\emptyset$ for each $u\in V(H')\setminus\{x\}$ , the various neighbourhoods in $C_u$ and $C'_{\!\!u}$ are equal to $C_u$ and $C_{u'}$ . So ( I2) and ( I3) hold trivially, and ( I4) holds by choice of the $W'_{\!\!i}$ and by choice of $\nu^{\ast}_{0,0}$ . Similarly, ( L1) and ( L3) hold because by choice of the $q_j$ the pair $(V_{q_j},V_{q_{j^{\prime}}})$ is $(\varepsilon,d',p)$ -regular for each $1\le j<j^{\prime}\le k+1$ , and ( L2) holds trivially.

We now have to show the induction step holds; suppose that for some $0\le z<|V(H')\setminus T|-1$ , the map $\phi$ is an embedding of the first z vertices of $H'-(T\cup \{x\})$ satisfying the conclusion of Claim 2. Let w be the $(z+1)$ st vertex of $H'-(T\cup\{x\})$ . We aim to show the existence of an embedding $\phi^{\prime}$ extending $\phi$ satisfying the conclusion of Claim 2 for $z+1$ .

To do this, it is enough to show that, for each statement among ( I2)–( I4) and ( L1)–( L3) separately, the number of vertices in $N_G\big(\Pi(w),C_w\big)$ which cause the given statement to fail is small compared to $\big|N_G\big(\Pi(w),C_w\big)\big|$ ; then we choose a vertex y in that set (so guaranteeing ( I1)) which causes none of the statements to fail, and have the desired embedding $\phi\cup\{w\to y\}$ . We therefore record some lower bounds on $\big|N_G\big(\Pi(w),C_w\big)\big|$ .

Suppose $d(x,w)\ge2$ and $d(x,w)+\rho'(w)\le s+1$ , or if $d(x,w)=1$ and w has two neighbours in $H'-x$ which come after w in $<_{\rho^{\prime}}$ . In the first case, by (6), we have $|\Pi(w)|\le\Delta-3$ . In the second case, since w has three neighbours in H ^′ which do not come before it in $<_{\rho^{\prime}}$ (as x is not in that order at all) we have $|\Pi(w)|\le\Delta-3$ . In either case, by ( I2), we get

(7) \begin{equation}\big|N_G\big(\Pi(w),C_w\big)\big|\ge\big(\tfrac{d'}{4}\big)^{\Delta-3}p^{\Delta-3}|C_w|\ge\big(\tfrac{d'}{4}\big)^{\Delta-3}p^{\Delta-2}\cdot\tfrac{\mu n}{4\ell t_1}\ge 100C\Delta^2p^{-2}\log n\,,\end{equation}

where the final inequality uses $p\ge C^*\big(\tfrac{\log n}{n}\big)^{1/\Delta}$ and the choice of $C^*$ . By a similar calculation, if either $d(x,w)=1$ and w has a neighbour coming after in in $<_{\rho^{\prime}}$ , or $d(x,w)+\rho'(w)>s+1$ and w has a neighbour coming after it in $<_{\rho^{\prime}}$ , we have

(8) \begin{equation}\big|N_G\big(\Pi(w),C_w\big)\big|\ge\big(\tfrac{d'}{4}\big)^{\Delta-1}p^{\Delta-1}\cdot\tfrac{\mu n}{4\ell t_1r}\ge 100C\Delta^2p^{-1}\log n\,.\end{equation}

Finally, if either $d(x,w)=1$ or $d(x,w)+\rho'(w)>s+1$ , we get

(9) \begin{equation}\big|N_G\big(\Pi(w),C_w\big)\big|\ge\big(\tfrac{d'}{4}\big)^{\Delta}p^{\Delta}\cdot\tfrac{\mu n}{4\ell t_1r}\ge 100C\Delta^2\log n\,.\end{equation}

We now estimate the fraction of $\big|N_G\big(\Pi(w),C_w\big)\big|$ which causes each of the desired statements to fail. The statement ( I2) can only fail for a neighbour u of w, and then only if we choose $y\in N_G\big(\Pi(w),C_w\big)$ which has too few neighbours in $N_G\big(\Pi(u),C_u\big)$ . But by ( I4) these two sets are on either side of a $\big(\nu^*_{|\Pi(w)|,|\Pi(u)|},d',p)_G$ -regular pair, and by ( I2) and ( I3) the latter covers more than a $\nu^*_{\Delta,\Delta}$ -fraction of $N_{\Gamma}\big(\Pi(u),C_u\big)$ . So by regularity, at most $\nu^*_{\Delta,\Delta}|N_{\Gamma}\big(\Pi(w),C_w\big)\big|$ vertices of $\big|N_G\big(\Pi(w),C_w\big)\big|$ can cause ( I2) to fail for u. Using ( I2) and ( I3), and summing over the at most $\Delta$ choices of u, we see that at most a $8^\Delta d'^{-\Delta}\Delta\nu^*_{\Delta,\Delta}$ -fraction of $\big|N_G\big(\Pi(w),C_w\big)\big|$ cause ( I2) to fail.

For ( I3), we note that embedding w can only cause this statement to fail if w has at least one neighbour in H ^′ coming after it in $<_{\rho^{\prime}}$ , and in this case by (7) and (8), we have $\big|N_G\big(\Pi(w),C_w\big)\big|\ge 100C\Delta^2p^{-1}\log n$ . Now a vertex $y\in N_G\big(\Pi(w),C_w\big)$ can only cause ( I3) to fail if it has the wrong number of neighbours in $N_{\Gamma}\big(\Pi(u),C_u\big)$ for some neighbour u of w. Because the good event of Proposition 17 occurs, this happens for at most $Cp^{-1}\log n$ vertices, and summing over the at most $\Delta$ choices of u, we see that at most a $\tfrac{1}{100}$ -fraction of $\big|N_G\big(\Pi(w),C_w\big)\big|$ cause ( I3) to fail.

For ( I4), we need to be a bit more careful. To start with, if there are no neighbours of w coming after w in $<_{\rho^{\prime}}$ , then no matter how we embed w we cannot make ( I4) fail. Suppose first that there are neighbours of w coming after w in $<_{\rho^{\prime}}$ , but that no two such neighbours are adjacent. As above, by (7) and (8), we have $\big|N_G\big(\Pi(w),C_w\big)\big|\ge 100C\Delta^2p^{-1}\log n$ . By ( I4), a vertex $y\in N_G\big(\Pi(w),C_w\big)$ can only cause ( I4) to fail for a given u,u ^′ if u is a neighbour of w and u ^′ is not, and y is one of the at most $Cp^{-1}\log n$ vertices which fail to inherit regularity, as guaranteed by the good event of Lemma 14. Summing over the at most $\Delta^2$ choices of u,u ^′, we see that in this case at most a $\tfrac{1}{100}$ -fraction of $\big|N_G\big(\Pi(w),C_w\big)\big|$ cause ( I4) to fail. The remaining case is that there are two adjacent neighbours of w coming after w in $<_{\rho^{\prime}}$ . In this case, we need the good events of Lemmas 14 and 15, and consequently for given u,u ^′ up to $Cp^{-2}\log n$ vertices might fail to inherit regularity. But in this case by (7) we have $ \big|N_G\big(\Pi(w),C_w\big)\big|\ge 100C\Delta^2p^{-2}\log n$ , and again in this case at most a $\tfrac{1}{100}$ -fraction of $\big|N_G\big(\Pi(w),C_w\big)\big|$ cause ( I4) to fail.

The proofs that at most a $\tfrac{1}{100}$ -fraction of $\big|N_G\big(\Pi(w),C_w\big)\big|$ cause any one of ( L1)–( L3) are essentially identical, and we omit the details.

Summing up, by choice of $\nu^*_{\Delta,\Delta}$ and since $|V(H')|\le\sum_{i=0}^{s+1}\Delta^i$ , we see that at least half of $\big|N_G\big(\Pi(w),C_w\big)\big|$ consists of vertices y such that $\phi\cup\{w\to y\}$ satisfies the conclusions of Claim 2 for $z+1$ , completing the induction step and hence the proof of the claim.

Now we can conclude the proof of Lemma 25. Given an embedding of $H'-(T\cup\{x\})$ satisfying the conclusions of Claim 2, we extend it to an embedding $\phi$ of $H'-T$ by setting $\phi(x) = v$ . This is a valid embedding since we embedded all neighbours of x to W, and we obtain ( P1’). Property ( P2’) holds by choice of the $q_1,\dots,q_{k}$ . For every vertex u in T we have that $C_u = V_{q_{\rho'(u)},j_{\rho'(u)}}$ and $|C_u| \ge |{V_{q_{\rho'(u)}}}\cap V({G^{\,\prime}})|/{2 t_1}$ . So by the choice of $\zeta$ , ( P4’) follows from ( I2). The choice of constants ensures that the remaining statements in the lemma are a direct consequence of ( L1)–( L3).

5. Proof of the main technical result

The proof of Theorem 22 is broadly similar to the proof of [Reference Allen, Böttcher, Ehrenmüller and Taraz1, Theorem 23]. Again, basically the idea is that we apply the lemmas of Section 3 in order to first find a well-behaved partition of G and a corresponding partition of H. We then deal with the few badly behaved vertices of G by sequentially pre-embedding onto them some vertices of H whose neighbourhoods contain at most s colours. Lemma 25 deals with this pre-embedding, and sets up for the vertices which are not pre-embedded but which have pre-embedded neighbours restriction sets in the sense of Definition 11. We then adjust the partition of H to fit this pre-embedding, and balance the partition of G to match. Finally, we see that the conditions of Lemma 13 are met, and that lemma completes the desired embedding of H in G.

As in [Reference Allen, Böttcher, Ehrenmüller and Taraz1], there are two slightly subtle points. The first is that for $\Delta=2$ we can have $Cp^{-2}>pn$ , so that we should be worried that we come to some badly behaved vertex of G onto which we wish to pre-embed and discover that all its neighbours have already been used in pre-embedding. As in [Reference Allen, Böttcher, Ehrenmüller and Taraz1], this is easy to handle: at each step we choose the badly behaved vertex with most neighbours already embedded to. It is easy to check that this ordering avoids the above problem. The second, more serious, problem is that we need restriction sets fulfilling the conditions of Definition 11. Although Lemma 25 gives us pre-embeddings satisfying these conditions, we might destroy the conditions when we pre-embed later vertices. The condition we could destroy is simply that we need each restriction set to be reasonably large; the danger is that we pre-embed many vertices to some restriction set. The solution to this is (as in [Reference Allen, Böttcher, Ehrenmüller and Taraz1]) to select a set S, whose size is linear in n but small, using Lemma 20 to avoid large intersections with any possible restriction set. When we apply Lemma 25 to cover a badly-behaved vertex v, we will pre-embed to v and to some vertices chosen from S, and not to any other vertex. The badly behaved vertices are not (by construction) in any restriction set, while S has small intersection with all restriction sets, so that even removing all of S would not make the restriction sets too small.

The only point in the proof where we really need to do more than in [Reference Allen, Böttcher, Ehrenmüller and Taraz1] (apart from using Lemma 25 to pre-embed) is that we need to ensure the conditions of Lemma 25 are met. When we wish to cover a badly-behaved v, its neighbourhood within the set S must contain many copies of $K_s$ . Further, some vertices of S will have been used in earlier pre-embeddings, and we need to ensure that these used vertices do not hit too many of the copies of $K_s$ . For this, we apply the sparse regularity lemma, Lemma 10, to $G\big[N_G(v)\big]$ before choosing S. We will see that (since $N_G(v)$ contains many copies of $K_s$ ) we find a set of s clusters in $N_G(v)$ such that all the pairs are relatively dense and regular. When we use Lemma 20 to choose S, we also insist that S contains a significant fraction of each of these clusters. The order in which we cover badly behaved vertices ensures that a (slightly smaller but still) significant fraction of each cluster is not used by the previous pre-embedding; and we find the desired many copies of $K_s$ in $N_G(v)\cap S$ as a result.

As a final observation, Lemma 25 ( P4’) gives us something which looks like an image restriction set suitable for Definition 11—but it is a subset of S. A careful reader will see from the constant choices below that it is therefore too small for Lemma 13. However, the fact that S is selected at random allows us to deduce the existence of a larger image restriction set which is suitable for Lemma 13.

Proof of Theorem 22. Given $\unicode[Times]{x03B3}>0$ , we set $d^+=2^{-s-5}\unicode[Times]{x03B3}$ and $\varepsilon^+_{s-2}=16^{-s}(d^+)^{2s}/s$ . For each $i=s-3,s-4,\ldots,0$ sequentially, let $0<\varepsilon^+_i\le \varepsilon^+_{i-1}$ be sufficiently small for Lemma 15 with input $d^+$ and $\varepsilon^+_{i+1}$ . Let $\varepsilon^+\le\varepsilon^+_0$ be small enough for an application of Lemma 20 with input $d^+$ and $\varepsilon^+_0$ . Let $t_1^+$ be returned by Lemma 10 for input $\varepsilon^+$ and $\lceil1/d^+\rceil$ , and let $\alpha^+=\tfrac14d^+/t_1^+$ . Let $\unicode[Times]{x03B3}^+=2^{-4s^2}(d^+)^{-2s^2}(t_1^+)^{-s}$ . Note we have $\unicode[Times]{x03B3}^+<\unicode[Times]{x03B3}$ .

We now choose $d \le \frac{\unicode[Times]{x03B3}^+}{32}$ not larger than the d given by Lemma 23 for input $\unicode[Times]{x03B3}$ , k and $r_0\;:\!=\;10^5\unicode[Times]{x03B3}^{-1}$ . We let $\alpha$ be the $\zeta$ returned by Lemma 25 for input $\Delta$ , k, s, $\unicode[Times]{x03B3}^+$ and d. We set $D=\Delta$ and let $\varepsilon_{BL}$ be returned by Lemma 13 for input $\Delta$ , $\Delta_{R'}=3k$ , $\Delta_J=\Delta$ , $\vartheta=\tfrac{1}{100D}$ , $\zeta=\tfrac{1}{4}\alpha$ , d and $\kappa=64$ . Next, putting $\varepsilon^{\ast}\;:\!=\;\tfrac18\varepsilon_{BL}$ into Lemma 25 (with earlier parameters as above) returns $\varepsilon_0>0$ . We set $\varepsilon=\min(\varepsilon_0,d,\varepsilon^*/4\Delta,1/100k)$ , and set $\varepsilon^-\le\varepsilon$ small enough for Lemma 20 with input as above and $d,\varepsilon$ . Now Lemma 23, for input $\varepsilon^-$ and earlier constants as above, returns $r_1$ . At last, Lemma 26, for input k, $r_1$ , $\Delta$ , $\unicode[Times]{x03B3}$ , d and $8\varepsilon$ , returns $\xi>0$ . Without loss of generality, we may assume $\xi<10(10kr_1)$ , and set $\beta=10^{-12}\xi^2/(\Delta k^4 r_1^2)$ . Let $\mu=\varepsilon^2/(100000kr_1)$ . Next, suppose $C^{\ast}$ is large enough for Lemma 25, and also to play the rôle of C in each of these other lemmas, and also for Proposition 17 with input $\varepsilon$ , for Lemma 15 with input $d^+$ and each of $\varepsilon^+_i$ for $i=1,\ldots,s-2$ , and for Lemma 20 with input $\varepsilon\mu^2$ , $\varepsilon$ , $\min(d,d^+)$ and $\Delta$ .

We set $C=10^{100}k^2 r_1^2 \varepsilon^{-2}\xi^{-1}\Delta^{1000k^3}\mu^{-\Delta}C^{\ast}$ and $z=10/\xi$ . Given $p\ge C\big(\tfrac{\log}{n}\big)$ , a.a.s. $\Gamma=G(n,p)$ satisfies the good events of each of the lemmas and propositions listed above with each of the specified inputs.

In addition, for each set W of at most $\Delta$ vertices of G(n,p), the size of the common neighbourhood $N_{G(n,p)}(W)$ is distributed as a binomial random variable with mean $p^{|W|}(n-|W|)$ . By Theorem 18, the probability that the outcome is $(1\pm\varepsilon)p^{|W|}n$ is at least $1-n^{-(\Delta+1)}$ for sufficiently large n. By the union bound, we conclude that a.a.s. G(n,p) satisfies

(10) \begin{equation} \text{for each $W\subset V\big(G(n,p)\big)$ with $|W|\le\Delta$ we have }\big|N_{G(n,p)}(W)\big|=(1\pm\varepsilon)p^{|W|}n\,.\end{equation}

Suppose that $\Gamma=G(n,p)$ satisfies these good events. Let G be a spanning subgraph of $\Gamma$ such that $\delta(G)\ge\big(\tfrac{k-1}{k}+\unicode[Times]{x03B3}\big)pn$ and such that for each $v\in V(G)$ the neighbourhood $N_G(v)$ contains at least $\delta p^{\binom{s}{2}}(pn)^s$ copies of $K_s$ . Let H be a graph on n vertices with $\Delta(H)\le\Delta$ . Let $\sigma$ be a proper colouring of V(H) using colours $\{0,\dots,k\}$ , and let ${\mathcal L}$ be a labelling of V(H) with bandwidth at most $\beta n$ with the following properties. The colouring $\sigma$ is $(z,\beta)$ -zero-free with respect to ${\mathcal L}$ , the first $\sqrt{\beta}n$ vertices of ${\mathcal L}$ do not use the colour zero, and the first $\beta n$ vertices of ${\mathcal L}$ contain $Cp^{-2}$ vertices whose neighbourhood contains only s colours.

We now claim that for each $v\in V(G)$ we can find s large subsets of $N_G(v)$ all pairs of which are dense and regular in G. This forms a ‘robust witness’ that each vertex neighbourhood in G contains many copies of $K_{s}$ .

Proof. We apply Lemma 10 with input $\varepsilon^+$ and $\lceil 1/d^+\rceil$ to $G\big[N_G(v)\big]$ , with an arbitrary equipartition into $\lceil 1/d^+\rceil$ sets as an initial partition. Note that the conditions of Lemma 10 are satisfied because the good event of Proposition 17 holds. We obtain an $(\varepsilon,p)$ -regular partition of $N_G(v)$ whose non-exceptional parts are of size between $\alpha^+pn$ and $8\alpha^+pn$ , by choice of $\alpha^+$ and since $\big|N_G(v)\big|>\tfrac12pn$ . If there exist s parts in this partition all pairs of which form $(\varepsilon^+,d^+,p)$ -regular pairs, then these parts form the desired $Q_{v,1},\cdots\!,Q_{v,s}$ . So we may assume for a contradiction that no such s parts exist. It follows that when we delete all edges within parts, meeting the exceptional sets, in irregular pairs, and in pairs of density less than $d^+p$ , we remove all copies of $K_s$ from $G\big[N_G(v)\big]$ .

The total number of such edges is, since the good event of Proposition 17 holds, at most

\begin{align*} (d^+)^{-1}\cdot 8p^3n^2(d^+)^{2}+2p(2\varepsilon^+pn)(2pn)+4\varepsilon^+p^3n^2+4d^+p^3n^2&\le (12\varepsilon^++12d^+)p^3n^2\\ &\le 2^{-s}\unicode[Times]{x03B3} p^3n^2\,, \end{align*}

where the final inequality is by choice of $d^+$ and $\varepsilon^+$ . We now estimate simply how many copies of $K_{s+1}$ a given edge e, together with v, can make in $\Gamma$ . Since by (10) any $\ell$ -tuple of vertices of $\Gamma$ has at most $2p^\ell n$ common neighbours, the number of copies of $K_4$ containing e and v is at most $2p^3n$ , and inductively the number of copies of $K_{s+1}$ containing e and v is at most

\begin{equation*}\prod_{\ell=3}^{s}2p^\ell n=2^{s-2}p^{\binom{s+1}{2}-3}n^{s-2}\,.\end{equation*}

Putting these estimates together we see that the total number of copies of $K_s$ in $G\big[N_G(v)\big]$ is at most $\tfrac12\unicode[Times]{x03B3} p^{\binom{s+1}{2}}n^{s}$ . This is the desired contradiction, completing the proof.

We apply Lemma 23 to G, with input $\unicode[Times]{x03B3}$ , k, $r_0$ and $\varepsilon^-$ , to obtain an integer r with $10\unicode[Times]{x03B3}^{-1}\le kr\le r_1$ , a set $V_0\subset V(G)$ with $|V_0|\le C^\ast p^{-2}$ , a k-equitable partition ${\mathcal V}=\big\{V_{i,j}\big\}_{i\in[r],j\in[k]}$ of $V(G)\setminus V_0$ , and a graph $R^k_r$ on $[r]\times[k]$ with minimum degree $\delta(R^k_r)\ge\big(\tfrac{k-1}{k}+\tfrac{\unicode[Times]{x03B3}}{2}\big)kr$ , such that $K^k_r\subset B^k_r\subset R^k_r$ and such that the following hold.