# Canonical colourings in random graphs

Nina Kamčev  Department of Mathematics, Faculty of Science, University of
Zagreb, Croatia<EMAIL_ADDRESS>and  Mathias Schacht  Fachbereich
Mathematik, Universität Hamburg, Hamburg, Germany<EMAIL_ADDRESS>Dedicated to Martin Aigner on the occasion of his 80th birthday

###### Abstract.

Rödl and Ruciński [_Threshold functions for Ramsey properties_ , J. Amer.
Math. Soc. 8 (1995)] established Ramsey’s theorem for random graphs. In
particular, for fixed integers $r$, $\ell\geq 2$ they showed that
$\hat{p}_{K_{\ell},r}(n)=n^{-\frac{2}{\ell+1}}$ is a threshold for the Ramsey
property that every $r$-colouring of the edges of the binomial random graph
$G(n,p)$ yields a monochromatic copy of $K_{\ell}$. We investigate how this
result extends to arbitrary colourings of $G(n,p)$ with an unbounded number of
colours. In this situation Erdős and Rado [_A combinatorial theorem_ , J.
London Math. Soc. 25 (1950)] showed that canonically coloured copies of
$K_{\ell}$ can be ensured in the deterministic setting. We transfer the
Erdős–Rado theorem to the random environment and show that for $\ell\geq 4$
both thresholds coincide. As a consequence, the proof yields $K_{\ell+1}$-free
graphs $G$ for which every edge colouring contains a canonically coloured
$K_{\ell}$.

The $0$-statement of the threshold is a direct consequence of the
corresponding statement of the Rödl–Ruciński theorem and the main contribution
is the $1$-statement. The proof of the $1$-statement employs the transference
principle of Conlon and Gowers [_Combinatorial theorems in sparse random sets_
, Ann. of Math. (2) 184 (2016)].

###### Key words and phrases:

Random graphs, thresholds, Ramsey’s theorem, canonical colourings

###### 2020 Mathematics Subject Classification:

05C80 (primary), 05D10, 05C55 (secondary)

The research was supported through the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie Action RobSparseRand
101038085 and by the ERC Consolidator Grant PEPCo 724903.

##  1\. Introduction

In the last three decades, extremal and Ramsey-type properties of random
graphs were considered, which led to several general approaches (see, e.g.
[bms15, cg16, klr97, nenadov21, rr95, st15, schacht16] and the references
therein). We consider Ramsey-type questions for the binomial random graph
$G(n,p)$. For graphs $G$ and $H$ and an integer $r\geq 2$ we write

$G\longrightarrow(H)_{r}$

to signify the statement that every $r$-colouring of the edges of $G$ yields a
monochromatic copy of $H$. Ramsey’s theorem [r30] tells us that for fixed $H$
and $r$ the family of graphs $G$ with $G\longrightarrow(H)_{r}$ is non-empty.
Obviously, this family is monotone and, hence, there is a threshold function
$\hat{p}_{H,r}\colon\mathds{N}\longrightarrow[0,1]$ such that

$\lim_{n\longrightarrow\infty}\mathds{P}\big{(}G(n,p)\longrightarrow(H)_{r}\big{)}=\begin{cases}0\,,&\text{if
$p\ll\hat{p}_{H,r}$,}\\\ 1\,,&\text{if $p\gg\hat{p}_{H,r}$.}\end{cases}$ (1.1)

As usual we shall refer to any such function as the threshold of that
property, even though it is not unique.

Rödl and Ruciński [rr93, rr95] determined the threshold $\hat{p}_{H,r}$ for
every graph $H$ and every fixed number of colours $r$. We restrict ourselves
to the situation when $H$ is a clique $K_{\ell}$ and state their result for
that case only.

######  Theorem 1.1 (Rödl & Ruciński).

For every $r\geq 2$ and $\ell\geq 3$ we have
$\hat{p}_{K_{\ell},r}(n)=n^{-\frac{2}{\ell+1}}$.∎

In fact, Rödl and Ruciński established a _semi-sharp_ threshold, i.e., the
$0$-statement in (1.1) holds as long as $p(n)\leq
c_{\ell,r}n^{-\frac{2}{\ell+1}}$ for some sufficiently small constant
$c_{\ell,r}>0$ and, similarly, the $1$-statement becomes true already if
$p(n)\geq C_{\ell,r}n^{-\frac{2}{\ell+1}}$ for some $C_{\ell,r}$. This was
sharpened recently in [fkss], where the gap between $c_{\ell,r}$ and
$C_{\ell,r}$ was closed. Perhaps surprisingly, the asymptotic growth of the
threshold function $\hat{p}_{K_{\ell},r}(n)$ in Theorem 1.1 is independent of
the number of colours $r$.

We are interested in arbitrary edge colourings of $G(n,p)$, i.e., colourings
which are not restricted to a fixed number of colours. However, if the number
of colours is unrestricted, then this allows injective edge colourings and,
consequently, monochromatic (nontrivial) subgraphs might be prevented. Erdős
and Rado [er50], however, showed that certain _canonical_ patterns are
unavoidable in edge colourings of sufficiently large cliques. Obviously, the
monochromatic and the injective pattern must be canonical. Two more canonical
patterns arise by ordering the vertices of $K_{n}$ and colouring every edge
$uv$ by $\min\\{u,v\\}$ or colouring every edge by its maximal vertex. More
generally, for finite graphs $G$ and $H$ with ordered vertex sets we write

$G\mathrel{\mathop{\longrightarrow}\limits^{\vbox
to0.0pt{\kern-2.1pt\hbox{$\scriptstyle*\hskip 1.0pt$}\vss}}}(H)$

if for every edge colouring $\varphi\colon E(G)\longrightarrow\mathds{N}$
there exists an order-preserving graph embedding $\varsigma\colon
H\longrightarrow G$ such that one of the following holds:

  1. ( )

the copy $\varsigma(H)$ of $H$ is monochromatic under $\varphi$,

  2. ( )

or $\varphi$ restricted to $E(\varsigma(H))$ is injective,

  3. ( )

or for all edges $e$, $e^{\prime}\in E(\varsigma(H))$ we have
$\varphi(e)=\varphi(e^{\prime})\ \Longleftrightarrow\
\min(e)=\min(e^{\prime})$,

  4. ( )

or for all edges $e$, $e^{\prime}\in E(\varsigma(H))$ we have
$\varphi(e)=\varphi(e^{\prime})\ \Longleftrightarrow\
\max(e)=\max(e^{\prime})$.

We call an ordered copy of $H$ in $G$ _canonical_ if it displays one of the
four patterns described in ( ) ‣ 1–( ) ‣ 1.

Note that for the patterns described in ( ) ‣ 1 and ( ) ‣ 1 the orderings of
the vertex sets have no bearing. Moreover, we shall refer to copies enjoying
an injective colouring as _rainbow_ copies of $H$ (even if $|E(H)|\neq 7$).
Similarly, we refer to the patterns appearing in ( ) ‣ 1 and ( ) ‣ 1 as _min-
coloured_ and _max-coloured_ , respectively. In case only the backward
implications in ( ) ‣ 1 or ( ) ‣ 1 are enforced, then we refer to those
colourings as _non-strict_ , e.g., if $\min(e)=\min(e^{\prime})$ yields
$\varphi(e)=\varphi(e^{\prime})$ for all edges $e$, $e^{\prime}\in
E(\varsigma(H))$, then $\varsigma(H)$ is a non-strictly min-coloured copy of
$H$. Obviously, monochromatic copies are also non-strictly min- and max-
coloured.

From now on, the vertex sets of all graphs considered are ordered. In
particular, for cliques and random graphs we simply assume

$V(K_{n})=[n]\qquad\text{and}\qquad V(G(n,p))=[n]\,.$

With this notation at hand, the aforementioned canonical Ramsey theorem of
Erdős and Rado [er50] restricted to the graph case asserts that canonical
copies are unavoidable.

######  Theorem 1.2 (Erdős & Rado).

For every $\ell\geq 3$, there exists $n$ such that
$K_{n}\mathrel{\mathop{\longrightarrow}\limits^{\vbox
to0.0pt{\kern-2.1pt\hbox{$\scriptstyle*\hskip 1.0pt$}\vss}}}(K_{\ell})$.∎

We are interested in a common generalisation of Theorems 1.1 and 1.2. Owing to
Theorem 1.2, for any ordered graph $H$, the monotone family $\\{G\colon
G\mathrel{\mathop{\longrightarrow}\limits^{\vbox
to0.0pt{\kern-2.1pt\hbox{$\scriptstyle*\hskip 1.0pt$}\vss}}}(H)\\}$ is non-
empty and it raises the problem of estimating the threshold
$\hat{p}_{H}\colon\mathds{N}\longrightarrow[0,1]$ such that

$\lim_{n\longrightarrow\infty}\mathds{P}\big{(}G(n,p)\mathrel{\mathop{\longrightarrow}\limits^{\vbox
to0.0pt{\kern-2.1pt\hbox{$\scriptstyle*\hskip
1.0pt$}\vss}}}(H)\big{)}=\begin{cases}0\,,&\text{if $p\ll\hat{p}_{H}$,}\\\
1\,,&\text{if $p\gg\hat{p}_{H}$.}\end{cases}$ (1.2)

It follows from the definition, that for every graph $H$ not admitting a
vertex cover of size at most two, the only canonical colourings of $H$ using
at most two colours are monochromatic. Consequently,

$\hat{p}_{H}\geq\hat{p}_{H,2}$

for every such graph $H$. In particular, for cliques on at least four vertices
this may suggest that the asymptotics of the thresholds for those Ramsey
properties coincide and our main result verifies this.

######  Theorem 1.3.

For every $\ell\geq 4$, there exists $C>0$ such that for $p=p(n)\geq
Cn^{-\frac{2}{\ell+1}}$ we have

$\lim_{n\longrightarrow\infty}\mathds{P}\big{(}G(n,p)\mathrel{\mathop{\longrightarrow}\limits^{\vbox
to0.0pt{\kern-2.1pt\hbox{$\scriptstyle*\hskip
1.0pt$}\vss}}}(K_{\ell})\big{)}=1\,.$

Combining Theorem 1.3 with the corresponding lower bound on
$\hat{p}_{K_{\ell},2}$ shows that the threshold for the canonical Ramsey
property is semi-sharp for $\ell\geq 4$. For $\ell=3$ we recall that the
canonical Ramsey threshold is indeed smaller than the Ramsey threshold
$n^{-1/2}$. In fact, one can check that every edge colouring of $K_{4}$ yields
a canonical copy of the triangle and, hence, $\hat{p}_{K_{3}}\leq n^{-2/3}$.

Moreover, we note that for $p=O(n^{-\frac{2}{\ell+1}})$ the random graph
$G(n,p)$ is likely to contain only $o(pn^{2})$ cliques $K_{\ell+1}$. In the
proof of Theorem 1.3 we can delete an edge from each such substructure.
Consequently, we obtain the following consequence in structural Ramsey theory,
which can be viewed as a Folkman-type extension of the Erdős–Rado theorem for
graphs.

######  Corollary 1.4.

For every $\ell\geq 4$ there exists a $K_{\ell+1}$-free graph $G$ such that
$G\mathrel{\mathop{\longrightarrow}\limits^{\vbox
to0.0pt{\kern-2.1pt\hbox{$\scriptstyle*\hskip 1.0pt$}\vss}}}(K_{\ell})$.
Moreover, $G$ contains no two distinct copies of $K_{\ell}$ that share at
least three vertices.

In the context of Ramsey’s theorem, the existence of such a graph $G$ was
asked for by Erdős and Hajnal [eh67]; for two colours this was established by
Folkman [f70], and for any fixed number of colours by Nešetřil and Rödl
[nr76]. The graph $G$ in Corollary 1.4 will be obtained by modifying the
random graph and, hence, the proof is non-constructive. Reiher and Rödl [rr]
pointed out that the first part of Corollary 1.4 can also be proved in a
constructive manner by means of the _partite construction method_ of Nešetřil
and Rödl [nr81]. While this approach falls short to exclude $K_{\ell}$’s
intersecting in triangles, it has the advantage that it readily extends to
$k$-uniform hypergraphs for every $k\geq 3$.

We conclude this introduction with a short overview of the main ideas of the
proof of Theorem 1.3. Roughly speaking, the proof is inspired by the proof of
the canonical graph Ramsey theorem laid out by Lefmann and Rödl [lr95] and
Alon et al. [ajmp03]. This approach pivots on a case distinction of the edge
colouring of the underlying graph $K_{n}$. The first case, when many different
colours appear everywhere, which is captured by assuming that every vertex is
incident to only $o(n)$ edges of the same colour, leads to rainbow copies of
$K_{\ell}$. In the other case, there is a vertex with a monochromatic
neighbourhood of size $\Omega(n)$, which by iterated applications, as in the
standard proof of Ramsey’s theorem, leads to a non-strictly min- or max-
coloured $K_{(\ell-2)^{2}+2}$. Such a non-strictly min/max-coloured clique
contains a canonical $K_{\ell}$ by a straightforward application of
Dirichlet’s box principle.

Transferring such an approach from $K_{n}$ to $G(n,p)$ for
$p=O(n^{-\frac{2}{\ell+1}})$ faces several challenges. Firstly, we shall not
use a $K_{(\ell-2)^{2}+2}$ in the coloured host graph, as such large cliques
are not very likely to appear in $G(n,p)$ for that edge probability. Moreover,
in the more challenging second case, when the colouring is unbounded, it is
certainly not sufficient to consider one vertex with a large monochromatic
neighbourhood (of size $\Omega(pn)$), as again, this neighbourhood is too
sparse to contain any useful structure in $G(n,p)$. Thus we resort to a robust
version of the above-mentioned argument, building a large non-strictly min- or
max-coloured subgraph which contains $\Omega(p^{2}n)$ edges.

The bounded case, with at most $\lambda$ edges of every colour incident to any
given vertex of $G(n,p)$, is a problem of independent interest. For example,
$\lambda=1$ corresponds to studying proper edge colourings of $G(n,p)$ and
anti-Ramsey properties (see, e.g. [kkm14, npss17, kmps19] and the references
therein). In fact, for $\ell\geq 5$, there are proper colourings of $G(n,p)$
with $p=cn^{-\frac{2}{\ell+1}}$ which do not contain a rainbow copy of
$K_{\ell}$ (see [kmps19]), which is an alternative argument for
$\hat{p}_{K_{\ell}}\geq cn^{-\frac{2}{\ell+1}}$ and another obstruction for
Theorem 1.3. For the proof of Theorem 1.3 presented here, we will need to
guarantee rainbow copies of $H$ under the weaker assumption that
$\lambda=o(pn)$. This can be viewed as a partial extension of the work of
Kohayakawa, Kostadinidis, and Mota [kkm14]. In both cases (bounded and
unbounded colourings) the transference principle for random discrete
structures developed by Conlon and Gowers [cg16] is an integral part of the
proof.

### Organisation

In the next section, we present the two main lemmata rendering the case
distinction sketched above, and deduce Theorem 1.3. The proofs of these
lemmata are deferred to Sections 3 and 4, along with the corresponding
preliminaries. We conclude with a discussion of possible generalisations of
this work from cliques $K_{\ell}$ to general graphs $H$ and of related open
problems in Section 5.

##  2\. Proof of the main result

###  2.1. Proof of the canonical Ramsey theorem for graphs

The proof of Theorem 1.3 adopts some ideas of the canonical Ramsey theorem for
graphs from the work of Lefmann and Rödl [lr95] and Alon et al. [ajmp03] and
below we recall their argument. For $\ell\geq 3$ we fix

$\delta=\frac{1}{4\ell^{3}}\quad\text{and}\quad n\geq
2^{6\ell^{2}(\log_{2}(\ell)+1)}$ (2.1)

and first we consider bounded colourings $\varphi\colon
E(K_{n})\longrightarrow\mathds{N}$. We say such a colouring is _$\delta$
-bounded_ if for every colour $c\in\mathds{N}$ and every vertex $v\in
V(K_{n})$ we have

$d_{c}(v)=\big{|}N_{c}(v)\big{|}=\big{|}\\{w\in
V(K_{n})\colon\varphi(vw)=c\\}\big{|}\leq\delta n\,.$

Roughly speaking, bounded colourings have the property that many different
colours are “present everywhere” and this yields rainbow copies of $K_{\ell}$.
In fact, a simple counting argument shows for $\delta$-bounded colourings that
at most $\delta n^{3}/2$ triples contain two edges of the same colour and at
most $\delta n^{4}/8$ quadruples contain two disjoint edges of the same
colour. Consequently, selecting every vertex of $K_{n}$ independently with
probability $2\ell/n$ and removing a vertex from every such triple and every
such quadruple, establishes the existence of $\ell$ vertices inducing a
rainbow $K_{\ell}$.

The second part of the proof resembles the standard proof of Ramsey’s theorem
for graphs and iterates along large monochromatic neighbourhoods. Given the
observation above for bounded colourings, we may assume that the edge
colouring $\varphi$ is unbounded in a hereditary way and this requires the
exponential lower bound on $n$ above.

More precisely, assuming that $\varphi$ fails to induce a rainbow copy of
$K_{\ell}$ gives rise to a vertex $v\in V(K_{n})$, a colour $c$, and a
comparability sign $\diamond\in\\{<\,,>\\}$ such that

$d^{\diamond}_{c}(v)=\big{|}N^{\diamond}_{c}(v)\big{|}=\big{|}\\{w\in
V(K_{n})\colon\varphi(vw)=c\ \text{and}\ v\diamond w\\}\big{|}>\frac{\delta
n}{2}\,.$

Restricting our attention to the colouring $\varphi$ on the edges contained in
$N^{\diamond}_{c}(v)$ and iterating this argument $L=2(\ell-2)^{2}+2$ times
leads to a sequence $(v_{i},c_{i},\diamond_{i})_{i\in[L]}$ such that for every
$i\in[L]$ we have

$\bigg{|}\bigcap_{j=1}^{i}N^{\diamond_{j}}_{c_{j}}(v_{j})\bigg{|}>\Big{(}\frac{\delta}{2}\Big{)}^{i}n\,.$
(2.2)

In fact, owing to the choices in (2.1) we can iterate this step $L$ times.

Furthermore, we may assume that there are indices $1\leq
i_{0}<\dots<i_{(\ell-2)^{2}}<L$ such that $\diamond_{i_{j}}$ is $<$ for all
$j$. Consequently, the correspondingly indexed vertices
$v_{i_{0}},\dots,v_{i_{(\ell-2)^{2}}}$ together with $v_{L}$ induce a non-
strictly min-coloured clique on $(\ell-2)^{2}+2$ vertices. Finally, if one of
the colours appears $\ell-1$ times among
$c_{i_{0}},\dots,c_{i_{(\ell-2)^{2}}}$, then this yields a monochromatic
$K_{\ell}$ among $v_{i_{0}},\dots,v_{i_{(\ell-2)^{2}}}$, and $v_{L}$.
Otherwise, at least $\ell-1$ distinct colours appear and we are guaranteed to
find a min-coloured $K_{\ell}$ instead.

###  2.2. Bounded and unbounded colourings in random graphs

For the proof of Theorem 1.3 we derive appropriate random versions of the
facts above that analyse bounded and unbounded colourings of $G(n,p)$ (see
Lemmata 2.1 and 2.2 below). We begin by defining a notion of boundedness
central to our proof. Roughly speaking, an edge colouring of $G(n,p)$ is
bounded if at most $o(pn)$ edges of the same colour are incident to any given
vertex. However, similar to the proof in the deterministic setting, it will be
useful to define this property for large subsets of vertices, which is made
precise as follows.

Given a graph $G=(V,E)$ with an edge colouring $\varphi\colon
E\longrightarrow\mathds{N}$, a subset $U\subseteq V$, and reals $\delta>0$,
$p\in(0,1]$ we say $\varphi$ is _$(\delta,p)$ -bounded on $U$_ if for every
colour $c\in\mathds{N}$ and every vertex $u\in U$ we have

$d_{c}(u,U)=\big{|}N_{c}(u,U)\big{|}=\big{|}\\{w\in
U\colon\varphi(uw)=c\\}\big{|}\leq\delta p|U|\,.$

The first lemma asserts that bounded edge colourings of $G(n,p)$ for $p\gg
n^{-\frac{2}{\ell+1}}$ yield rainbow copies of $K_{\ell}$ asymptotically
almost surely, i.e., with probability tending to $1$ as
$n\longrightarrow\infty$. In view of Corollary 1.4, we define the _$\ell$
-clean_ subgraph $G_{\ell}$ of a given graph $G$ on $[n]$ as follows: Consider
all edges of $G$ in lexicographic order and remove an edge $e$ in the current
subgraph of $G$, if the edge $e$ is contained in two distinct $K_{\ell}$’s
intersecting in at least three vertices. Actually, the precise definition is
not relevant for our argument, but it will be convenient that this way the
$\ell$-clean subgraph $G_{\ell}\subseteq G$ is unique. Note that $G_{\ell}$
contains no copy of $K_{\ell+1}$, since this would yield two $K_{\ell}$’s
intersecting in $\ell-1$ vertices. We emphasise that throughout the paper (in
particular, in Lemma 2.1 and Lemma 2.2), $d_{c}(u,U)$ and similar notation
refers to the edges incident to $u$ in the original graph $G$, and not in the
$\ell$-clean subgraph $G_{\ell}$.

######  Lemma 2.1.

For all integers $\ell\geq 4$ and every $\nu>0$ there is some constant $C>0$
such that for $p=p(n)\geq Cn^{-\frac{2}{\ell+1}}$ asymptotically almost surely
the following holds for $G\in G(n,p)$.

If $\varphi\colon E(G)\longrightarrow\mathds{N}$ is $(\ell^{-5}/4,p)$-bounded
on some $U\subseteq V(G)$ with $|U|\geq\nu n$, then $U$ induces a rainbow copy
of $K_{\ell}$ in $G$.

Moreover, if in addition we have $p(n)\leq
n^{-\frac{2\ell-2}{\ell^{2}+\ell-4}}/\omega(n)$ for some arbitrary function
$\omega$ tending to infinity as $n\longrightarrow\infty$, then the
$\ell$-clean subgraph $G_{\ell}\subseteq G$ also contains a rainbow copy of
$K_{\ell}$.

Lemma 2.1 strengthens a result of Kohayakawa, Kostadinidis, and Mota [kkm14],
where a more restrictive boundedness assumption is required. The proof of
Lemma 2.1 makes use of the transference principle of Conlon and Gowers [cg16],
which allows us to transfer the bounded case in the deterministic setting to
the random environment. We defer the proof of Lemma 2.1 to Section 3. The
second lemma yields canonical copies in unbounded colourings.

######  Lemma 2.2.

For all integers $\ell\geq 3$ and every $\delta>0$ there is some constant
$C>0$ such that for $p=p(n)\geq Cn^{-\frac{2}{\ell+1}}$ asymptotically almost
surely the following holds for $G\in G(n,p)$.

If $\varphi\colon E(G)\longrightarrow\mathds{N}$ has the property that every
$U\subseteq V(G)$ with size $|U|\geq\delta^{5\ell^{2}}n$ satisfies

$\big{|}\\{u\in U\colon d_{c}(u,U)\geq 8\delta p|U|\text{ for some colour
}c\\}\big{|}\geq\frac{|U|}{2}\,,$ (2.3)

then $G$ contains a canonical copy of $K_{\ell}$.

Moreover, if in addition we have $p(n)\leq
n^{-\frac{2\ell-2}{\ell^{2}+\ell-4}}/\omega(n)$ for some arbitrary function
$\omega$ tending to infinity as $n\longrightarrow\infty$, then the
$\ell$-clean subgraph $G_{\ell}\subseteq G$ also contains a rainbow copy of
$K_{\ell}$.

As in the unbounded case in the deterministic setting, the proof of Lemma 2.2
yields either a monochromatic, or a min-coloured, or a max-coloured copy of
$K_{\ell}$. The proof of Lemma 2.2 is more involved and we give a detailed
outline in Section 4.1. We conclude this section with the short proof of
Theorem 1.3 and Corollary 1.4 based on Lemmata 2.1 and 2.2.

###### Proof of Theorem 1.3 and Corollary 1.4.

Given $\ell\geq 4$ we set $\delta=\ell^{-5}/64$ and $\nu=\delta^{5\ell^{2}}/2$
and let $C$ be sufficiently large so that we can appeal to Lemma 2.1 with
$\ell$ and $\nu$ and to Lemma 2.2 with $\ell$ and $\delta$. Owing to the
monotonicity of the canonical Ramsey property, for the proof of Theorem 1.3 we
may assume $p=p(n)=Cn^{-\frac{2}{\ell+1}}$. Since $\ell\geq 4$ this implies
$p(n)\leq n^{-\frac{2\ell-2}{\ell^{2}+\ell-4}}/\omega(n)$ for some function
$\omega$ tending to infinity with $n$.

Let $G\in G(n,p)$ satisfy the conclusion of both lemmata and consider an
arbitrary edge colouring $\varphi\colon E(G)\longrightarrow\mathds{N}$ of $G$.

For every $U\subseteq V(G)$ we consider its subset of unbounded vertices in
$U$

$B(U)=\\{w\in U\colon d_{c}(w,U)\geq 8\delta p|U|\text{ for some colour
}c\\}\,.$

Owing to Lemma 2.2 we may assume that there is a set $U\subseteq V(G)$
satisfying $|U|\geq\delta^{5\ell^{2}}n$ and $|B(U)|<|U|/2$. Removing the
unbounded vertices from $U$ we arrive at a set

$U^{\prime}=U\smallsetminus
B(U)\quad\text{with}\quad|U^{\prime}|>\frac{|U|}{2}\geq\nu n\,.$

For every vertex $u\in U^{\prime}$ and every colour $c$ we have

$d_{c}(u,U^{\prime})\leq d_{c}(u,U)<8\delta p|U|<16\delta p|U^{\prime}|\,.$

In other words, $\varphi$ is $(16\delta,p)$-bounded on $U^{\prime}$ and Lemma
2.1 yields asymptotically almost surely a rainbow copy of $K_{\ell}$ in the
$\ell$-clean subgraph $G_{\ell}\subseteq G$. ∎

##  3\. Rainbow cliques in bounded colourings of random graphs

We shall use the following notation. For a graph $G=(V,E)$, a vertex $v$, and
a set $U\subseteq V$ we write $d_{G}(v,U)$ for the size of the neighbourhood
of $v$ in $U$. For subsets $X$, $Y\subseteq V$ we denote by $e_{G}(X,Y)$ the
number of edges with one vertex in $X$ and one vertex in $Y$, where edges in
$X\cap Y$ are counted twice, i.e.,

$e_{G}(X,Y)=\big{|}\\{(x,y)\in X\times Y\colon xy\in E\\}\big{|}=\sum_{x\in
X}d_{G}(x,Y)\,.$

Moreover, for some integer $\ell\geq 2$ we denote by $\kappa_{\ell}(G)$ the
number of (labeled) copies of $K_{\ell}$ in $G$. For a family
${\mathcal{U}}=(U_{1},\dots,U_{\ell})$ of mutually disjoint vertex subsets of
$V$ we write $G[{\mathcal{U}}]$ for the $\ell$-partite subgraph induced by the
sets $U_{1},\dots,U_{\ell}$.

The proof of Lemma 2.1 is based on the transference principle of Conlon and
Gowers [cg16], which we use in the following form [cgss14]*Theorem 3.2.

######  Theorem 3.1 (Conlon & Gowers).

For all integers $\ell\geq 3$ and every $\varepsilon>0$ there is some constant
$C>0$ such that for $p=p(n)$ with $Cn^{-\frac{2}{\ell+1}}\leq p\leq 1/C$ and
every $\zeta>0$ asymptotically almost surely the following holds for $G\in
G(n,p)$.

For every family ${\mathcal{U}}=(U_{1},\dots,U_{\ell})$ of mutually disjoint
vertex subsets of $V(G)$ and every $\ell$-partite subgraph $S$ of
$G[{\mathcal{U}}]$, there exists an $\ell$-partite subgraph $D$ of
$K_{n}[{\mathcal{U}}]$ such that

  1. ( )

for all subsets $X$, $Y\subseteq V(G)$ we have $|e_{S}(X,Y)-p\cdot
e_{D}(X,Y)|\leq\varepsilon pn^{2}$

  2. ( )

and
$\big{|}\kappa_{\ell}(S)-p^{\binom{\ell}{2}}\cdot\kappa_{\ell}(D)\big{|}\leq\varepsilon
p^{\binom{\ell}{2}}n^{\ell}$.

Moreover, we have

  1. ( )

for every $X\subseteq V(G)$ all but at most $\varepsilon n$ vertices $v\in
V(G)$ satisfy

$|d_{S}(v,X)-p\cdot d_{D}(v,X)|\leq\varepsilon pn$

  2. ( )

and if $G^{\prime}$ is obtained from $G$ by removing at most $\zeta pn^{2}$
edges, then

$\big{|}\kappa_{\ell}(G^{\prime}[{\mathcal{U}}])-p^{\binom{\ell}{2}}|U_{1}|\cdots|U_{\ell}|\big{|}\leq(\varepsilon+\zeta)p^{\binom{\ell}{2}}n^{\ell}\,.\qed$

We say the graph $D$ provided by Theorem 3.1 is a _dense model_ for the
subgraph $S$ of the sparse random graph. Furthermore, we remark that the
moreover-part is not stated in [cgss14]*Theorem 3.2. However, it easily
follows from ( ) ‣ 3.1 and ( ) ‣ 3.1 applied with an appropriately chosen
$\varepsilon^{\prime}\ll\varepsilon$. In fact, part ( ) ‣ 3.1 follows from ( )
‣ 3.1 applied to $X$ and $Y^{+}$ being the set of vertices having too high
degree in $D$, and a second application to $X$ and a similarly defined set
$Y^{-}$ (see, e.g., proof of Lemma 4.4 in Section 4.2). Part ( ) ‣ 3.1 can be
deduced by applying ( ) ‣ 3.1 and ( ) ‣ 3.1 for
$S^{\prime}=G^{\prime}[{\mathcal{U}}]$. In fact, for this choice, part ( ) ‣
3.1 combined with Chernoff’s inequality implies that all $\binom{\ell}{2}$
bipartite subgraphs $D^{\prime}[U_{i},U_{j}]$ have density close to $1$. More
precisely, in this case $D^{\prime}[{\mathcal{U}}]$ and $K_{n}[{\mathcal{U}}]$
differ by at most $(2\varepsilon^{\prime}+\zeta)n^{2}$ edges. Consequently,
$\big{|}\kappa_{\ell}(D^{\prime})-|U_{1}|\cdots|U_{\ell}|\big{|}\leq(2\varepsilon^{\prime}+\zeta)n^{\ell}$,
which can be transferred to $S^{\prime}=G^{\prime}[{\mathcal{U}}]$ by ( ) ‣
3.1. The two conclusions of the following lemma further strengthen the upper
bound of part ( ) ‣ 3.1 and can be viewed as a customised version of part ( )
‣ 3.1 for our proof of Lemma 2.1.

######  Lemma 3.2.

For all integers $\ell\geq 4$ and every $\varepsilon>0$ there is some constant
$C>0$ such that for $p=p(n)$ with $Cn^{-1/m_{2}(H)}\leq p\leq 1/C$
asymptotically almost surely the following holds for $G\in G(n,p)$.

For every family ${\mathcal{U}}=(U_{1},\dots,U_{\ell})$ of mutually disjoint
vertex subsets of $V(G)$ and every $\ell$-partite subgraph $S$ of
$G[{\mathcal{U}}]$ the following holds:

  1. ( )

For $d_{12}=\frac{e_{S}(U_{1},U_{2})}{p|U_{1}||U_{2}|}$ and
$d_{34}=\frac{e_{S}(U_{3},U_{4})}{p|U_{3}||U_{4}|}$ we have

$\kappa_{\ell}(S)\leq d_{12}d_{34}\cdot
p^{\binom{\ell}{2}}|U_{1}|\cdots|U_{\ell}|+\varepsilon
p^{\binom{\ell}{2}}n^{\ell}\,.$

  2. ( )

For $c_{123}=\frac{\sum_{u\in
U_{1}}d_{S}(u,U_{2})d_{S}(u,U_{3})}{p^{2}|U_{1}||U_{2}||U_{3}|}$ we have

$\kappa_{\ell}(S)\leq c_{123}\cdot
p^{\binom{\ell}{2}}|U_{1}|\cdots|U_{\ell}|+\varepsilon
p^{\binom{\ell}{2}}n^{\ell}\,.$

###### Proof.

We only prove part ( ) ‣ 3.2, since the proof of ( ) ‣ 3.2 is very similar.
Given $\ell$ and $\varepsilon$, let $C$ be sufficiently large, so that Theorem
3.1 applies for $\ell$ and $\varepsilon/16$.

For the given $\ell$-partite subgraph $S$ on partition classes
$U_{1},\dots,U_{\ell}$ we may assume, without loss of generality, that
$|U_{i}|\geq\varepsilon n/2$, since otherwise the bound easily follows from
$\kappa_{\ell}(S)\leq\kappa_{\ell}(G)$ and part ( ) ‣ 3.1 of Theorem 3.1.
Moreover, due to the properties of the random graph $G\in G(n,p)$, we can
bound the degrees by

$d_{S}(v)\leq d_{G}(v)\leq 2pn$ (3.1)

for every vertex $v\in V(G)$.

Let $D$ be the dense model of $S$ provided by Theorem 3.1. In view of part ( )
‣ 3.1 of Theorem 3.1, it suffices to show that

$\kappa_{\ell}(D)\leq
c_{123}\cdot|U_{1}|\cdots|U_{\ell}|+\frac{\varepsilon}{2}n^{\ell}\,.$ (3.2)

Let $Y^{+}$ be the set of vertices $u\in U_{1}$ for which $p\cdot
d_{D}(u,U_{2})>d_{S}(u,U_{2})+\varepsilon pn/16$ or $p\cdot
d_{D}(u,U_{3})>d_{S}(u,U_{3})+\varepsilon pn/16$. Part ( ) ‣ 3.1 tells us
$|Y^{+}|\leq\varepsilon n/8$ and combined with (3.1) it follows

$\displaystyle p^{2}\cdot\sum_{u\in U_{1}}d_{D}(u,U_{2})d_{D}(u,U_{3})$
$\displaystyle\leq\sum_{u\in
U_{1}}d_{S}(u,U_{2})d_{S}(u,U_{3})+\Big{(}\frac{\varepsilon}{4}+\frac{\varepsilon^{2}}{16}\Big{)}p^{2}n^{3}+|Y^{+}|p^{2}n^{2}$
$\displaystyle\leq c_{123}\cdot
p^{2}|U_{1}||U_{2}||U_{3}|+\frac{\varepsilon}{2}p^{2}n^{3}\,.$

Consequently, the number of $K_{1,2}$ in $D$ with center vertex in $U_{1}$ and
leaves in $U_{2}$ and $U_{3}$ is bounded from above by

$c_{123}\cdot|U_{1}||U_{2}||U_{3}|+\frac{\varepsilon}{2}n^{3}$

and (3.2) by bounding the extension of each of these $K_{1,2}$ trivially by
$|U_{4}|\cdots|U_{\ell}|$. ∎

We conclude this section with the proof of Lemma 2.1, which yields rainbow
cliques in bounded colourings of the random graph.

###### Proof of Lemma 2.1.

Given $\ell\geq 4$ and $\nu>0$ we define the auxiliary constant
$\delta=\ell^{-4}/2$ and let $C$ be sufficiently large so that the Theorem 3.1
and Lemma 3.2 apply for

$\varepsilon=\Big{(}\frac{\nu}{2\ell}\Big{)}^{\ell}\,.$ (3.3)

Suppose $G\in G(n,p)$ satisfies the conclusions of Theorem 3.1 and Lemma 3.2.
We may also assume that for every subset $X\subseteq V(G)$ of size at least
$|X|\geq\frac{\nu n}{2\ell}$ we have $d_{G}(v,X)\leq 1.1p|X|$ for all but at
most $n/\log(n)$ vertices $v$.

Below we only prove the moreover-part of the lemma for the $\ell$-clean
subgraph $G_{\ell}\subseteq G$, since the proof for $G$ without the upper
bound on $p$ is identical. Hence, we assume $p=p(n)\leq
n^{-\frac{2\ell-2}{\ell^{2}+\ell-4}}/\omega(n)$ for some function $\omega$
tending to infinity. From this upper bound on $p$ it follows by Markov’s
inequality that asymptotically almost surely the number of distinct pairs of
$K_{\ell}$ sharing more than two vertices is at most $o(pn^{2})$ and,
therefore, we may assume

$\big{|}E(G)\smallsetminus E(G_{\ell})\big{|}\leq\varepsilon pn^{2}\,.$ (3.4)

Let $\varphi\colon E(G)\longrightarrow\mathds{N}$ be an edge colouring, which
is $(\ell^{-5}/4,p)$-bounded on $U\subseteq V(G)$ of size at least $\nu n$.

Let $U^{\prime}_{1}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\dots\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}U^{\prime}_{\ell}=U$
be a balanced partition of $U$. After removing a few vertices of too high
degree, i.e., vertices $u\in U^{\prime}_{i}$ for which
$d_{G}(u,U^{\prime}_{j})>1.1\,p|U^{\prime}_{j}|$ for some $j\neq i$, we arrive
at a collection ${\mathcal{U}}=(U_{1},\dots,U_{\ell})$ of mutually disjoint
sets of size $m$ such that

$|U_{1}|=\dots=|U_{\ell}|=m\geq\frac{|U|}{2\ell}\geq\frac{\nu}{2\ell}n$

and for every every vertex $u_{i}\in U_{i}$ and $j\in[\ell]$ we have

$d_{G}(u_{i},U_{j})\leq 2p|U_{j}|=2pm\,.$ (3.5)

In addition, the boundedness of $\varphi$ and the choice of $\delta$ ensures
for every colour $c\in\mathds{N}$

$d_{c}(u_{i},U_{j})\leq
d_{c}(u_{i},U)\leq\frac{1}{4\ell^{5}}p|U|\leq\frac{1}{2\ell^{4}}p|U_{j}|=\delta
pm\,.$ (3.6)

In view of (3.4), part ( ) ‣ 3.1 of Theorem 3.1 yields

$\kappa_{\ell}(G_{\ell}[{\mathcal{U}}])\geq(1-2\varepsilon)p^{\binom{\ell}{2}}m^{\ell}$

and below we shall bound the number of non-rainbow copies of $K_{\ell}$ in
$G[{\mathcal{U}}]\supseteq G_{\ell}[{\mathcal{U}}]$.

For that it will be useful to classify the non-rainbow copies according to
where the repeated colour occurs. We consider two cases depending on whether
the two edges of the same colour share a vertex or form a matching. Hence, we
consider the number
$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@moveto{9.95863pt}{28.45276pt}\pgfsys@curveto{9.95863pt}{33.95282pt}{5.50006pt}{38.41139pt}{0.0pt}{38.41139pt}\pgfsys@curveto{-5.50006pt}{38.41139pt}{-9.95863pt}{33.95282pt}{-9.95863pt}{28.45276pt}\pgfsys@curveto{-9.95863pt}{22.9527pt}{-5.50006pt}{18.49413pt}{0.0pt}{18.49413pt}\pgfsys@curveto{5.50006pt}{18.49413pt}{9.95863pt}{22.9527pt}{9.95863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)$
of copies of $K_{\ell}$ in $G[{\mathcal{U}}]$ containing edges $e\in
E_{G}(U_{1},U_{2})$ and $e^{\prime}\in E_{G}(U_{1},U_{3})$ such that
$\varphi(e)=\varphi(e^{\prime})$. Similarly, we define
$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@moveto{34.59863pt}{28.45276pt}\pgfsys@curveto{34.59863pt}{33.95282pt}{30.14006pt}{38.41139pt}{24.64pt}{38.41139pt}\pgfsys@curveto{19.13994pt}{38.41139pt}{14.68137pt}{33.95282pt}{14.68137pt}{28.45276pt}\pgfsys@curveto{14.68137pt}{22.9527pt}{19.13994pt}{18.49413pt}{24.64pt}{18.49413pt}\pgfsys@curveto{30.14006pt}{18.49413pt}{34.59863pt}{22.9527pt}{34.59863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@moveto{-14.68137pt}{28.45276pt}\pgfsys@curveto{-14.68137pt}{33.95282pt}{-19.13994pt}{38.41139pt}{-24.64pt}{38.41139pt}\pgfsys@curveto{-30.14006pt}{38.41139pt}{-34.59863pt}{33.95282pt}{-34.59863pt}{28.45276pt}\pgfsys@curveto{-34.59863pt}{22.9527pt}{-30.14006pt}{18.49413pt}{-24.64pt}{18.49413pt}\pgfsys@curveto{-19.13994pt}{18.49413pt}{-14.68137pt}{22.9527pt}{-14.68137pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)$
to be those copies with the two edges of the same colour being from
$E_{G}(U_{1},U_{2})$ and $E_{G}(U_{3},U_{4})$. We will exploit the boundedness
of $\varphi$ to deduce the following claim from Lemma 3.2.

######  Claim 3.3.

We have
$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@moveto{34.59863pt}{28.45276pt}\pgfsys@curveto{34.59863pt}{33.95282pt}{30.14006pt}{38.41139pt}{24.64pt}{38.41139pt}\pgfsys@curveto{19.13994pt}{38.41139pt}{14.68137pt}{33.95282pt}{14.68137pt}{28.45276pt}\pgfsys@curveto{14.68137pt}{22.9527pt}{19.13994pt}{18.49413pt}{24.64pt}{18.49413pt}\pgfsys@curveto{30.14006pt}{18.49413pt}{34.59863pt}{22.9527pt}{34.59863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@moveto{-14.68137pt}{28.45276pt}\pgfsys@curveto{-14.68137pt}{33.95282pt}{-19.13994pt}{38.41139pt}{-24.64pt}{38.41139pt}\pgfsys@curveto{-30.14006pt}{38.41139pt}{-34.59863pt}{33.95282pt}{-34.59863pt}{28.45276pt}\pgfsys@curveto{-34.59863pt}{22.9527pt}{-30.14006pt}{18.49413pt}{-24.64pt}{18.49413pt}\pgfsys@curveto{-19.13994pt}{18.49413pt}{-14.68137pt}{22.9527pt}{-14.68137pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)\leq
5\delta p^{\binom{\ell}{2}}m^{\ell}$ and
$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@moveto{9.95863pt}{28.45276pt}\pgfsys@curveto{9.95863pt}{33.95282pt}{5.50006pt}{38.41139pt}{0.0pt}{38.41139pt}\pgfsys@curveto{-5.50006pt}{38.41139pt}{-9.95863pt}{33.95282pt}{-9.95863pt}{28.45276pt}\pgfsys@curveto{-9.95863pt}{22.9527pt}{-5.50006pt}{18.49413pt}{0.0pt}{18.49413pt}\pgfsys@curveto{5.50006pt}{18.49413pt}{9.95863pt}{22.9527pt}{9.95863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)\leq
5\delta p^{\binom{\ell}{2}}m^{\ell}$.

Applying the claim to cover all $\binom{\binom{\ell}{2}}{2}$ possibilities
where the two identically coloured edges may appear within the pairs of
classes of ${\mathcal{U}}$ yields at least

$(1-2\varepsilon)p^{\binom{\ell}{2}}m^{\ell}-\frac{\ell^{4}}{8}\cdot 5\delta
p^{\binom{\ell}{2}}m^{\ell}>\frac{1}{2}p^{\binom{\ell}{2}}m^{\ell}$

rainbow copies of $K_{\ell}$ in $G_{\ell}[{\mathcal{U}}]$. Hence, for the
proof of Lemma 2.1 it only remains to verify Claim 3.3. ∎

###### Proof of Claim 3.3.

We first bound
$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@moveto{34.59863pt}{28.45276pt}\pgfsys@curveto{34.59863pt}{33.95282pt}{30.14006pt}{38.41139pt}{24.64pt}{38.41139pt}\pgfsys@curveto{19.13994pt}{38.41139pt}{14.68137pt}{33.95282pt}{14.68137pt}{28.45276pt}\pgfsys@curveto{14.68137pt}{22.9527pt}{19.13994pt}{18.49413pt}{24.64pt}{18.49413pt}\pgfsys@curveto{30.14006pt}{18.49413pt}{34.59863pt}{22.9527pt}{34.59863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@moveto{-14.68137pt}{28.45276pt}\pgfsys@curveto{-14.68137pt}{33.95282pt}{-19.13994pt}{38.41139pt}{-24.64pt}{38.41139pt}\pgfsys@curveto{-30.14006pt}{38.41139pt}{-34.59863pt}{33.95282pt}{-34.59863pt}{28.45276pt}\pgfsys@curveto{-34.59863pt}{22.9527pt}{-30.14006pt}{18.49413pt}{-24.64pt}{18.49413pt}\pgfsys@curveto{-19.13994pt}{18.49413pt}{-14.68137pt}{22.9527pt}{-14.68137pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)$.
Note that if each colour occupies $\delta pm^{2}$ edges of $G[U_{1},U_{2}]$,
then the claimed upper bound follows easily from Lemma 3.2 ( ) ‣ 3.2. We shall
reduce the problem to this case.

Fix a partition $C_{1}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\dots\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}C_{r}=\mathds{N}$
of the set of colours such that

$r\leq\frac{2}{\delta}\qquad\text{and}\qquad\big{|}\varphi^{-1}(C_{\varrho})\cap
E_{G}(U_{1},U_{2})\big{|}\leq 2\delta pm^{2}\ \text{for every
$\varrho\in[r]$.}$

Note that due to (3.5) and (3.6) such a partition of the colours can be found
greedily, by adding colours to a class $C_{\varrho}$ as long as the bound on
the number of edges in the preimage holds.

For $\varrho\in[r]$ let $S_{\varrho}$ be the subgraph obtained from
$G[{\mathcal{U}}]$ by restricting the edges from $G[U_{1},U_{2}]$ and
$G[U_{3},U_{4}]$ to $\varphi^{-1}(C_{\varrho})\cap E_{G}(U_{1},U_{2})$ and
$\varphi^{-1}(C_{\varrho})\cap E_{G}(U_{3},U_{4})$, i.e., to those edges
having a colour from $C_{\varrho}$. Note that every copy counted by
$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@moveto{34.59863pt}{28.45276pt}\pgfsys@curveto{34.59863pt}{33.95282pt}{30.14006pt}{38.41139pt}{24.64pt}{38.41139pt}\pgfsys@curveto{19.13994pt}{38.41139pt}{14.68137pt}{33.95282pt}{14.68137pt}{28.45276pt}\pgfsys@curveto{14.68137pt}{22.9527pt}{19.13994pt}{18.49413pt}{24.64pt}{18.49413pt}\pgfsys@curveto{30.14006pt}{18.49413pt}{34.59863pt}{22.9527pt}{34.59863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@moveto{-14.68137pt}{28.45276pt}\pgfsys@curveto{-14.68137pt}{33.95282pt}{-19.13994pt}{38.41139pt}{-24.64pt}{38.41139pt}\pgfsys@curveto{-30.14006pt}{38.41139pt}{-34.59863pt}{33.95282pt}{-34.59863pt}{28.45276pt}\pgfsys@curveto{-34.59863pt}{22.9527pt}{-30.14006pt}{18.49413pt}{-24.64pt}{18.49413pt}\pgfsys@curveto{-19.13994pt}{18.49413pt}{-14.68137pt}{22.9527pt}{-14.68137pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)$
is contained in some $S_{\varrho}$.

Applying Lemma 3.2 ( ) ‣ 3.2, we obtain

$\kappa_{\ell}(S_{\varrho})\leq 2\delta
pm^{2}\cdot\big{|}E_{S_{\varrho}}(U_{3},U_{4})\big{|}\cdot
p^{\binom{\ell}{2}-2}m^{\ell-4}+\varepsilon p^{\binom{\ell}{2}}n^{\ell},$

and summing over all $\varrho\in[r]$ and recalling (3.5) yields the desired
bound

$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@moveto{34.59863pt}{28.45276pt}\pgfsys@curveto{34.59863pt}{33.95282pt}{30.14006pt}{38.41139pt}{24.64pt}{38.41139pt}\pgfsys@curveto{19.13994pt}{38.41139pt}{14.68137pt}{33.95282pt}{14.68137pt}{28.45276pt}\pgfsys@curveto{14.68137pt}{22.9527pt}{19.13994pt}{18.49413pt}{24.64pt}{18.49413pt}\pgfsys@curveto{30.14006pt}{18.49413pt}{34.59863pt}{22.9527pt}{34.59863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@moveto{-14.68137pt}{28.45276pt}\pgfsys@curveto{-14.68137pt}{33.95282pt}{-19.13994pt}{38.41139pt}{-24.64pt}{38.41139pt}\pgfsys@curveto{-30.14006pt}{38.41139pt}{-34.59863pt}{33.95282pt}{-34.59863pt}{28.45276pt}\pgfsys@curveto{-34.59863pt}{22.9527pt}{-30.14006pt}{18.49413pt}{-24.64pt}{18.49413pt}\pgfsys@curveto{-19.13994pt}{18.49413pt}{-14.68137pt}{22.9527pt}{-14.68137pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{24.64pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{-24.64pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)\leq
4\delta p^{\binom{\ell}{2}}m^{\ell}+\varepsilon
p^{\binom{\ell}{2}}n^{\ell}\overset{\eqref{eq:eps-bdd}}{\leq}5\delta
p^{\binom{\ell}{2}}m^{\ell}\,.$

For the bound on
$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@moveto{9.95863pt}{28.45276pt}\pgfsys@curveto{9.95863pt}{33.95282pt}{5.50006pt}{38.41139pt}{0.0pt}{38.41139pt}\pgfsys@curveto{-5.50006pt}{38.41139pt}{-9.95863pt}{33.95282pt}{-9.95863pt}{28.45276pt}\pgfsys@curveto{-9.95863pt}{22.9527pt}{-5.50006pt}{18.49413pt}{0.0pt}{18.49413pt}\pgfsys@curveto{5.50006pt}{18.49413pt}{9.95863pt}{22.9527pt}{9.95863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)$,
we will again partition the colours, to reduce it to $2/\delta$ applications
of Lemma 3.2 ( ) ‣ 3.2. However, every vertex in $U_{1}$ will define its own
partition. For every vertex $u\in U_{1}$ we fix a partition
$C^{u}_{1}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\dots\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}C^{u}_{r_{u}}=\mathds{N}$
such that for every $\varrho\in[r_{u}]$ we have

$\sum_{c\in C^{u}_{\varrho}}d_{c}(u,U_{2})\leq 2\delta pm^{2}\,.$

Again it follows from (3.5) and (3.6) that such a partition exists for some
$r_{u}\leq 2/\delta$. For simplicity we allow empty partition classes and,
hence, we may assume that $r_{u}=r=\lfloor 2/\delta\rfloor$ for every vertex
$u\in U_{1}$.

For $\varrho\in[r]$ this time we let $S_{\varrho}$ be the subgraph obtained
from $G[{\mathcal{U}}]$ by restricting the edges in $G[U_{1},U_{2}]$ and
$G[U_{1},U_{3}]$ incident to a vertex $u\in U_{1}$ to those, which received a
colour from $C^{u}_{\varrho}$, i.e.,

$E_{S_{\varrho}}(U_{1},U_{2})=\bigcup_{u\in U_{1}}\big{\\{}uv\in E(G)\colon
v\in U_{2}\ \text{and}\ \varphi(uv)\in C^{u}_{\varrho}\big{\\}}$

and $E_{S_{\varrho}}(U_{1},U_{3})$ is defined in an analogous way. This
definition guarantees that every $K_{\ell}$ in $G[{\mathcal{U}}]$ containing a
monochromatic $K_{1,2}$ with center in $U_{1}$ and leaves in $U_{2}$ and
$U_{3}$ is contained in $S_{\varrho}$ for some $\varrho\in[r]$.

In view of Lemma 3.2 ( ) ‣ 3.2, we have

$\displaystyle\kappa_{\ell}(S_{\varrho})$ $\displaystyle\leq\sum_{u\in
U_{1}}2\delta pm\cdot\sum_{c\in C^{u}_{\varrho}}d_{c}(u,U_{3})\cdot
p^{\binom{\ell}{2}-2}m^{\ell-3}+\varepsilon p^{\binom{\ell}{2}}n^{\ell}$
$\displaystyle=\big{|}E_{S_{\varrho}}(U_{1},U_{3})\big{|}\cdot 2\delta
p^{\binom{\ell}{2}-1}m^{\ell-2}+\varepsilon p^{\binom{\ell}{2}}n^{\ell}\,.$

In view of (3.5), summing over all $\varrho\in[r]$ yields the desired bound

$\kappa_{\ell}^{\mathord{\scaleobj{1.2}{\scalerel*{\leavevmode\hbox{\set@color
\leavevmode\hbox to71.99pt{\vbox to63pt{\pgfpicture\makeatletter\hbox{\hskip
34.7995pt\lower-24.38501pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\ignorespaces\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@moveto{9.95863pt}{28.45276pt}\pgfsys@curveto{9.95863pt}{33.95282pt}{5.50006pt}{38.41139pt}{0.0pt}{38.41139pt}\pgfsys@curveto{-5.50006pt}{38.41139pt}{-9.95863pt}{33.95282pt}{-9.95863pt}{28.45276pt}\pgfsys@curveto{-9.95863pt}{22.9527pt}{-5.50006pt}{18.49413pt}{0.0pt}{18.49413pt}\pgfsys@curveto{5.50006pt}{18.49413pt}{9.95863pt}{22.9527pt}{9.95863pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@moveto{-14.68224pt}{-14.22638pt}\pgfsys@curveto{-14.68224pt}{-8.72632pt}{-19.14081pt}{-4.26775pt}{-24.64087pt}{-4.26775pt}\pgfsys@curveto{-30.14093pt}{-4.26775pt}{-34.5995pt}{-8.72632pt}{-34.5995pt}{-14.22638pt}\pgfsys@curveto{-34.5995pt}{-19.72644pt}{-30.14093pt}{-24.18501pt}{-24.64087pt}{-24.18501pt}\pgfsys@curveto{-19.14081pt}{-24.18501pt}{-14.68224pt}{-19.72644pt}{-14.68224pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{-24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@moveto{34.5995pt}{-14.22638pt}\pgfsys@curveto{34.5995pt}{-8.72632pt}{30.14093pt}{-4.26775pt}{24.64087pt}{-4.26775pt}\pgfsys@curveto{19.14081pt}{-4.26775pt}{14.68224pt}{-8.72632pt}{14.68224pt}{-14.22638pt}\pgfsys@curveto{14.68224pt}{-19.72644pt}{19.14081pt}{-24.18501pt}{24.64087pt}{-24.18501pt}\pgfsys@curveto{30.14093pt}{-24.18501pt}{34.5995pt}{-19.72644pt}{34.5995pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{24.64087pt}{-14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@setlinewidth{7.96677pt}\pgfsys@invoke{
}\ignorespaces{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{-24.64087pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{\ignorespaces}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@stroke@opacity{0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0}\pgfsys@invoke{
}{}\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@moveto{36.98866pt}{0.0pt}\pgfsys@curveto{36.98866pt}{1.5715pt}{35.71472pt}{2.84544pt}{34.14322pt}{2.84544pt}\pgfsys@curveto{32.57172pt}{2.84544pt}{31.29778pt}{1.5715pt}{31.29778pt}{0.0pt}\pgfsys@curveto{31.29778pt}{-1.5715pt}{32.57172pt}{-2.84544pt}{34.14322pt}{-2.84544pt}\pgfsys@curveto{35.71472pt}{-2.84544pt}{36.98866pt}{-1.5715pt}{36.98866pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{34.14322pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\ignorespaces \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{\ignorespaces}{\ignorespaces}{\ignorespaces}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{x}}}}(G[{\mathcal{U}}],\varphi)\leq
4\delta p^{\binom{\ell}{2}}m^{\ell}+\varepsilon
p^{\binom{\ell}{2}}n^{\ell}\overset{\eqref{eq:eps-bdd}}{\leq}5\delta
p^{\binom{\ell}{2}}m^{\ell}\,,$

which concludes the proof of Claim 3.3 and, hence, Lemma 2.1 is established. ∎

######  Remark 3.4.

Theorem 3.1 from [cgss14] is more general and applies not only to cliques
$K_{\ell}$, but to all _strictly balanced_ graphs $H$ for $p\geq
Cn^{-\frac{|V(H)|-2}{|E(H)|-1}}$, i.e., for graphs $H$ satisfying

$\frac{|E(H^{\prime})|-1}{|V(H^{\prime})|-2}<\frac{|E(H)|-1}{|V(H)|-2}$

for all proper subgraphs $H^{\prime}\subsetneq H$ on at least three vertices.
Starting with this general version of Theorem 3.1, the arguments tfrom this
section can be carried out verbatim for such graphs $H$. This yields a version
of Lemma 2.1 guaranteeing rainbow copies of strictly balanced graphs $H$ for
$(\delta,p)$-bounded edge colourings of $G(n,p)$ for $p\geq
Cn^{-\frac{|V(H)|-2}{|E(H)|-1}}$ as long as $\delta$ is sufficiently small and
$C$ is sufficiently large depending on $H$.

##  4\. Canonical cliques in unbounded colourings of random graphs

This section contains the proof of Lemma 2.2 along with the required
prerequisites. We begin with an overview of the proof.

###  4.1. Outline of the proof

Again, the main tool in the proof of Lemma 2.2 is the transference principle
developed by Conlon and Gowers. This result asserts that asymptotically almost
surely every subgraph $F$ of $G(n,p)$ has a dense model (see, e.g., Theorem
3.1 ( ) ‣ 3.1). Moreover, if $p\gg n^{-\frac{2}{\ell+1}}$, then the dense
model $D$ and the subgraph $F$, have closely related distributions of the
copies of $K_{\ell}$, which is made precise in part ( ) ‣ 3.1 of Theorem 3.1.
Roughly speaking, we may think of $F$ being _close to_ a random subgraph of
$D$ whose edges are sampled independently with probability $p$.

For mimicking the argument from Section 2 for colourings of $K_{n}$, the main
obstacle is that the neighbourhoods in $G(n,p)$ are of order $pn$, not
allowing the iteration rendered in (2.2). We circumvent this by considering
suitable subgraphs $F_{1},F_{2},\ldots,F_{L}$ of $G(n,p)$ for
$L=2(\ell-1)(\ell-2)+2$ and obtain their dense models $D_{1},\ldots,D_{L}$,
which yield linear-sized sets as neighbourhoods in the dense models. Another
challenge is that, for transference to be useful, the dense model has to
contain $\Omega(n^{\ell})$ copies of $K_{\ell}$, so we also need a robust,
counting version of the argument for the case of unbounded colourings of
$K_{n}$.

In the proof of Lemma 2.2 the ordering of the underlying vertex set will be
important. For that, we refine the definition of $d_{c}(u,U)$ for a given edge
colouring $\varphi$ and for $\diamond\in\\{<\,,>\\}$ we set

$d^{\diamond}_{c}(u,U)=\big{|}N^{\diamond}_{c}(u,U)\big{|}=\big{|}\\{w\in
U\colon\varphi(uw)=c\ \text{and}\ u\diamond w\\}\big{|}\,.$

In Lemma 2.2 we assume that every sufficiently large set $U$ of vertices of
the random graph has the property that half of its vertices $u$ have a large
monochromatic neighbourhood. For simplicity, in the outline below we shall
always assume that, in fact, these vertices $u$ always lie before their
monochromatic neighbourhood, i.e., $d^{<}_{c}(u,U)\geq 4\delta p|U|$ for at
least $|U|/4$ vertices.

The subgraphs $F_{i}\subseteq G(n,p)$ for $i\in[L]$ will be selected in an
iterative manner. For the definition of $F_{1}$, let $V_{1}$ be those $n/4$
vertices $v$ such that $d^{<}_{c(v)}(v)\geq 4\delta pn$ for some associated
colour $c(v)$. The graph $F_{1}$ is then defined as the union of those edges,
i.e.,

$E(F_{1})=\\{vw\in E(G(n,p))\colon v\in V_{1},v<w,\ \text{and}\
\varphi(vw)=c(v)\\}\,.$

In other words, the colour of each edge $e\in E(F_{1})$ is defined by its
starting point $\min(e)$. The transference principle yields a dense model
$D_{1}$ of $F_{1}$, and by part ( ) ‣ 3.1 of Theorem 3.1 most $v\in V_{1}$
satisfy $p\cdot d^{<}_{D_{1}}(v)$ is well approximated by $d^{<}_{F_{1}}(v)$.
Consequently, typically the neighbourhood of $v$ in $D_{1}$ defines a subset
$S_{1}(v)$ of size at least $3\delta n$.

We continue and define $F_{2}$ based on the sets $S_{1}(v_{1})$ for $v_{1}\in
V_{1}$. Again appealing to the assumption (2.3) of Lemma 2.2 as described
above for $U=S_{1}(v_{1})$, we obtain $|S_{1}(v_{1})|/4$ pairs $(v_{2},c)\in
S_{1}(v_{1})\times\mathds{N}$ with

$d_{c}^{<}(v_{2},S_{1}(v_{1}))\geq 4\delta
p|S_{1}(v_{1})|=\Omega(\delta^{2}pn)\,.$ (4.1)

However, the colour $c$ depends on $v_{1}$ and, similarly, as in the
definition of $F_{1}$ we shall find a “large” monochromatic neighbourhood of
$v_{2}$ for the definition of $F_{2}$. On the other hand, since the degree of
$v_{2}$ is close to $pn$ in $G(n,p)$ at most $1/\delta^{2}$ different colours
might occur for different choices of $v_{1}$. We let $c(v_{2})$ be the
majority colour and restrict to it for the definition of $F_{2}$. Moreover,
for an appropriately chosen subset $V_{2}\subseteq\bigcup\\{S_{1}(v_{1})\colon
v_{1}\in V_{1}\\}$ and we shall define $F_{2}$ in such a way that

$E(F_{2})\subseteq\\{v_{2}w\colon v_{2}\in V_{2},v_{2}<w,\ \text{and}\
\varphi(v_{2}w)=c(v_{2})\\}\,.$

In particular, the colours of the edges in $F_{2}$ are determined again by
their starting point. For some technical reasons the definition of $F_{2}$ is
a bit more involved and, for example, we will impose $F_{2}$ to be bipartite
(see Claim 4.5 below for the formal statement). Similar as before, we obtain a
dense model $D_{2}$ for $F_{2}$. Owing to (4.1), the vertices in $V_{2}$ have
$\Omega(\delta^{2}pn)$ neighbours in $F_{2}$. Consequently, most vertices in
$V_{2}$ have $\Omega(\delta^{2}n)$ neighbours in $D_{2}$. Those neighbourhoods
yield the linear sized sets $S_{2}(v_{2})$, which allows us to iterate the
argument to obtain a subgraph $F_{3}\subseteq G(n,p)$ with all edges colours
determined by its starting vertex and a dense model $D_{3}$ of $F_{3}$ with
linear sized neighbourhoods.

This way we obtain graphs $F=F_{1}\cup\dots\cup F_{L}$, and
$D=D_{1}\cup\dots\cup D_{L}$. We shall show that the dense graph $D=$ contains
$\Omega(n^{\ell})$ copies of $K_{\ell}$ by its construction through “nested
neighbourhoods.” Consequently, the transference principle in form of part ( )
‣ 3.1 of Theorem 3.1 tells us that the sparse subgraph $F\subseteq G(n,p)$
contains $\Omega(p^{\binom{\ell}{2}}n^{\ell})$ copies of $K_{\ell}$ and by the
choice of the $F_{i}$ these copies will be non-strictly min-coloured.

It remains to analyse the induced vertex colourings of these non-strictly min-
coloured copies of $K_{\ell}$ in $G(n,p)$. However, those induced vertex
colours are not synchronised within each of the sets $V_{1},\dots,V_{L}$,
i.e., the edges edges of $F_{i}$ are not monochromatic and may induce
different colours for the vertices in $V_{i}$. We address this issue by a more
careful selection of the graphs $F_{1},\dots,F_{\ell}$ (see ( ) ‣ 4.5 of Claim
4.5 below).

The proof of Lemma 2.2 is based on a more involved application of the
transference principle compared to the proof of Lemma 2.1 in Section 3. In
Section 4.2 we review the required results from [cg16] and some helpful
consequences for the proof of Lemma 2.2 presented in Section 4.3.

###  4.2. The transference principle

In this section, we present the prerequisites for the proof of Lemma 2.2. The
statements are written for arbitrary strictly balanced graphs $H$, although we
shall only employ them for $H=K_{\ell}$. For a strictly balanced graph $H$ on
at least three vertices, we can define its _$2$ -density_ by

$m_{2}(H)=\frac{|E(H)|-1}{|V(H)|-2}\,,$

and we note that $m_{2}(K_{\ell})=(\ell+1)/2$ appears in the exponents of
$p=p(n)$ in the in the assumptions of the earlier statements in Sections 1–3.
Similarly, below we shall impose $p=p(n)\geq Cn^{-1/m_{2}(H)}$ for some
sufficiently large constant $C$ for some strictly balanced graph $H$ on the
vertex set $[\ell]$ for some $\ell\geq 3$.

For some (large) integer $n$, we shall work within the set of functions from
$[n]^{(2)}$ to $\mathds{R}$, which naturally corresponds to the set of
_weighted graphs_ on the vertex set $[n]$. Therefore, we often identify a
graph $F$ on $[n]$ with the indicator function $\mathds{1}_{F}$ of its edge
set and a dense model $\mathfrak{d}$ for $F$ is a function
$\mathfrak{d}\colon[n]^{(2)}\longrightarrow[0,1]$, which is “close” to
$p^{-1}\mathds{1}_{F}$ in terms of its distribution of weighted edges and
copies of $H$. The definitions of edge counts and vertex degrees extend
straightforwardly to functions
$\mathfrak{f}\colon[n]^{(2)}\longrightarrow\mathds{R}$ and for that we set

$e(\mathfrak{f})=\sum_{u<w}\mathfrak{f}(uw)\,,\quad
e_{\mathfrak{f}}(U,W)=\sum_{u\in U,w\in
W}\mathfrak{f}(uw)\,,\quad\text{and}\quad d_{\mathfrak{f}}(v,U)=\sum_{u\in
U\smallsetminus\\{v\\}}\mathfrak{f}(uv).$

With this notation at hand we can define the _cut-norm_ by

$\left\|\mathfrak{f}\right\|_{\square}=\frac{1}{n^{2}}\max_{U,W\subseteq[n]}e_{\mathfrak{f}}(U,W)\,.$

This norm allows us to compare the edge distributions of two weighted graphs
on $[n]$. In fact, we will consider weighted graphs $\mathfrak{f}$ and
$\mathfrak{d}$ to be “close,” if
$\left\|\mathfrak{f}-\mathfrak{d}\right\|_{\square}$ is “small” (see, e.g.,
Theorem 3.1 ( ) ‣ 3.1 and Theorem 4.1 ( ) ‣ 4.1 below). Similarly, for a graph
$H$ with vertex set $[\ell]$ we define its homomorphism density in
$\mathfrak{f}$ by

$\Lambda_{H}(\mathfrak{f})=\frac{1}{n^{\ell}}\sum_{v_{1},\dots,v_{\ell}\in[n]}\prod_{ij\in
e(H)}\mathfrak{f}(v_{i}v_{j})\,,$

where we use the convention $\mathfrak{f}(v_{i}v_{j})=0$ in case
$v_{i}=v_{j}$. Consequently, for cliques the quantity
$\Lambda_{K_{\ell}}(\mathfrak{f})$ corresponds to the weighted
$K_{\ell}$-density in $\mathfrak{f}$ and for $\mathfrak{f}$ being an
unweighted graph we can recover the notation
$\kappa_{\ell}(\mathfrak{f})=n^{\ell}\cdot\Lambda_{K_{\ell}}(\mathfrak{f})$
from Section 3.

As discussed in the outline for the proof of Lemma 2.2, Theorem 3.1 will be
applied in stages to the subgraphs $F_{1},\dots,F_{L}\subseteq G(n,p)$ to
obtain dense models $D_{1},\dots,D_{L}$. In order to ensure that
$D=D_{1}\cup\dots\cup D_{L}$ is still a useful approximation of
$F=F_{1}\cup\dots\cup F_{L}$, we need a bit more insight into how these dense
models are obtained. Informally, Conlon and Gowers [cg16] construct a norm
$\|\cdot\|$ on the set of weighted graphs $\mathds{R}^{[n]^{(2)}}$ so that the
following holds: If $\mathds{1}_{F}$ is the characteristic function of the
edges of some $F\subseteq G(n,p)$ and $\|p^{-1}\mathds{1}_{F}-\mathfrak{d}\|$
is sufficiently small for some dense model $\mathfrak{d}$ with
$\|\mathfrak{d}\|_{\infty}\leq 1$, then $p^{-1}\mathds{1}_{F}$ and
$\mathfrak{d}$ have a “similar” distribution of edges and copies of $H$. A
major contribution of [cg16] is precisely finding a norm which is sufficiently
weak to allow a dense model which is arbitrarily close to
$p^{-1}\mathds{1}_{F}$, and sufficiently strong to preserve the relevant
properties of $F$. However, the norm $\|\cdot\|$ actually depends on the
random graph $G(n,p)$ in the sense that asymptotically almost surely $G\in
G(n,p)$ has the property that there is a norm $\|\cdot\|$ with the
aforementioned properties for every subgraph $F\subseteq G$. Theorem 4.1 below
is version of the transference principle of Conlon and Gowers, which is
tailored for our proof of Lemma 2.2. It is implicit in the work in [cg16] and
in the Appendix we discuss in more detail how it can be extracted.

######  Theorem 4.1.

For every strictly balanced graph $H$ with $V(H)=[\ell]$ and every
$\varepsilon>0$ there is some constant $C>0$ such that for $p=p(n)$ with
$Cn^{-1/m_{2}(H)}\leq p\leq 1/C$ asymptotically almost surely the following
holds for $G\in G(n,p)$.

There exists a norm $\|\cdot\|$ on the set of weighted graphs
$\mathds{R}^{[n]^{(2)}}$ such that for every $F\subseteq G$, there is a dense
model $\mathfrak{d}_{F}\colon[n]^{(2)}\longrightarrow[0,1]$ with
$\|p^{-1}\mathds{1}_{F}-(1+\varepsilon)\mathfrak{d}_{F}\|<\varepsilon$ and

  1. ( )

for all functions $\mathfrak{f}$,
$\mathfrak{d}\colon[n]^{(2)}\longrightarrow\mathds{R}$ with
$\|\mathfrak{f}-(1+\varepsilon)\mathfrak{d}\|<\varepsilon$ we have

$\left\|\mathfrak{f}-\mathfrak{d}\right\|_{\square}\leq 2\varepsilon\,.$

  2. ( )

for every function $\mathfrak{d}\colon[n]^{(2)}\longrightarrow[0,2\ell]$ with
$\|p^{-1}\mathds{1}_{F}-(1+\varepsilon)\mathfrak{d}\|\leq\varepsilon$ we have

$\Lambda_{H}(\mathfrak{d})\leq
p^{-|E(H)|}\Lambda_{H}(F)+(4\ell)^{\ell^{2}}\cdot\varepsilon\,.$

We emphasise that, while ( ) ‣ 4.1 applies to any weighted graph
$\mathfrak{f}$, part ( ) ‣ 4.1 only applies to the subgraphs $F$ of the random
graph. Anyhow, in our intended application we have
$\mathfrak{f}=p^{-1}\mathds{1}_{F}$. Theorem 4.1 is closely related to Theorem
3.1 where $S$ and $D$ in Theorem 3.1 take the rôle of $F$ and
$\mathfrak{d}_{F}$ in Theorem 4.1. In fact, applying ( ) ‣ 4.1 and ( ) ‣ 4.1
with $\mathfrak{d}=\mathfrak{d}_{F}$ and $\mathfrak{f}=p^{-1}\mathds{1}_{F}$
in Theorem 4.1 yields closely related statements ( ) ‣ 3.1 and ( ) ‣ 3.1 of
Theorem 3.1.

It will be convenient to move from the dense weighted graphs $\mathfrak{d}$
back to unweighted graphs $D$ sampled by the edge weights of $\mathfrak{d}$.
The following lemma follows directly from the sharp concentration of the
binomial distribution and Chernoff’s inequality.

######  Lemma 4.2.

For every $\varepsilon>0$ and any sequence of functions
$\mathfrak{d}\colon[n]^{(2)}\longrightarrow[0,1]$ asymptotically almost surely
we have $\left\|\mathds{1}_{D}-\mathfrak{d}\right\|_{\square}\leq\varepsilon$
for the random graph $D$ on $[n]$ with every edge $e$ appearing independently
with probability $\mathfrak{d}(e)$. ∎

We will also use the following _counting lemma_ comparing the number of copies
of subgraph of graphs in terms of the cut-norm. This can be viewed as the
global counting lemma for the weak regularity lemma of Frieze and Kannan
[fk99] and it can be found in [ls06]*Lemma 4.1.

######  Lemma 4.3.

For every graph $H$ and all functions $\mathfrak{f}$,
$\mathfrak{d}\colon[n]^{(2)}\longrightarrow[0,1]$ we have

$\big{|}\Lambda_{H}(\mathfrak{f})-\Lambda_{H}(\mathfrak{d})\big{|}\leq
2e(H)\cdot\left\|\mathfrak{f}-\mathfrak{d}\right\|_{\square}\qed$

We conclude this section with the following fact that the cut-norm controls
most vertex degrees into given subsets (see, e.g., the deduction of ( ) ‣ 3.1
of Theorem 3.1 from ( ) ‣ 3.1).

######  Lemma 4.4.

For every $\varepsilon>0$ and all functions $\mathfrak{f}$,
$\mathfrak{d}\colon[n]^{(2)}\longrightarrow[0,1]$ with
$\left\|\mathfrak{f}-\mathfrak{d}\right\|_{\square}\leq\varepsilon$ the
following holds. For all $U\subseteq[n]$ with $|U|>2\varepsilon^{1/3}n$, all
but at most $\varepsilon^{1/3}n$ vertices $v\in[n]$ satisfy

$|d_{\mathfrak{f}}(v,U)-d_{\mathfrak{d}}(v,U)|\leq\varepsilon^{1/3}|U|\,.$

###### Proof of Lemma 4.4.

Let $S$ be the set of vertices $v$ with
$d_{\mathfrak{f}}(v,U)-d_{\mathfrak{d}}(v,U)\geq\varepsilon^{1/3}|U|$. We have

$\displaystyle
n^{2}\left\|\mathfrak{f}-\mathfrak{d}\right\|_{\square}\geq\sum_{v\in
S}d_{\mathfrak{f}}(v,U)-d_{\mathfrak{d}}(v,U)\geq\varepsilon^{1/3}|U||S|\geq
2\varepsilon^{2/3}n|S|$

and $|S|\leq\varepsilon^{1/3}n/2$ folllows. Similarly, one can show that there
are at most $\varepsilon^{1/3}n/2$ vertices $v$ such that
$d_{\mathfrak{d}}(v,U)-d_{\mathfrak{f}}(v,U)\geq\varepsilon^{1/3}|U|$ and the
claimed bound follows. ∎

###  4.3. Proof of Lemma 2.2

Given $\ell\geq 3$ and $\delta>0$ we fix auxiliary constants

$L=2(\ell-1)(\ell-2)+2\,,\quad\nu=\frac{\delta^{4\ell^{4}+2\ell^{2}}}{10^{4\ell^{2}}}\,,\quad\alpha=\frac{\nu}{4\ell^{2}}\,,\quad\text{and}\quad\zeta=\delta^{10\ell^{2}+1}\,.$

Moreover we fix auxiliary constants $\varepsilon_{1}$ and $\varepsilon_{2}$
and the desired $C$ to satisfy the hierarchy

$\delta\,,\ell^{-1}\gg\varepsilon_{2}\gg\varepsilon_{1}\gg C^{-1}\,.$

Assume that $G\in G(n,p)$ satisfies the conclusion of Theorem 4.1 and Theorem
3.1 ( ) ‣ 3.1 for $\varepsilon=\varepsilon_{1}$. Let
$\left\|\,\cdot\,\right\|$ denote the norm given by Theorem 4.1. Moreover, we
may assume that all vertices in $G$ have degree $(1\pm\varepsilon_{1})pn$,
since all these properties hold asymptotically almost surely.

For the moreover-part of the lemma, we have in addition $p=p(n)\leq
n^{-\frac{2\ell-2}{\ell^{2}+\ell-4}}/\omega(n)$ for some function $\omega$
tending to infinity. Similarly as in the proof of Lemma 2.1 this implies that
we can assume

$\big{|}E(G)\smallsetminus E(G_{\ell})\big{|}\leq\zeta pn^{2}\,.$ (4.2)

By our choice of $\zeta$ this implies that the crucial assumption (2.3) for
$G$ in Lemma 2.2 extends to $G_{\ell}$ on the price of a small change of the
constants and the proof given below can be carried out in $G_{\ell}$ as well.

For a comparability sign $\diamond\in\\{<,\,>\\}$ set

$B^{\diamond}(U)=\\{v\in U\colon d_{c}^{\diamond}(v,U)\geq 4\delta p|U|\text{
for some colour }c\\}\,.$

The assumption (2.3) implies that for every set $U$ with
$|U|\geq\delta^{5\ell^{2}}n$, we have

$|B^{<}(U)|\geq\frac{|U|}{4}\quad\text{ \ or \
}\quad|B^{>}(U)|\geq\frac{|U|}{4}.$ (4.3)

The condition (4.3) will be iterated to inductively build some structures in
$G$, as detailed in the following claim. We will build subgraphs $F_{t}$ of
$G$ which are non-strictly min-coloured or max-coloured and relatively dense
to $G$, and $D_{t}$ will be dense models of $F_{t}$ obtained using Theorem
4.1. The hypergraph ${\mathcal{H}}$ is used to keep track of cliques in
$\bigcup_{t}D_{t}$. In the statement and proof, we usually identify a
hypergraph ${\mathcal{H}}$ with its set of edges. In particular,
$|{\mathcal{H}}|$ is the number of edges in ${\mathcal{H}}$.

######  Claim 4.5.

For every $t\in[L]$ there is a set of vertices $V_{t}$ with
$|V_{t}|\geq\frac{1}{25}\alpha\delta^{2t}$, a comparability sign
$\diamond_{t}\in\\{<,\,>\\}$, and a colour index
$\psi_{t}\in\mathds{N}\mathbin{\mathchoice{\leavevmode\vtop{
\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{
\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\\{\star\\}$
such that the following holds:

  1. ( )

Each $v\in V_{t}$ is assigned a colour $c(v)$ and there is a graph
$F_{t}\subseteq G$ whose edges $vu$ satisfy $v\in V_{t}$ and $u\in
N^{\diamond_{t}}_{c(v)}(v)\smallsetminus(V_{1}\cup\dots\cup V_{t})$.

  2. ( )

If $\psi_{t}=j\in\mathds{N}$, then $c(v)=j$ for all $v\in V_{t}$. Otherwise,
if $\psi_{t}=\star$, then we have $|\\{v\in V_{t}\colon
c(v)=j\\}|\leq\alpha|V_{t}|$ for every colour $j$.

  3. ( )

There is a function $\mathfrak{d}_{t}\colon[n]^{(2)}\longrightarrow[0,1]$ with

$\|p^{-1}\mathds{1}_{F_{t}}-(1+\varepsilon_{1})\mathfrak{d}_{t}\|\leq\varepsilon_{1}\,,$

and a graph $D_{t}$ with

$\left\|D_{t}-\mathfrak{d}_{t}\right\|_{\square}\leq
7\varepsilon_{1}\text{\quad and
\quad}\left\|D_{t}-p^{-1}\mathds{1}_{F_{t}}\right\|_{\square}\leq
9\varepsilon_{1}\,.$

  4. ( )

There is a $t$-partite $t$-uniform hypergraph ${\mathcal{H}}_{t}$ on
$V_{1}\cup\dots\cup V_{t}$ with

$|{\mathcal{H}}_{t}|\geq 10^{-2t}\delta^{t^{2}}|V_{1}|\dots|V_{t}|$

and for any $(v_{1},\ldots,v_{t})\in{\mathcal{H}}_{t}$, there is a set
$S(v_{1},\ldots,v_{t})$ disjoint from $V_{1},\ldots,V_{t}$ of size at least
$\delta^{t}n$ such that for $i\leq t$,

$N_{D_{i}}(v_{i})\supseteq\\{v_{i+1},\ldots,v_{t}\\}\cup
S(v_{1},\ldots,v_{t})\,.$

###### Proof of Claim 4.5.

To show the induction basis, let $t=1$. Let $B=B^{\diamond_{1}}([n])$ be the
set of $\frac{n}{4}$ vertices given by (4.3). For $v\in B$, let $c(v)$ be a
colour in which

$d^{\diamond_{1}}_{c(v)}(v)\geq 4\delta pn,$

Moreover, we wish to transfer a bipartite graph $F_{1}$. To this end, let each
vertex of $B$ be placed into a set $Z_{1}$ independently at random with
probability $1/2$, and let $Y_{1}=[n]\smallsetminus Z_{1}$. We may assume that
$|Z_{1}|\geq|B|/3\geq n/30$, and each $v\in Z_{1}$ satisfies

$d^{\diamond_{1}}_{c(v)}(v,Y_{1})\geq 1.5\delta pn$ (4.4)

as this happens with high probability.

If there is a colour $j$ such that $|c^{-1}(j)\cap Z_{1}|\geq\alpha|Z_{1}|$,
set $V_{1}=c^{-1}(j)$ and $\psi_{1}=j$. Otherwise take $V_{1}=Z_{1}$ and set
$\psi_{1}=\star$. Note that in either case,

$|V_{1}|\geq\frac{\alpha n}{30}\,.$

Let $F_{1}$ be the subgraph of $G$ with

$E(F_{1})=\\{v_{1}v\colon v_{1}\in V_{1},v\in Y_{1},v_{1}\diamond_{1}v,\
\text{and}\ \varphi(v_{1}v)=c(v_{1})\\}\,.$

Let $\mathds{1}_{F_{1}}$ be the characteristic function of $F_{1}$. By Theorem
4.1, there is a weighted graph
$\mathfrak{d}_{1}\colon[n]^{(2)}\longrightarrow[0,1]$ with
$\|p^{-1}\mathds{1}_{F_{1}}-\mathfrak{d}_{1}\|\leq\varepsilon_{1}$. In
particular,
$\left\|p^{-1}\mathds{1}_{F_{1}}-\mathfrak{d}_{1}\right\|_{\square}\leq
2\varepsilon_{1}$ by Theorem 4.1 ( ) ‣ 4.1.

Let
$\mathfrak{d}_{1}^{\prime}=\mathfrak{d}_{1}\\!\restriction_{V_{1}\times([n]\smallsetminus
V_{1})}$. Passing to a restriction of $\mathfrak{d}_{1}$ is just a
technicality to circumvent small overlaps between
$\mathfrak{d}_{1},\ldots,\mathfrak{d}_{t}$, and we will now show that
$\left\|\mathfrak{d}_{1}-\mathfrak{d}_{1}^{\prime}\right\|_{\square}\leq
6\varepsilon_{1}$. Denote $\mathfrak{f}_{1}=p^{-1}\mathds{1}_{F_{1}}$. To
bound $\mathfrak{d}_{1}-\mathfrak{d}_{1}^{\prime}$, notice that, by definition
of $\mathfrak{d}_{1}^{\prime}$ and since all edges of $F_{1}$ lie in
$V_{1}\times([n]\smallsetminus V_{1})$,

$\frac{1}{n^{2}}\left(e_{\mathfrak{d}_{1}^{\prime}}([n])-e_{\mathfrak{f}_{1}}([n])\right)=\frac{2}{n^{2}}\left(e_{\mathfrak{d}_{1}}(V_{1},[n]\smallsetminus
V_{1})-e_{\mathfrak{f}_{1}}(V_{1},[n]\smallsetminus V_{1})\right)\leq
2\left\|\mathfrak{d}_{1}-\mathfrak{f}_{1}\right\|_{\square}\leq
4\varepsilon_{1}\,.$

Hence
$e_{\mathfrak{d}_{1}}([n])-e_{\mathfrak{d}_{1}^{\prime}}([n])=e_{\mathfrak{d}_{1}}([n])-e_{\mathfrak{f}_{1}}([n])+e_{\mathfrak{f}_{1}}([n])-e_{\mathfrak{d}_{1}^{\prime}}([n])\leq
6\varepsilon_{1}n^{2}$. Since $\mathfrak{d}_{1}-\mathfrak{d}_{1}^{\prime}\geq
0$, we have

$\left\|\mathfrak{d}_{1}-\mathfrak{d}_{1}^{\prime}\right\|_{\square}=\frac{1}{n^{2}}(e_{\mathfrak{d}_{1}}([n])-e_{\mathfrak{d}_{1}^{\prime}}([n]))\leq
6\varepsilon_{1}.$

Moreover,

$\left\|\mathfrak{d}_{1}^{\prime}-p^{-1}\mathds{1}_{F_{1}}\right\|_{\square}\leq
8\varepsilon_{1}$

using the triangle inequality.

Let $D_{1}$ be a graph sampled from $\mathfrak{d}^{\prime}_{1}$. With high
probability,
$\left\|\mathds{1}_{D_{1}}-\mathfrak{d}_{1}^{\prime}\right\|_{\square}\leq\varepsilon_{1}$
by Lemma 4.2. Therefore, using the triangle inequality, we may assume that

$\left\|D_{1}-\mathfrak{d}_{1}\right\|_{\square}\leq
7\varepsilon_{1}\text{\quad and
\quad}\left\|D_{1}-p^{-1}\mathds{1}_{F_{1}}\right\|_{\square}\leq
9\varepsilon_{1}\,.$

Let ${\mathcal{H}}_{1}$ be the set of vertices $v\in V_{1}$ with

$d_{D_{1}}(v,Y_{1})\geq\delta n\,.$

By Lemma 4.4, using (4.4),
$\left\|\mathds{1}_{D_{1}}-p^{-1}\mathds{1}_{F_{1}}\right\|_{\square}\leq
9\varepsilon_{1}$, and taking $\varepsilon_{1}<\varepsilon_{2}^{4}$, we have
that $|{\mathcal{H}}_{1}|\geq|V_{1}|-\varepsilon_{2}n\geq\frac{|V_{1}|}{2}$.
This completes the case $t=1$.

Suppose the Claim holds for $1,2,\ldots,t-1$. Let
$X=[n]\smallsetminus(V_{1}\cup\dots\cup V_{t-1})$. For
$(v_{1},\ldots,v_{t-1})\in{\mathcal{H}}_{t-1}$, consider the set
$S(v_{1},\ldots,v_{t-1})\subseteq X$ as stated in ( ) ‣ 4.5. Specifically,
$|S(v_{1},\ldots,v_{t-1})|\geq\delta^{t-1}n$. Denote
$\xi=\xi(t):=\delta^{t-1}$. Applying the assumption (4.3), we obtain a set
$B^{\diamond}(S(v_{1},\ldots,v_{t-1}))$ of order at least $\frac{\xi n}{10}$
for some $\diamond=\diamond(v_{1},\ldots v_{t-1})$ such that for every $v\in
B^{\diamond}(S(v_{1},\ldots,v_{t-1}))$ and some colour
$c=c(v_{1},\ldots,v_{t-1},v)$,

$d^{\diamond}_{c}(v,S(v_{1},\ldots,v_{t-1}))\geq 4\delta\xi pn\,.$ (4.5)

The next step is to remove the dependency of $\diamond$ and $c$ on
$(v_{1},\ldots,v_{t-1})$. Firstly, let ${\mathcal{H}}^{\prime}_{t-1}$ be a
subhypergraph of ${\mathcal{H}}_{t-1}$ of order at least
$\frac{1}{2}|{\mathcal{H}}_{t-1}|$ such that $\diamond(v_{1},\ldots
v_{t-1})=\diamond_{t}$ for all
$(v_{1},\ldots,v_{t-1})\in{\mathcal{H}}^{\prime}_{t-1}$.

Now form an auxiliary bipartite graph $J$ with parts
${\mathcal{H}}^{\prime}_{t-1}$ and $X\times\mathds{N}$ as follows: an edge
$((v_{1},v_{2},\ldots v_{t-1}),(v,c))$ in $J$ means that

$\leavevmode\nobreak\ d_{c}^{\diamond_{t}}(v,S(v_{1},\ldots,v_{t-1}))\geq
4\delta\xi pn\,.$ (4.6)

Since every $(v_{1},\ldots v_{t-1})\in{\mathcal{H}}^{\prime}_{t-1}$ is
contained in at least $\xi n/10$ edges in $J$ (one for each element of
$B^{\diamond_{t}}(v_{1},\ldots,v_{t-1})$), we have

$|J|\geq\frac{1}{2}|{\mathcal{H}}_{t-1}|\cdot\frac{\xi n}{10}\,.$

Let $X^{\prime}\subset X$ be the set of vertices $v$ such that some $(v,c)$ is
incident to an edge of $J$, and note that for each $v$, there are at most
$(3\delta\xi)^{-1}$ such colours $c$ – this follows from $d_{c}(v)\geq
4\delta\xi pn$ and $d_{G}(v)\leq(1+\varepsilon_{1})pn$. For each $v\in
X^{\prime}$, let $c(v)$ be the colour which maximises the degree of $(v,c)$ in
$J$. Form $J^{\prime}$ from $J$ by deleting all the vertices $(v,c^{\dagger})$
with $c^{\dagger}\neq c(v)$; we have

$|J^{\prime}|\geq|J|\cdot
3\delta\xi\geq\frac{3}{20}|{\mathcal{H}}_{t-1}|\delta\xi^{2}n\,.$

Since now each vertex $v\in X^{\prime}$ is associated with a unique colour
$c(v)$, we may assume that one vertex part of $J^{\prime}$ is just
$X^{\prime}$

We wish the graph $F_{t}$ to be bipartite, so let us split the set $X$ as
follows. Let $W_{t}\subseteq X^{\prime}$ consist of vertices sampled from
$X^{\prime}$ independently at random with probability $1/2$. Let
$Y_{t}=X\smallsetminus W_{t}$. With positive probability,

$|J^{\prime}[E({\mathcal{H}}_{t-1}^{\prime}),W_{t}]|\geq\frac{3}{50}|{\mathcal{H}}_{t-1}|\delta\xi^{2}n\,,$

and for each $((v_{1},\ldots,v_{t-1}),v)\in J^{\prime}$ (recalling (4.6)),

$d^{\diamond_{t}}_{c(v)}(v,Y_{t}\cap S(v_{1},\ldots,v_{t-1}))\geq 1.5\delta\xi
pn\,,$ (4.7)

where we used Chernoff bounds and the union bound. Thus we may assume that
these two inequalities are satisfied.

Now, let $Z_{t}\subseteq W_{t}$ be the set of vertices of degree at least
$\frac{1}{50}|{\mathcal{H}}_{t-1}|\delta\xi^{2}$ in $J^{\prime}$, and let
$J^{*}$ be the induced subgraph of $J^{\prime}$ on
$(E({\mathcal{H}}_{t-1}^{\prime}),Z_{t})$. Since the vertices in
$W_{t}\smallsetminus Z_{t}$ were incident to at most
$\frac{1}{50}|{\mathcal{H}}_{t-1}|\delta\xi^{2}n$ edges in total, we have

$|J^{*}|\geq\frac{1}{25}|{\mathcal{H}}_{t-1}|\delta\xi^{2}n\,.$

Recalling that $J^{*}$ is a bipartite graph on the vertex sets
$(E({\mathcal{H}}_{t-1}^{\prime}),Z_{t})$, we have the lower bound

$|Z_{t}|\geq\frac{|J^{*}|}{|{\mathcal{H}}_{t-1}|}\geq\frac{1}{25}\delta\xi^{2}n=\frac{1}{25}\delta^{1+2(t-1)}n\geq\frac{1}{25}\delta^{2t}n\,.$
(4.8)

Now, to ensure ( ) ‣ 4.5, if there is a colour $j$ such that

$Z_{t,j}=\\{v\in Z_{t}\colon c(v)=j\\}$

contains at least $\alpha|Z_{t}|$ vertices, let $V_{t}=Z_{t,j}$ and set
$\psi_{t}=j$ (recalling that $\alpha\ll\delta,\ell^{-1}$ is a constant).
Otherwise, set $V_{t}=Z_{t}$ and $\psi_{t}=\star$. Using the minimum degree of
the vertices from $V_{t}$, we have

$\big{|}J^{*}[E({\mathcal{H}}_{t-1}^{\prime}),V_{t}]\big{|}\geq\frac{1}{50}|{\mathcal{H}}_{t-1}|\delta\xi^{2}|V_{t}|\,.$

Moreover, $|V_{t}|\geq\alpha|Z_{t}|\geq\frac{1}{25}\alpha\delta^{2t}n$, as
required by the claim.

Let $F_{t}$ be the subgraph of $G$ with

$E(F_{t})=\\{vy\colon v\in V_{t},y\in Y_{t},v\diamond_{t}y\\}\,.$

Recall that if $((v_{1},\ldots,v_{t-1}),v_{t})\in J^{*}$, then by (4.7),

$d_{F_{t}}(v_{t},S(v_{1},\ldots,v_{t-1})\cap Y_{t})\geq 1.5\delta\xi
pn=1.5\delta^{t}pn\,.$ (4.9)

Let ${\mathfrak{f}}_{t}=p^{-1}\mathds{1}_{F_{t}}$. By Theorem 4.1, there is a
function $\mathfrak{d}_{t}$ with $0\leq\mathfrak{d}_{t}\leq 1$ and

$\|{\mathfrak{f}}_{t}-(1+\varepsilon_{1})\mathfrak{d}_{t}\|\leq\varepsilon_{1}\,.$

Let
$\mathfrak{d}_{t}^{\prime}=\mathfrak{d}_{t}\\!\restriction_{V_{t}\times([n]\smallsetminus(V_{1}\cup\dots
V_{t}))}$, and let $D_{t}$ be a graph sampled from
$\mathfrak{d}_{t}^{\prime}$. By the same argument as in the induction basis,
we may assume that

$\left\|D_{t}-\mathfrak{d}_{t}\right\|_{\square}\leq
7\varepsilon_{1}\text{\quad and
\quad}\left\|D_{t}-p^{-1}\mathds{1}_{F_{t}}\right\|_{\square}\leq
9\varepsilon_{1}\,,$

where $D_{t}$ stands for the indicator function $\mathds{1}_{D_{t}}$.

Let ${\mathcal{H}}_{t}$ consist of $t$-tuples $(v_{1},\ldots,v_{t})$ such that
$v_{t}\in N_{J^{*}}(v_{1},\ldots,v_{t-1})$ and

$d_{D_{t}}(v_{t},S(v_{1},\ldots,v_{t-1})\cap Y_{t})\geq\delta^{t}n\,.$ (4.10)

Using Lemma 4.4 and (4.9), for each
$(v_{1},\ldots,v_{t-1})\in{\mathcal{H}}_{t-1}^{\prime}$, there are at most
$\varepsilon_{2}n$ vertices $v_{t}\in N_{J^{*}}(v_{1},\ldots,v_{t-1})$
violating (4.10) (recalling that $\varepsilon_{2}>\varepsilon_{1}^{4}$), so
indeed

$\displaystyle|{\mathcal{H}}_{t}|$
$\displaystyle\geq|J^{*}[E({\mathcal{H}}_{t-1}^{\prime}),V_{t}]|-\varepsilon_{2}n^{t}$
$\displaystyle\geq\frac{1}{100}|{\mathcal{H}}_{t-1}|\delta\xi^{2}|V_{t}|$
$\displaystyle\geq 10^{-2t}\delta^{(t-1)^{2}+2t-1}|V_{1}|\ldots|V_{t}|$
$\displaystyle=10^{-2t}\delta^{t^{2}}|V_{1}|\ldots|V_{t}|\,,$

where we used the inductive hypothesis in the second line.

Finally, we set $S(v_{1},\ldots v_{t})=N_{D_{t}}(v_{t})\cap
S(v_{1},\ldots,v_{t-1})\cap Y_{t}$ to obtain a set which satisfies asserting (
) ‣ 4.5 of Claim 4.5. ∎

For the remainder of the proof, we do not need properties ( ) ‣ 4.5 and ( ) ‣
4.5, but only the following consequences. We remark that it is crucial that
the relative density of $K_{\ell}$-copies mentioned in ( ) ‣ 4.5 (denoted
$\nu$) does not depend on $\alpha$, but only on $\delta$ and $\ell$. On the
other hand $|V_{i}|/n$ may depend on $\alpha$.

For every subset $M\subseteq[L]$ below we show

  1. ( )

The graph $\bigcup_{i\in M}D_{i}$ contains at least $\nu n\prod_{i\in
M}|V_{i}|$ copies of $K_{|M|+1}.$

  2. ( )

If $|M|\leq\ell$, then

$p^{-\binom{\ell}{2}}\cdot\Lambda_{K_{\ell}}\bigg{(}\bigcup_{i\in
M}F_{i}\bigg{)}\geq\Lambda_{K_{\ell}}\bigg{(}\bigcup_{i\in
M}D_{i}\bigg{)}-\varepsilon_{2}\,.$

We first show that part ( ) ‣ 4.5 of Claim 4.5 implies ( ) ‣ 4.3. Fix any
$(v_{1},\ldots,v_{L})\in{\mathcal{H}}_{L}$, and let
$|V^{*}_{L+1}|=S(v_{1},\ldots,v_{L})$, so $|V^{*}_{L+1}|\geq\delta^{L}n$. Now,
for each $v_{L+1}\in V^{*}_{L+1}$, the vertices $\\{v_{i}\colon i\in
M\\}\cup\\{v_{L+1}\\}$ form a clique in $\bigcup_{i\in M}D_{i}$, since
$N_{D_{i}}(v_{i})$ contains $v_{j}$ for $j>i$ by ( ) ‣ 4.5. The number of
choices for $(v_{i}\colon i\in M)$ contained in some edge
$(v_{1},\ldots,v_{L})\in{\mathcal{H}}_{L}$ is at least

$|{\mathcal{H}}_{L}|\left(\prod_{i\in[L]\smallsetminus
M}|V_{i}|\right)^{-1}\geq 10^{-2L}\delta^{L^{2}}\prod_{i\in M}|V_{i}|.$

Putting these two bounds together, we obtain at least $n\delta^{L}\cdot
10^{-2L}\delta^{L^{2}}\prod_{i\in M}|V_{i}|$ copies of $K_{|M|+1}$, which
implies ( ) ‣ 4.3 since $L\leq 2\ell^{2}$.

Secondly, we claim that $D_{i}$ satisfy ( ) ‣ 4.3. Let $D=\bigcup_{i\in
M}D_{i}$, $\mathfrak{d}=\sum_{i\in M}\mathfrak{d}_{i}$, and $F=\bigcup_{i\in
M}F_{i}$, so that $\mathds{1}_{F}=\sum_{i\in M}\mathds{1}_{F_{i}}$. By the
triangle inequality and part ( ) ‣ 4.5 of Claim 4.5, we have

$\Big{\|}p^{-1}\mathds{1}_{F}-(1+\varepsilon_{1})\sum_{i\in
M}\mathfrak{d}_{i}\Big{\|}\leq\varepsilon_{1}\ell.$

Hence, by Theorem 4.1, and taking $\varepsilon_{1}$ sufficiently small
depending on $\varepsilon_{2}$, we have

$\Lambda_{K_{\ell}}(p^{-1}\mathds{1}_{F})\geq\Lambda_{K_{\ell}}(\mathfrak{d})-\varepsilon_{1}\ell^{3\ell^{2}}\geq\Lambda_{K_{\ell}}(\mathfrak{d})-\frac{\varepsilon_{2}}{2}.$

Moreover, $\left\|\mathfrak{d}_{t}-D_{t}\right\|_{\square}\leq
7\varepsilon_{1}$ for $t\in[L]$, so using Lemma 4.3, we have
$\Lambda_{K_{\ell}}(\mathfrak{d})\geq\Lambda_{K_{\ell}}(D)-\frac{\varepsilon_{2}}{2}.$
It follows that

$\Lambda_{K_{\ell}}(p^{-1}\mathds{1}_{F})\geq\Lambda_{K_{\ell}}(D)-\varepsilon_{2}\,,$

as required for the proof of ( ) ‣ 4.3.

We now complete the proof of Lemma 2.2. Let $I^{\prime}\subset[L]$ be a set of
order $L/2$ such that $\diamond$ is constant on $I^{\prime}$ and, without loss
of generality, we may assume that $\diamond_{i}=<$ for $i\in I^{\prime}$.
Moreover, let $I\subset I^{\prime}$ be a set of order $\ell-1$ such that

  1. ( )

either $\psi_{i}\neq\star$ for $i\in I$ and $\psi$ is constant or injective on
$I$,

  2. ( )

or $\psi_{i}=\star$ for $i\in I$.

Let

$\vartheta=\prod_{i\in I}\frac{\left|V_{i}\right|}{n},\quad F=\bigcup_{i\in
I}F_{i}\text{ \quad and \quad}D=\bigcup_{i\in I}D_{i}\,,$

and note that $\vartheta$ is bounded from below by a constant depending on
$\alpha,\delta,\ell$, due to the lower bound on $|V_{i}|$ in Claim 4.5. By
assertion ( ) ‣ 4.3, $D$ contains at least $\nu\vartheta n^{\ell}$ copies of
$K_{\ell}$. Hence, owing to ( ) ‣ 4.3 and
$\varepsilon_{2}\leq\frac{1}{10}\nu\vartheta$, the graph $F$ contains at least
$\frac{1}{2}\nu\vartheta n^{\ell}p^{\binom{\ell}{2}}$ copies of $K_{\ell}$.

All these copies are non-strictly min-coloured by construction of $F$ (i.e.,
$\varphi(uv)=c(u)$ for $u<v$, $uv\in F$), and now we will use ( ) ‣ 4.5 and
the choice of $I$ to show that there is actually a strictly min-coloured or a
monochromatic copy. We first show that each copy of $K_{\ell}$ in $F$ has
exactly one vertex in $V_{i}$ for $i\in I$. Let $v_{1}<v_{2}<\dots<v_{\ell}$
be the vertex set of a $K_{\ell}$ in $F$, and recall the property ( ) ‣ 4.5 of
Claim 4.5 for $F$. Since all the edges in $F$ have the starting point in
$\bigcup_{i\in I}V_{i}$, we have that
$\\{v_{1},\ldots,v_{\ell-1}\\}\subseteq\bigcup_{i\in I}V_{i}$. But each
$V_{i}$ is an independent set in $F$, so it contains at most one (and hence
exactly one) vertex from $\\{v_{1},\ldots,v_{\ell-1}\\}$.

If $\psi_{i}\neq\star$ for $i\in I$, any copy of $K_{\ell}$ in $F$ is min-
coloured (in case $\psi$ is injective on $I$) or monochromatic (in case $\psi$
is constant on $I$); to see this, recall that by ( ) ‣ 4.5 of Claim 4.5, if
$uv\in E(F_{i})$, $\varphi(uv)=\psi_{i}$.

Suppose that $\psi_{i}=\star$ for $i\in I$. For $i,j\in I$, let
${\mathcal{K}}_{ij}$ be the collection of $K_{\ell}$-copies containing
vertices $v_{i}\in V_{i}$ and $v_{j}\in V_{j}$ with $c(v_{i})=c(v_{j})$. We
will show that for all $i\neq j\in I$

$|{\mathcal{K}}_{ij}|\leq 3\alpha\vartheta p^{\binom{\ell}{2}}n^{\ell}.$
(4.11)

(This follows easily from Theorem 3.1 ( ) ‣ 3.1 when each colour class in
$V_{i}$ is of size $\alpha|V_{i}|$, but we need to be slightly more careful
about smaller vertex classes.)

Partition the colours in $c[V_{i}]$ into clusters $1,\ldots,m$ with $m\leq
2\alpha^{-1}$ such that for each $k\in[m]$, the proportion of vertices in
cluster $k$ in $V_{i}$ lies in $[\alpha,2\alpha]$. Note that such a partition
exists since $|c[V_{i}]|\leq\alpha|V_{i}|$ by ( ) ‣ 4.5 of Claim 4.5. For each
cluster $k\in[m]$, let $\beta(k)$ (resp. $\gamma(k)$) be the proportion of
vertices $v$ in $V_{i}$ (resp. $V_{j}$) such that $c(v)$ is in cluster $k$, so
$\alpha\leq\beta(k)\leq 2\alpha$. By Theorem 3.1 ( ) ‣ 3.1, the number of
$K_{\ell}$-copies with vertices in cluster $k$ in both $V_{i}$ and $V_{j}$ is
at most

$(\beta(k)\gamma(k)\vartheta+\varepsilon_{1})p^{\binom{\ell}{2}}n^{\ell}\leq(2\alpha\gamma(k)\vartheta+\varepsilon_{1})p^{\binom{\ell}{2}}n^{\ell}.$

Summing over $k\in[m]$, corresponding to clusters $1,\ldots,m$, and using
$\sum_{k\in[m]}\gamma(k)\leq 1$, we obtain

$|{\mathcal{K}}_{ij}|\leq\sum_{k\in[m]}(2\alpha\gamma(k)\vartheta+\varepsilon_{1})p^{\binom{\ell}{2}}n^{\ell}\leq(2\alpha\vartheta+2\alpha^{-1}\varepsilon_{1})p^{\binom{\ell}{2}}n^{\ell}.$

Taking $\varepsilon_{1}\leq\frac{1}{3}\alpha^{2}\vartheta$ implies (4.11).

The bound (4.11) holds for any $i,j$, so taking $\alpha<\nu/(4\ell^{2})$, we
obtain

$\left|\bigcup_{i<j\in I}{\mathcal{K}}_{ij}\right|\leq
3\ell^{2}\alpha\vartheta
p^{\binom{\ell}{2}}n^{\ell}\leq\frac{1}{4}\nu\vartheta
p^{\binom{\ell}{2}}n^{\ell}.$

Recalling that $F$ contains at least $\frac{1}{2}\nu\vartheta
p^{\binom{\ell}{2}}n^{\ell}$ copies of $K_{\ell}$, it follows that there is a
copy outside $\bigcup_{i<j\in I}{\mathcal{K}}_{ij}$, which is then strictly
min-coloured.

This completes the proof of Lemma 2.2.∎

######  Remark 4.6.

The fact that $K_{\ell}$ is a clique was only used to show that each copy of
$K_{\ell}$ in $F$ has at most one vertex in each $V_{i}$ for $i\in I$. In the
concluding remarks, we will discuss to what extent our proof extends to
general graphs $H$.

##  5\. Concluding remarks

###  5.1. Thresholds for canonical Ramsey properties for general graphs

Recall that for an ordered graph $H$, we defined $\hat{p}_{H}$ as the
threshold for the property
$G(n,p)\mathrel{\mathop{\longrightarrow}\limits^{\vbox
to0.0pt{\kern-2.1pt\hbox{$\scriptstyle*\hskip 1.0pt$}\vss}}}(H)$ and Theorem
1.3 establishes $\hat{p}_{K_{\ell}}=n^{-\frac{2}{\ell+1}}$. The problem of
determining the threshold $\hat{p}_{H}$ for ordered graphs $H$ which are not
complete is still open, but there are some partial results.

Firstly, Alvarado, Kohayakawa, Morris, and Mota [morris23pers] studied a
closely related problem for even cycles $C_{2\ell}$. Their result implies that
for $p=Cn^{-1/m_{2}(C_{2\ell})}\log n$, any colouring of $G(n,p)$ contains a
canonical copy of the cycle $C_{2\ell}$. However, in their work the ordering
of the random graph $G(n,p)$ is determined after the colouring.

Secondly, for a strictly balanced graph $H$, our proof guarantees for $p\gg
n^{-2/m_{2}(H)}$ a canonical copy of $H$, but one cannot require a specific
vertex ordering of $H$. This statement is shown using the following
modification of Theorem 4.1, which actually slightly simplifies the present
proof of Lemma 2.2 for $K_{\ell}$ as well, but at the expense of introducing
some additional formalism. For a collection of functions $f=(f_{e})_{e\in H}$,
define

$\Lambda^{\dagger}((f_{e})_{e\in H})=\sum_{u_{1},\ldots,u_{\ell}}\prod_{ij\in
H}f_{ij}(u_{i},u_{j}),$

that is, the density of $H$-copies in which the image of each edge $e\in H$ is
weighted by $f_{e}$. A small modification of Corollary 3.7 in [cg16] (which
appears in [cgss14] in order to prove Theorem 3.1) implies that if
$\|\mathfrak{f}_{e}-\mathfrak{d}_{e}\|=o(1)$ for $e\in E(H)$, then
$|\Lambda^{\dagger}((\mathfrak{f}_{e})_{e\in
H})-\Lambda^{\dagger}((\mathfrak{d}_{e})_{e\in H})|=o(1)$. Hence, using our
proof, we can find many embeddings $\zeta\colon H\longrightarrow G$ such that
if $ij\in E(H)$ with $i<j$, then $\zeta(i)\zeta(j)$ lies in $F_{i}$, so its
colour is determined by $\min(\zeta(i),\zeta(j))$.

###  5.2. Canonical colourings in random hypergraphs

Furthermore, it would be interesting to investigate extensions of Theorem 1.3
to $k$-uniform hypergraphs for $k\geq 3$. Namely, in their original work Erdős
and Rado [er50] established a canonical Ramsey theorem for $k$-uniform
hypergraphs. However, their proof for $k$-uniform hypergraphs used Ramsey’s
theorem for $2k$-uniform hypergraphs and this seems to be an obstacle for
transferring it to random hypergraphs at the right threshold. Hence, for
transferring their result to the random setting, it seems necessary to start
with a proof which avoids the use of hypergraphs with larger uniformity. Such
proofs can be found in [rrsss22, shelah95].

##  A. Transference

First we informally outline the proof of Theorem 9.3 from [cg16], which
corresponds to our Theorem 3.1. Then we state the formal claims that we need
from [cg16], and show how they are applied to deduce Theorem 4.1. Note that
the proof of Theorem 9.3 itself (as well as its corresponding deterministic
result, Theorem 4.10) is not actually spelled out in [cg16]. Instead, the
authors prove Theorem 9.1, which is a Ramsey-type result for $G(n,p)$, and say
that the proof of Theorem 9.3 is ‘much the same’. Moreover, their setting is
much more general – they work with random subsets of a set $X$, which for us
is just the set of edges of a complete graph $K_{n}$. In particular, for us,
$|X|=\binom{n}{2}$.

Theorem 9.3 from [cg16] states that with high probability, any subgraph $F$ of
$G(n,p)$ with $p=Cn^{-1/m_{2}(H)}$ can be approximated by a _dense model_ $D$
which asymptotically matches the edge distribution and the number of
$H$-copies in $F$.

As mentioned, instead of graphs, we work with functions from $[n]^{(2)}$ to
$\mathds{R}$, or weighted graphs. For a random graph $G\in G(n,p)$, the
_associated measure_ of $G$ is defined as $\mu=\mu_{G}=p^{-1}\mathds{1}_{G}$.
Given an $m$-tuple of functions
$\mu=(\mu_{1},\ldots,\mu_{m})\in\mathds{R}^{[n]^{(2)}}$ (which will later be
taken as the associated measures of $m$ independent copies of
$G(n,p_{\star})$), Conlon and Gowers introduce the set of $(\mu,1)$-basic
anti-uniform functions $\Phi_{\mu,1}$, which have the key property that the
number of $H$-copies in a weighted graph $\mathfrak{f}\leq
m^{-1}(\mu_{1}+\dots+\mu_{m})$ can be bounded in terms of the inner products

$\max\left\\{|\langle\mathfrak{f},\varphi\rangle|\colon\varphi\in\Phi_{\mu,1}\right\\}\,.$

The norm $\|\cdot\|$ is defined as

$\|\mathfrak{f}\|=\max\left\\{|\langle\mathfrak{f},\varphi\rangle|\colon\varphi\in\Phi_{\mu,1}\right\\}\cup\\{\|\mathfrak{f}\|_{\square}\\}\,,$

where the term $\|\mathfrak{f}\|_{\square}$ is just appended to ensure that
$\|\cdot\|$ also controls the edge distribution of a weighted graph. This
corresponds to Definition 4.9 from [cg16]. Note that in order for this norm to
be useful (that is, for the properties (P0)–(P3′)) below to be satisfied with
high probability), it is important that ${\|\mathfrak{f}\|_{\square}}$ can be
expressed in terms of inner products of $\mathfrak{f}$ with at most $2^{O(n)}$
functions, that is,

$\|\mathfrak{f}\|_{\square}=\max\left\\{|\langle\mathfrak{f},\mathds{1}_{[U,W]}+\mathds{1}_{[U\cap
W,U\cap W]}\rangle|\colon U,W\subset[n]\right\\}.$ (A.1)

One caveat in this description is that $\|\cdot\|$ only controls the number of
$H$-copies under certain deterministic conditions on $\mu_{1},\ldots,\mu_{m}$
(in the context of graphs, these conditions, denoted (P0)–(P3′) in [cg16],
imply the property that the corresponding random graphs have a sufficiently
homogeneous edges distribution, which is a well-known necessary condition for
all similar counting results in sparse random graphs). To prove Theorem 3.1,
Conlon and Gowers show three statements. Firstly, with high probability, the
associated measures $\mu_{1},\ldots,\mu_{m}$ of $G(n,p_{\star})$ with
$p_{\star}=Cn^{-1/m_{2}(H)}$ satisfy (P0)–(P3′)). Secondly, assuming
(P0)–(P3′), for any $\mathfrak{f}\leq m^{-1}(\mu_{1}+\dots+\mu_{m})$ there is
a _dense model_ $\mathfrak{d}\colon[n]^{(2)}\longrightarrow[0,1]$ with

$\|\mathfrak{f}-(1+\varepsilon)\mathfrak{d}\|\leq\varepsilon\,,$

and thirdly, $\mathfrak{d}$ is a useful approximation for $\mathfrak{f}$ in
our context.

These three statements imply that asymptotically almost surely, any such
function $\mathfrak{f}\leq m^{-1}(\mu_{1}+\dots+\mu_{m})$ has a suitable dense
model. To reach the same conclusion for subgraphs of $G(n,p)$, a small
additional step is needed (cf. Proof of Theorem 9.1 in [cg16]). Given $m$
independent samples of $G(n,p_{\star})$ with $p_{\star}=Cn^{-1/m_{2}(H)}$, let
$G$ be the union of $U_{1},U_{2},\ldots,U_{m}$. Then $G$ is distributed as
$G(n,p)$ with $p=1-(1-p_{\star})^{m}$, which is slightly smaller than
$p_{\star}m$. Thus the hypothesis $\mathfrak{f}\leq p^{-1}\mathds{1}_{G}$ does
not quite imply that $\mathfrak{f}\leq
m^{-1}p_{\star}^{-1}(\mathds{1}_{U_{1}}+\dots+\mathds{1}_{U_{m}})=m^{-1}(\mu_{1}\dots+\dots\mu_{m})$.
Still, since $p=p_{\star}m(1+o(1))$, this caveat can be resolved by slightly
rescaling $\mathfrak{f}$, which we do at the start of the proof.

Now we formally state the claims which are used for deducing Theorem 4.1, and
where they can be found in [cg16]. Say that $\mu_{1},\ldots,\mu_{m}$ satisfy
the property ${\mathcal{P}}(\eta,\lambda,d,m)$ if they satisfy properties
(P0)–(P3′) stated in [cg16]*Section 4. The following statement can be found in
the proof of Theorem 9.1 in [cg16].

######  Lemma A.1.

Given $\eta,\lambda,d,m$, there is $C$ such that for
$p_{\star}=Cn^{-1/m_{2}(H)}$ the following holds. If $U_{1},\ldots,U_{m}\in
G(n,p_{\star})$ are mutually independent and
$\mu_{i}=p_{\star}^{-1}\mathds{1}_{U_{i}}$ is the associated measure of
$U_{i}$ for $i\in[m]$, then $\mu_{1},\ldots,\mu_{m}$ satisfy
${\mathcal{P}}(\eta,\lambda,d,m)$ with high probability.

The following lemmata can be deduced from the proof of Theorem 4.5 in [cg16].

######  Lemma A.2.

Given $\varepsilon>0$, there are sufficiently small constants $\eta,\lambda>0$
and large integers $d,m$ such that if $\mu_{1},\ldots,\mu_{m}$ satisfy