Proof. Property [item:bound32max32deg] and the first part of property [item:few32F] are standard properties of the distribution of the edges and small subgraphs in \(G_{n,p}\) that can be proved using the second moment method and union bounds, see for example [23]. The ‘moreover’ part of property [item:few32F] follows from Markov’s inequality and a union bound over all \(F\) with \(v_F\leq 8\). Property [item:K210-count] also follows from Markov’s inequality. Indeed, we have that \[\mathbb{E}[N_{K_{2,10}}(G)]\le n^{12}p^{20}=n^{11}p^{18}\cdot{np^2},\] and \(np^2\ll 1\) due to the fact that \(p\ll n^{-1/2}\).

We will establish property [item:many32K3] using Corollary 7. To this end, fix any \(U \subseteq V(G)\) with \(|U|\ge \tfrac{n}{2}\), let \(X\mathrel{\vcenter{:}}= N_{K_3}(G[U])\) and note that \(\mu\mathrel{\vcenter{:}}=\mathbb{E}[N_{K_3}(G[U])] = \binom{|U|}{3}p^3\) for \(n\) large. Denoting by \(I_T\), for every triangle \(T\) in \(U\), the indicator random variable of the event that \(T\) appears in \(G\), we have \[\Delta\mathrel{\vcenter{:}}=\sum\left\{\mathbb{E}[I_TI_{T'}]: T,T' \text{ triangles in }K_n[U], E(T)\cap E(T')\neq \emptyset\right\} \leq \mu \cdot (1+ np^2)\le 2 \mu,\] where \(\mu\) accounts for a choice of \(T\), the first summand in the bracket accounts for a choice of \(T'\) such that \(|E(T')\cap E(T)|\ge 2\) (and hence \(T=T'\)) and the second summand accounts for a choice of \(T'\) such that \(|E(T)\cap E(T')|=1\); we also used that \(p\ll n^{-1/2}\) in the last inequality. By Corollary 7, with \(\Gamma = K_n[U]\) and \(\mathcal{A}\) the collection of all triangles in \(\Gamma\), the probability that every collection of pairwise edge-disjoint triangles in \(G[U]\) is smaller than \[D \mathrel{\vcenter{:}}= \frac{\mu^2}{800 \Delta} \ge \frac{\mu}{1600} \ge \frac{|U|^3p^3}{10000}\] is at most \(e^{-D}\). Property [item:many32K3] then follows from a union bound over the (less than \(2^n\)) choices of vertex subset \(U\), using that \(D\gg n\) for all such \(U\) because \(p\gg n^{-2/3}\).

Finally, in order to prove that \(G\) has [item:eAB-concentration], note that, for any choice of \(a,b\gg (\log n)^7 / p\) and \(A,B\subseteq V\) such that \(|A|\le a, |B|\le b\), we have that \(\mu \mathrel{\vcenter{:}}= \mathbb{E}[e(A,B)]=\left(|A||B|-\binom{|A\cap B|}{2}\right)p\le |A||B|p\). Moreover \(e(A,B)\) is binomially distributed and, setting \(k \mathrel{\vcenter{:}}= abp/\log^3n\), we have that \(\mu+k/3\le 2abp\). Hence, by Lemma 5, we have that \[\begin{align} \Pr\big[e(A,B)\ge |A||B|p+k\big] &\le \Pr\big[e(A,B)\ge \mu +k \big] \le \exp \left(-\frac{k^2}{2(\mu+k/3)}\right) \\ & \le \exp\left(-\frac{(abp)^2}{\log^6 n\cdot 4abp}\right) \le \exp\left(-\frac{abp}{4\log^6 n}\right). \end{align}\] Therefore, applying a union bound over the choice of \(a,b,A,B\), we get: \[\begin{align} \Pr\left[ G \notin~\ref{item:eAB-concentration} \right] & \le \sum _{a,b} \sum _{ \substack{ 1\le \alpha \le a \\ 1\le \beta \le b } } \binom{n}{\alpha} \cdot \binom{n}{\beta} \cdot \exp\left(-\frac{abp}{4\log^6 n}\right)\\ & \le \sum _{a,b} \sum _{ \substack{ 1\le \alpha \le a \\ 1\le \beta \le b } } n^\alpha \cdot n^\beta \cdot \exp\left(-\frac{abp}{4\log^6 n}\right)\\ & \le n^2\cdot \sum _{a,b } n^a \cdot n^b \cdot\exp\left(-\frac{abp}{4\log^6 n}\right) \\ & \le n^2\cdot \sum _{a,b} \exp \left( a\log n + b\log n - \frac{abp}{4\log ^6 n} \right), \end{align}\] where the (outer) sum goes over all choices of \(a=a(n)\in \mathbb{N}\) and \(b=b(n)\in \mathbb{N}\) such that \((\log n)^7 / p\ll a,b\le n\). For all such \(a,b\), we have that \(\frac{abp}{4\log ^6n} \gg a\log n,b\log n\), and so \[\Pr\left[ G \notin~\ref{item:eAB-concentration} \right] \le n^2 \cdot \sum _{a,b } n^{-g_{a,b}(n)} \ll 1,\] where \(g_{a,b}(n)= \frac{abp}{4\log ^7 n}- a - b \gg 1\) for all \(a,b\). ◻

Proof. Label the vertices of \(C\) as \(x,y,w,z\) so that \(e_1=xy\) and \(e_2=xw\). Further, for \(i=1,2\), let \(u_i\) be the vertex which forms the triangle with \(e_i\) given by the statement of the lemma; we therefore have that \(u_1\neq w\) and \(u_2\neq y\). We consider the following cases. Firstly, if one of the \(u_i\) is equal to \(z\), then the vertices of \(C\) host a \(K_4^-\) in \(G\) and we are done. So we can assume that neither \(u_i\) is equal to \(z\). If \(u_1=u_2\), then we get a copy of \(F_1^-\) that contains \(C\), whilst if \(u_1\neq u_2\), we get a copy of \(F_0^-\) containing \(C\). The moreover statement can also be easily checked in each case. ◻

Proof. Let \(e_1\) and \(e_2\) be the red edges in the copy of \(C_{rrbb}\). Condition [item:mostly32blue] in Definition 9 implies that each of these edges is in a triangle of \(G\). Moreover, \(G\) does not contain the edge \(e_3\) that forms a triangle with \(e_1\) and \(e_2\), as otherwise there would be no way to colour \(e_3\) without creating a monochromatic triangle, contradicting the fact that \(\varphi\) is triangle-free, which is condition [item:no32mc32tris] in Definition 9. ◻

Proof of Proposition 10. We first show the following claim.

Given \(G_1\) and a red/blue-colouring of its edges, we call an edge \(uv \in K_n\setminus G_1\) dangerous if there is a copy of \(C_{rrbb}\) in \(G_1\) with edges \(uw,wv,vx,xu\) for some vertices \(w, x \notin \{u,v\}\) such that \(uw, wv\) are coloured red and \(vx, xu\) are coloured blue.

In view of Claim 14, and again appealing to Fubini’s theorem, it suffices to show that for every instance of \(G_1\) that has the two properties described in the claim, every \(t\)-good colouring \(\varphi\) of \(G_1\) can be extended to a \(K_3\)-free colouring of \(G_1 \cup G_2\) for every instance of the graph \(G_2\) that satisfies the events described in both [cond:wb32mixed32F32and32K954] and [cond:no32dangerous32edges], which a.a.s.hold (for fixed \(G_1\) and \(\varphi\)). To this end, consider an arbitrary ordering of the edges of \(G_2\setminus G_1\) and colour them one-by-one according to the following rule. We colour \(e\in G_2\setminus G_1\) blue unless \(e\) forms a blue triangle with previously coloured edges (of \(G_1\cup G_2\)), in which case we colour \(e\) red. We claim that the resulting colouring of \(G_1 \cup G_2\) is \(K_3\)-free.

Note that the only possible monochromatic triangles that can occur in our colouring of \(G_1 \cup G_2\) must be red and contain an edge of \(G_2\setminus G_1\), as \(\varphi\) is good and thus triangle-free. Suppose that \(e\) is the last edge of \(G_2\setminus G_1\) that completes a red triangle; denote this triangle by \(T\) and its two remaining edges by \(f_{r}\) and \(g_r\). Note that \(e\) is also contained in a triangle with two blue edges, say \(f_b\) and \(g_b\), already coloured in \(G_1\cup G_2\), as otherwise our rule would colour \(e\) blue. We claim that \(f_r\) and \(g_r\) are both contained in triangles other than \(T\) in \(G_1 \cup G_2\). Indeed, let \(h \in \{ f_r, g_r\}\) be arbitrary. If \(h \in G_1\), then \(h\) must be contained in a (non-monochromatic) triangle of \(G_1\) due to the fact that our colouring of \(G_1\) was good and the fact that \(h\) is coloured red. If \(h \in G_2 \setminus G_1\), then it must be contained in a triangle whose remaining two edges are blue, as otherwise we would have coloured it blue. Consequently, by Lemma 11, we have that the \(4\)-cycle \(C \mathrel{\vcenter{:}}= \{f_r,g_r,f_b,g_b\}\) is contained in a copy of \(F^-\) in \(G_1\cup G_2\), for some \(F\in\{F_0,F_1,K_4\}\), and the edge \(e\) completes this copy of \(F^-\) to a copy of \(F\). However, as we have assumed that \(G_2\) contains no dangerous edges, one of the edges of the \(C_{rrbb}\)-copy \(C\mathrel{\vcenter{:}}=\{f_r,g_r,f_b,g_b\}\) must belong to \(G_2\). This contradicts the assumed conclusion of [cond:wb32mixed32F32and32K954], as the copy of \(F\) containing \(C\) has at least two edges in \(G_2\), namely \(e\) and one of the edges in \(C\). This shows that no red triangle can occur, which concludes the proof of the proposition. ◻

Proof. By Proposition 10, it suffices to show that a.a.s.\(G_1\sim G_{n,p}\) admits a \(t\)-good colouring \(\varphi\) with \(t=150n^6p^8\). Firstly, we claim that a.a.s.\(G_1\) contains at most \(n^6p^8\) copies of \(F^-\), for each \(F\in \{F_0, F_1,K_4\}\). Indeed, this follows from Lemma 8 [item:few32F], which applies since \(m(F_0^-) = 4/3\), \(m(F_1^-) = 7/5\), and \(m(K_4^-) = 5/4\), and the fact that \(n^4p^5, n^5p^7\ll n^6p^8\) for \(p\gg n^{-2/3}\). We also have that a.a.s. \(G_1\) is not \(K_3\)-Ramsey due to Theorem 1 [triangle32ramsey32032statement]. It is therefore enough to show that \(G_1\) admits a \(t\)-good colouring \(\varphi\) under the assumption that these two asymptotically-almost-sure events occur.

We define \(\varphi\) as follows. Take any triangle-free colouring of \(G_1\) and recolour any edge not in a triangle blue. As we only changed the colour of edges not in triangles, it is clear that \(\varphi\) remains triangle-free; it only remains to show that \(\varphi\) induces at most \(t\) copies of \(C_{rrbb}\). This follows from Corollary 12, as each copy of \(C_{rrbb}\) is contained in some copy of \(F^-\) for some \(F\in\{F_0, F_1,K_4\}\). Each such copy of some \(F^-\) with \(F\in\{F_0, F_1,K_4\}\), hosts at most⁷ \(50\) copies of \(C_{rrbb}\) and so the number of \(C_{rrbb}\) is at most \(50\) times the number of copies of some \(F^-\) with \(F\in\{F_0, F_1,K_4\}\). This completes the proof due to our upper bounds on the number of these copies above. ◻

Proof of Theorem 17. By Proposition 10, it suffices to show that a.a.s.\(G_1\) admits a \(t\)-good colouring with \(t \mathrel{\vcenter{:}}= n^3p^{7/2}\). Let us assume the asymptotically-almost-sure conclusions of Lemma 20 and Lemma 8 [item:few32F] and also that \(G_1\) is not \(K_3\)-Ramsey, which happens a.a.s.due to Theorem 1 [triangle32ramsey32032statement].

We colour the edges of \(G_1\) according to the following scheme, where we define \(\mathcal{C}(G_1)\) to be the collection of collages \(C \in \mathcal{C}\) such that \(C \subseteq G_1\):

1. Colour all maximal subgraphs \(C\in \mathcal{C}(G_1)\) which are very well-behaved with a very good colouring (this is possible, due to Lemma 21).

2. Colour all the other maximal subgraphs in \(\mathcal{C}(G_1)\) in a triangle-free way, such that all edges not in a triangle are blue (this is possible as \(G_1\) is not \(K_3\)-Ramsey).

We claim that the resulting colouring is \(t\)-good. Firstly, note that all edges of \(G_1\) are indeed coloured as every edge of \(G_1\) lies in some maximal collage contained in \(G_1\) (the collage may just consist of the single edge). Clearly, all edges not in a triangle are coloured blue. Moreover, as every triangle of \(G_1\) lies in some maximal collage, the resulting colouring contains no monochromatic triangles. It remains to show that there are at most \(t\) copies of \(C_{rrbb}\).

Corollary 12 implies that any copy of \(C_{rrbb}\) must lie in some copy of \(F_1^-\), \(F_0^-\), or \(K_4^-\). However, each of these graphs is contained in some maximal collage (they all induce connected subhypergraphs in \(H\)) and thus all copies of \(C_{rrbb}\) are contained in maximal collages that are not very well-behaved. It thus suffices to show that the total number of \(4\)-cycles that lie in such collages is at most \(t\). By the assumed conclusion of Lemma 20, every \(C\in \mathcal{C}(G_1)\) is well-behaved, and so if \(C\) is not very well-behaved, then it contains some copy of a subgraph \(F\) with \(v_F\) vertices and \(e_F\) edges such that \((v_F,e_F)\in\{(4,6),(5,7),(8,12)\}.\) However, the assumed conclusion of Lemma 8 [item:few32F] implies that there are at most \[n^4p^6\log n+\binom{\binom{5}{2}}{7}n^5p^7\log n+\binom{\binom{8}{2}}{12}n^8p^{12}\log n\leq 2^{10}n^5p^7\log n\] copies of such an \(F\) in \(G_1\) (using that \(n^4p^6\ll n^8p^{12}\ll n^5p^7\) here). Therefore, there are at most \(2^{10}n^5p^7\log n\) maximal collages \(C\in \mathcal{C}(G_1)\) that are not very well-behaved. A collage \(C\in \mathcal{C}(G_1)\) contains at most \(v(C)^4\) copies of 4-cycles, and each collage \(C\in \mathcal{C}(G_1)\) has at most \(\log n\) vertices on account of it being well-behaved. So in total, there are at most \(2^{10}n^5p^7 \cdot \log^5n\ll n^3p^{7/2}\) copies of \(C_{rrbb}\) in our colouring of \(G_1\), finishing our proof. ◻

Proof of Lemma 20. Let \(\mathcal{C}_{\textrm{bad}}\) be the collection of all \(C \in \mathcal{C}\) such that either \(e(C) / v(C) \ge 5/3\) or \(v(C) \ge \log n\). It suffices to show that a.a.s.\(G_1 \sim G_{n,p}\) does not contain any subgraphs in \(\mathcal{C}_{\textrm{bad}}\). In fact, we will focus on another family \(\mathcal{C}^*\) of (nonempty) subgraphs of \(K_n\) with the following properties:

1. Every set in \(\mathcal{C}_{\textrm{bad}}\) contains some element of \(\mathcal{C}^*\).

2. Every \(C^* \in \mathcal{C}^*\) satisfies \(e(C^*) \ge 5v(C^*)/3\) or both \(v(C^*) \ge \log n\) and \(e(C^*) \ge 5v(C^*)/3-3\).

3. For every \(5\le k\le n\), there are at most \((2k)^{150}(16n)^k\) graphs \(C^* \in \mathcal{C}^*\) with \(v(C^*) = k\).

Assuming we can find such a family \(\mathcal{C}^*\) of subgraphs, we claim that we are done. Indeed, by [item:Ccores-1], \[\Pr[\exists C \in \mathcal{C}_{\textrm{bad}}: C \subseteq G_1] \le \Pr[\exists C^* \in \mathcal{C}^*:C^* \subseteq G_1] \le \sum_{C^* \in \mathcal{C}^*} p^{e(C^*)}.\] Moreover, by [item:Ccores-2] and [item:Ccores-3], \[\sum_{C^* \in \mathcal{C}^*} p^{e(C^*)} = \sum^n_{k=5} \sum_{\substack{C^* \in \mathcal{C}^*\\ v(C^*) = k}} p^{e(C^*)} \le \sum^{\log n}_{k =5} (2k)^{150} (16n)^k p^{5k/3} + \sum^{n}_{k =\log n} (2k)^{150} (16n)^k p^{5k/3-3} \ll 1,\] where the last inequality follows from the assumption that \(p \ll n^{-3/5}\). We also used that [item:Ccores-2] easily implies that there are no \(C^*\in \mathcal{C}^*\) with less than 5 vertices.

It remains to define a family \(\mathcal{C}^*\) of subgraphs of \(K_n\) satisfying conditions [item:Ccores-1]–[item:Ccores-3] above. First, we fix some order \(\sigma\) on \(E(K_n)\). Now given a collage \(C \in \mathcal{C}_{\textrm{bad}}\), we construct the ‘core’ of \(C\) algorithmically as follows. We initiate our algorithm with logs \(L_V\), \(L_E\), \(L_T\), \(L_O\) and \(L_D\) all being empty. Throughout the algorithm, we will have that \(L_V\) is a sequence of distinct vertices in \(V(C)\subseteq V(K_n)\), \(L_E\) and \(L_T\) are sequences of distinct edges in \(E(C)\subseteq E(K_n)\), \(L_O\) is a sequence of integers and \(L_D\) is a sequence whose each entry indicates a time step \(i\geq 0\) and some set of edges \(F\subseteq E(C)\subseteq E(K_n)\). We will maintain, at the end of every time step \(i\geq 0\) of the algorithm, that the set of vertices in \(L_V\) and the set of edges in \(L_E\) define a subgraph of \(C\), which we denote as \(C_i\) (and so \(C_0\) is the empty graph). Moreover at the end of each time step \(i\geq 0\), the collection of edges featuring in \(L_T\) will be precisely those edges in \(L_E\) which are contained in a triangle in \(C_i\).

Now, in the first step of the algorithm, we take \(e_1\in C\) to be the first edge in \(C_1\) according to the order \(\sigma\) on \(E(K_n)\), add its endpoints (in an arbitrary order) to \(L_V\) and add \(e_1\) to \(L_E\) (so that \(C_1\) is the one-edge graph \(e_1\)). In every subsequent step \(i\geq 2\), we do the following:

• We terminate and output \(C^*=C_{i-1}\) if one of the following is true: \[|L_D|=7, \qquad |L_V|\geq \log n \qquad \text{or} \qquad C_{i-1}=C.\]

• Otherwise, since \(C_{i-1} \neq C\) and \(C\) is a collage, there must be a copy of \(K_3\), \(F_0^-\) or \(F_1^-\) in \(C\) that intersects \(C_{i-1}\) in at least one edge but is not fully contained in \(C_{i-1}\). Call such a copy regular if it is a copy of \(F_0^-\) and it intersects \(C_{i-1}\) in a triangle; otherwise, call it degenerate. We say that a regular copy of \(F_0^-\) is rooted at \(e\) if \(e\) belongs to its intersection with \(C_{i-1}\) and it is the edge of the triangle that also participates in the (unique) \(4\)-cycle of \(F_0^-\).

  • If there exist regular copies of \(F_0^-\), then to each copy associate a number \(x\in \mathbb{N}\) which is the position in \(L_T\) of the edge \(e_x\) that the copy is rooted at. Take a copy of \(F_0^-\) that minimises this position and add this minimum \(x\) to \(L_O\) if the vertices of \(e_x\) appear in \(L_V\) in an order consistent with their degrees in the copy of \(F_0^-\). If, on the other hand, the vertex of \(e_x\) which has degree 4 in the copy of \(F_0^-\) appears in \(L_V\) before the vertex of \(e_x\) with degree 3, we add \(-x\) to \(L_O\). We also update \(L_V\) and \(L_E\) by appending the vertices and the edges of our copy of \(F_0^-\) that do not lie in \(C_{i-1}\): the five such edges are added according to their relative order in \(\sigma\) and the three vertices in some canonical order. Note that this defines \(C_i\) with \(e(C_i) = e(C_{i-1}) + 5\) and \(v(C_i) = v(C_{i-1})+3\). Finally, we add to \(L_T\) all edges that are in a triangle in \(C_i\) but not in a triangle in \(C_{i-1}\), adding them in the order that they appear in \(L_E\).

  • If there are no regular copies of \(F_0^-\), fix some degenerate copy of \(K_3\), \(F_0^-\) or \(F_1^-\), append to \(L_V\) and to \(L_E\) the vertices and the edges of this copy that do not lie in \(C_{i-1}\): the edges are added according to their relative order in \(\sigma\) and the vertices (if there are any) in an arbitrary order; this again defines \(C_i\). We then add to \(L_T\) all edges that are in a triangle in \(C_i\) but not in a triangle in \(C_{i-1}\), adding them in the order that they appear in \(L_E\). Finally, detail this degenerate step \(i\) by logging it in \(L_D\) along with the set of edges in \(E(C_i)\setminus E(C_{i-1})\).

Since each step increases \(L_E\) by at least one, this algorithm terminates for any \(C\in \mathcal{C}_{\textrm{bad}}\). We may thus define \(\mathcal{C}^*\) as the set of all its outputs, that is, \(\mathcal{C}^*\mathrel{\vcenter{:}}= \{C^* : C \in \mathcal{C}_{\textrm{bad}}\}\). This definition guarantees that \(\mathcal{C}^*\) satisfies [item:Ccores-1] above; we will show that it also satisfies [item:Ccores-2] and [item:Ccores-3]. First though we establish the following key estimate that bounds the distance of \(e(C_i)\) from \(5v(C_i)/3\) in terms of the number of degenerate steps (equivalently, the size of \(|L_D|\)) at the end of step \(i\), which we denote by \(d(i)\).

Property [item:Ccores-2] now follows from Claim 22. Indeed, if \(C^*=C\) and \(v(C^*)<\log n\) then certainly \(e(C^*)\geq 5v(C^*)/3\) as \(C\in \mathcal{C}_{\textrm{bad}}\). If \(C^*\neq C\) and \(v(C^*) < \log n\), then at the time \(\tau\) at which the algorithm terminates we have that \(C^*=C_{\tau-1}\) and \(d(\tau-1)=7\) and so \(0\le 3e(C^*)-5v(C^*)\) as required. Finally if \(v(C^*)\geq \log n\), the lower bound on \(e(C^*)\) also follows from Claim 22, using that, trivially, \(0\) is a lower bound on the number of degenerate steps taken when the algorithm terminates.

It remains to prove property [item:Ccores-3] of the collection \(\mathcal{C}^*\), so let us fix some \(5\leq k \leq n\). We bound the number of \(C^*\in \mathcal{C}^*\) with \(v(C^*)=k\) as follows. Firstly, we note that \(C^*\) can be completely determined by the logs \(L_V, L_O\) and \(L_D\) when the algorithm terminates. That is, we can recover \(L_E\) (and \(L_T\)) from these logs. Indeed, the first two vertices in \(L_V\) determine the first edge in \(L_E\). Now, suppose we have recovered \(L_E\) and \(L_T\) up to time \(i-1\) and consider time step \(i\). If the step is not degenerate (which we know from \(L_D\)), the new edges of the regular copy of \(F_0^-\) are completely determined by the edge that the copy is rooted at, which we know from \(L_O\) and our recovery of \(L_T\) so far, which vertex of this edge has degree 4 in the copy of \(F_0^-\), which we know from the sign of the entry in \(L_O\) and the order of the vertices of this edge in \(L_V\), and the next three vertices, which appear (in a canonical order) in \(L_V\). Hence, we can add the new edges (in order according to the order \(\sigma\) on \(E(K_n)\)) to \(L_E\) and recover \(L_E\) up to time \(i\). If, on the other hand, the step \(i\) is degenerate, then \(L_D\) will signify this and indicate the new edges that need to be added to \(L_E\). Again the order they are added is determined by \(\sigma\). In either case, once we know \(L_E\) at time \(i\), we can recover \(L_T\) up to time \(i\) also.

This shows that in order to bound the number of \(C^*\) with \(v(C^*)=k\), it suffices to bound the number of possibilities for the logs \(L_V,L_O\) and \(L_D\) output by the algorithm with \(|L_V|=k\). For the logs \(L_V\), we use the simple upper bound that there are at most \(n^k\) choices. For the logs \(L_O\), note first that Claim 22 implies that any \(C^*\) with \(v(C^*)=k\) has \[e(C^*)\le \frac{5k+21\cdot 7}{3}\le 2k+49,\] using here that there are at most \(7\) degenerate steps before the algorithm terminates. Now for any log \(L_O\), let \(L_O^{|\cdot|}\) be the log obtained from \(L_O\) by replacing each entry by its absolute value. In each instance of the algorithm, we therefore have that the log \(L^{|\cdot|}_O\) is a nondecreasing sequence of natural numbers bounded by \(e(C^*)\leq 2k+49\). Moreover, the length of the sequence is the number of regular steps which is certainly less than \(k\) and we can append repeated entries with value \(2k+50\) to make all the sequences length \(k\). Hence we can bound the number of possible \(L^{|\cdot|}_O\) by the number of nondecreasing sequences of length \(k\) with elements in \(\{1, \dotsc, 2k+50\}\), which is \(\binom{k+(2k+50)-1}{k}\le 2^{3k+50}\). The log \(L_O\) can then be recovered from \(L^{|\cdot|}_O\) by a choice of sign for the at most \(k\) entries. Finally, each of the at most 7 entries of \(L_D\) indicates a step (at most \(k+7\) choices) and a selection of at most 7 edges which lie on vertices in \(L_V\) (at most \(k^2\) choices for each edge). Hence there at most \(\sum_{j=0}^7((k+7)(\sum_{h=1}^7(k^2)^h))^j\le k^{140}\) choices for \(L_D\). Combining our estimates of the number of choices of \(L_V,L_O\) and \(L_D\) gives [item:Ccores-3] and completes the proof of Lemma 20. ◻

Proof of Lemma 21. Assume the contrary and let \(C \in \mathcal{C}\) be a smallest counterexample. We claim that every proper subgraph \(D \subsetneq C\) admits a very good colouring. Indeed, let \(D = D_1 \cup \dotsb \cup D_t\) be the partition of \(D\) into maximal collages and note each \(D_i\) is also very well-behaved. Since \(C\) is a smallest counterexample, each \(D_i\) admits a very good colouring. We claim that the union of these colourings is a very good colouring of \(D\). Indeed, every triangle in \(D\) is contained in some \(D_i\) (as it is a maximal collage) and thus it is not monochromatic. It is clear that every edge not in a triangle is coloured blue. If there was a copy of \(C_{rrbb}\) in \(D\), it would lie in some copy of \(F_0^-\), \(F_1^-\) or \(K_4^-\), by Corollary 12, and thus it would lie in some \(D_i\) (as each of \(F_0^-\), \(F_1^-\) and \(K_4^-\) induces a connected subhypergraph of \(H\)), a contradiction.

Our aim is now to remove from \(C\) a carefully chosen selection of edges and show that any very good colouring of the remaining subgraph (which exists, from above) can be extended to the removed edges while remaining very good, thus contradicting our assumption that \(C\) is a counterexample. In order to find such a removable set of edges, we define a discharging procedure which assigns weights to small subgraphs of \(C\) that we call blocks.

To define our blocks, notice that condition [wb:subgraph] of Definition 19 implies that \(C\) does not contain copies of \(K_4\) and the graphs \(F_2\) and \(F_3\) depicted in Figure 2. This in turn implies that every triangle in \(C\) shares edges with at most one other triangle in \(C\). We define our blocks \(\mathcal{B}=\mathcal{B}(C)\) to be all copies of \(K_4^-\) in \(C\) and all triangles in \(C\) that are not contained in a \(K_4^-\); this definition guarantees that blocks are pairwise edge-disjoint. Fix an ordering \(\sigma\) of \(\mathcal{B}\) such that every triangle in \(\mathcal{B}\) precedes every copy of \(K_4^-\) and assign weights to the blocks in \(\mathcal{B}\) as follows:

1. Assign weight \(5\) to each vertex of \(C\) and weight \(-3\) to each edge.

2. For every \(v\in V(C)\) contained in exactly one block, send its weight to this block.

3. For every vertex \(v\in V(C)\) contained in more than one block, redistribute its weight equally to the two smallest blocks that contain \(v\) according to the ordering \(\sigma\) on \(\mathcal{B}\). Note that in this step, if \(v\) is a vertex in \(i\geq 0\) triangles in \(\mathcal{B}\), then \(i'\mathrel{\vcenter{:}}=\min\{i,2\}\) triangles containing \(v\) and \(2-i'\) copies of \(K_4^-\) containing \(v\) increase their weight by \(5/2\).

4. For every \(e\in E(C)\) contained in a block, redistribute its weight to the block containing it (recall that blocks are pairwise edge-disjoint).

5. For every \(v\in V(C)\) not contained in a block, redistribute its weight equally to the edges incident to \(v\) (note that these edges were not yet handled, since they are also not in a block).

6. For every \(e\in E(C)\) not contained in a block, redistribute its weight in the following way: Since \(e\) belongs to a copy of \(F_0^-\) or \(F_1^-\), at least one of its endpoints must also be a vertex in a block.

   1. If only one of the endpoints belongs to some block, distribute \(e\)’s weight equally among all the blocks it belongs to.

   2. Otherwise, split \(e\)’s weight equally among its two endpoints and, for each of the endpoints, distribute the weight equally among all its blocks.

Note that by the end of this process, the total weight of all the edges and vertices in \(C\) has been redistributed to \(\mathcal{B}\), and the total weight remains unchanged. By our assumption that \(e(C)/v(C) < 5/3\), the total weight of the vertices and edges before redistribution to blocks was positive, and therefore so is the total weight of all the blocks. Therefore, \(C\) must contain (at least) one positive-weight block \(X\in \mathcal{B}\). We will split the argument into two cases, depending on whether \(X\) is a copy of \(K_3\) or \(K_4^-\). In each case, we will find a removable set of edges. Before embarking on this, we prove a technical claim that allows us to reason about the weight of \(X\) by inspecting the graph \(C\) locally, without knowledge of the whole of \(C\).

Before proving these claims, let us see how we can use them to contradict our assumption that \(C\) is a minimal counterexample. Firstly, consider the case that our positive-weight block \(X\) is a triangle. Let \(e\) be an edge of \(X\) from the assertion of Claim 24. As shown at the beginning of the proof, \(C\setminus \{e\}\) has a very good colouring. We may extend this colouring to a very good colouring of \(C\) as follows. We colour \(e\) blue unless the other two edges of \(X\) are coloured blue, in which case we colour \(e\) red. As \(X\) is the only triangle containing \(e\), the colouring remains triangle-free and every edge of \(C\) that is not in a triangle is still coloured blue. Thus, we just need to show that there are no copies of \(C_{rrbb}\) in \(C\), see property [item:few32Crrbbs] of Definition 9. Suppose that there was such a copy. As the colouring of \(C\setminus \{e\}\) is very good, this copy of \(C_{rrbb}\) would contain \(e\). Corollary 12 would then imply that \(e\) lies in the \(4\)-cycle in a copy of \(K_4^-\), contradicting the assumption that \(X\) is a block, a copy of \(F_0^-\), contrary to our choice of \(e\), or a copy of \(F_1^-\), contradicting the property [wb:subgraph] of being very well-behaved.

The case when \(X\) is a copy of \(K_4^-\) is resolved similarly. Without loss of generality, we can assume that the edges of \(X\) are labelled as in Claim 25 and neither \(e_1\) nor \(f_1\) belong to a \(4\)-cycle in a copy of \(F_0^-\). As above, \(C \setminus \{e_1,f_1\}\) has a very good colouring, which we may extend to a very good colouring of \(C\) as follows. We colour \(e_1\) red and \(f_1\) blue unless that creates a copy of \(C_{rrbb}\) with the edges \(e_2\) and \(f_2\), in which case we colour \(e_1\) blue and \(f_1\) red. We claim that this gives a very good colouring of \(C\). Since the only triangle in \(C\) containing \(e_1\) or \(f_1\) is the triangle containing both of them, the colouring remains triangle-free; every edge not in a triangle is still blue. We just need to verify that there are no copies of \(C_{rrbb}\). As in the previous case, we can apply Corollary 12 and rule out that \(e_1\) and \(f_1\) are in copies of \(F_1^-\) and \(F_0^-\) using condition [wb:subgraph] of being very well-behaved and the key property of \(e_1\) and \(f_1\) coming from Claim 25. The only case left to consider then, is that \(e_1\) or \(f_1\) lie in some copy of \(C_{rrbb}\) that lies in a copy of \(K_4^-\) in \(C\). Since \(C\) is \(\{ K_4, F_2, F_3 \}\)-free, the only copy of \(K_4^-\) containing our copy of \(C_{rrbb}\) is \(X\) itself, which is impossible, as we coloured \(X\) to avoid having a copy of \(C_{rrbb}\).

Now that we have proved that Claims 24 and 25 contradict the assumption that \(C\) is a minimal counterexample, it remains only to prove these two claims.

Proof of Claim 24. Denote \(V(X)=\{x,y,z\}\) and suppose towards a contradiction that each of \(xy\), \(xz\) and \(yz\) belongs to a \(4\)-cycle in some copy of \(F_0^-\). To get a contradiction, due to Claim 23, it suffices to show that there is some \(C^{\prime} \subseteq C\) such that \(\mathcal{B}(C)=\mathcal{B}(C^{\prime})\) and \(w_{C^{\prime}}(X) \le 0\).

We begin by considering \(C'\) to be the union of all the triangles in \(C\) (so that \(\mathcal{B}(C)=\mathcal{B}(C')\)). By our assumption, each edge of \(X\) must share a vertex with a triangle other than \(X\); indeed, otherwise it cannot lie on a \(4\)-cycle in a copy of \(F_0^-\). Consequently, at least two of \(X\)’s vertices, say \(y\) and \(z\), are also in other triangles and hence blocks. Therefore, their contribution to \(X\)’s weight (in stage [stage:3] of the weight redistribution process) is at most \(5/2\) each, and so \(w_{C'}(X) \le 1\). We may further assume that \(x\) does not lie in an additional triangle, since otherwise \(w_{C'}(X) \le -3/2\), see Figure 3.

Now, since both \(xy\) and \(xz\) are in some copies of \(F_0^-\) and \(X\) is the only triangle that \(x\) belongs to, \(C\) must have an edge \(xv\) that does not lie in a block; we now add \(xv\) to \(C'\). If \(v\) supported a triangle (and hence a block) in \(C\), then \(xv\) would contribute \(-3/2\) to \(w_{C'}(X)\) in stage [stage:6] of the weight redistribution process and therefore \(w_{C'}(X)\le -1/2\) would be negative (see Figure 4 for illustration). We may thus further assume that \(v\) does not belong to a triangle in \(C\). Now, add to \(C'\) all edges in copies of \(F_0^-\) that contain one of \(xy\), \(xz\). If \(xv\) lied in a \(4\)-cycle containing \(xy\) and in a \(4\)-cycle containing \(xz\), we would have that \(d_{C'}(v) \ge 3\) and so \(xv\) would have weight at most \(-3+5/3 = -4/3\) after stage [stage:5], all of which would go to \(X\) in stage [stage:6], and once again \(w_{C'}(X) \le -1/3\) would be negative. Thus, the \(4\)-cycles containing \(xy\) and \(xz\) do not share edges so there must be a vertex \(u \neq v\) such that \(xu \in C'\). The contribution of each of \(xu\) and \(xv\) to \(X\)’s weight is at most \(-1/2\) and therefore \(w_{C'}(X) \le 0\), a contradiction. This concludes the proof of Claim 24. ◻

Proof of Claim 25. Denote \(V(X)=\{x_1,x_2,y,z\}\) so that \(g=yz\) and \(e_i = x_iy, f_i =x_iz\) for \(i \in \{1, 2\}\). Assume towards contradiction that one of \(e_1, f_1\) as well as one of \(e_2, f_2\) belongs to a 4-cycle in a copy of \(F_0^-\). We let \(C'\) be the union of all triangles in \(C\), so that \(\mathcal{B}(C') = \mathcal{B}(C)\). By Claim 23, it is enough to show that \(w_{C'}(X) \le 0\).

Now, note that stage [stage:4] of the redistribution process on \(C'\) moves weight from the edges of \(X\) to \(X\). If two or more vertices of \(X\) belonged to blocks other than \(X\), then the contribution to \(X\)’s weight coming from its vertices, in stages [stage:2] and [stage:3], would be at most \(2\cdot 5+2\cdot(5/2)\leq 15\) and we would have \(w_{C'}(X)\leq 0\). Hence, it must be the case that at most one vertex in \(X\) belongs to a block that is not \(X\). Moreover, if none of \(y,z,x_i\) belonged to a block other than \(X\), then none of \(e_{i}, f_{i}\) would be contained in a 4-cycle of a copy of \(F_0^-\). Consequently, one of \(y, z\) must belong to a block other than \(X\); without loss of generality, assume that \(y\) is the only vertex of \(X\) contained in a block other than \(X\). Since neither \(f_1\) nor \(f_2\) can lie in a \(4\)-cycle of a copy of \(F_0^-\), it must be that both \(e_1\) and \(e_2\) do.

For each \(i \in \{1, 2\}\), denote by \(C_i\) the \(4\)-cycle in a copy of \(F_0^-\) that passes through \(e_i\). We claim that \(e_i\) is the only edge of \(X\) in \(C_i\). Indeed, the union of a copy of \(K_4^-\) and a copy of \(F_0^-\) whose \(4\)-cycle intersects this \(K_4^-\) in more than one edge contains a copy of \(F_2\), \(F_3\) or \(F_4\) depicted in Figure 2. However, \(C\) cannot contain any of these graphs, see condition [wb:subgraph] in Definition 19. Further, the second edge of \(C_i\) that is incident with \(y\) belongs to some block \(X_i' \neq X\). We claim that \(X_i'\) is not a copy of \(K_4^-\). Indeed, if it were, then \(X \cup X_i' \cup C_i\) would be a copy of either \(F_5, F_5'\) or \(F_5''\) from Figure 5 (recall that \(C_i\) is not allowed to intersect a copy of \(K_4^-\) in more than one edge) and this graph is too dense to be contained in \(C\), see condition [wb:subgraph] in Definition 19. Therefore, both \(X_1'\) and \(X_2'\) are triangle blocks. Finally, if \(X_1' \neq X_2'\), then, since the ordering \(\sigma\) prioritises triangles over copies of \(K_4^-\), the vertex \(y\) would give none of its weight to \(X\) in stage [stage:3] of the redistribution process, yielding \(w_{C'}(X)\leq 0\), as desired. Thus \(X' \mathrel{\vcenter{:}}= X_1' = X_2'\) is a triangle block. Moreover, each \(C_i\) shares only one edge with \(X'\), as otherwise \(X' \cup C_i\) would be a copy of \(K_4^-\), which is impossible due to the assumption that \(X'\) is a triangle block. Consequently, each \(C_i\) contains a unique vertex \(w_i \notin V(X) \cup V(X')\). If \(w_1 = w_2\), then \(X \cup C_1 \cup C_2\) contains a copy of \(F_4\), which is too dense to be contained in \(C\), so we may assume that \(w_1 \neq w_2\). But then, \(X \cup X' \cup C_1 \cup C_2\) would be a copy of one of \(F_6\) or \(F_6'\) from Figure 5, a contradiction. ◻

This concludes the proof of Lemma 21. ◻

Proof of Proposition 26. Fix some \(G_1\) satisfying property [item:K210-count] of Lemma 8 (which occurs a.a.s.) and some colouring \(\varphi \colon E(G_1)\to \{\mathrm{red},\mathrm{blue}\}\) that contains at least \(t\) copies of \(C_{rrbb}\). Recall that a pair of vertices \(\{x,y\} \in E(K_n)\) is dangerous if it is the ‘colour-splitting’ diagonal of at least one such \(C_{rrbb}\), that is, if there exist \(u,v\in V(G_1)\setminus \{x,y\}\) with \(xu,yu,xv,yv\in E(G_1)\), \(\varphi(xu)=\varphi(yu)=\mathrm{blue}\) and \(\varphi(xv)=\varphi(yv)=\mathrm{red}\), see Figure 6. We will show that there are at least \(t/50\) dangerous pairs. Note that this immediately implies the assertion of the lemma. Indeed, the number of dangerous pairs that appear in \(G_{n,q}\) is bounded from below by a \(\mathrm{Bin}(t/50, q)\), which is positive with probability \(1-o(1)\), by our assumption that \(tq \gg 1\).

Let \(D\) be the collection of dangerous pairs. For each pair \(\rho\in D\), let \(r_\rho\geq 1\) be the number of red copies of \(K_{1,2}\) in \(G_1\) that form a triangle with \(\rho\) and likewise let \(b_\rho\) be the number of blue copies of \(K_{1,2}\) in \(G_1\) that form a triangle with \(\rho\), so that \(\rho\) is the colour-splitting diagonal for \(r_\rho b_\rho\) copies of \(C_{rrbb}\) in \(G_1\) and \(\sum_{\rho\in D}r_\rho b_\rho\geq t\). We further say that \(\rho\in D\) is heavy if \(r_\rho b_\rho\geq 25\) and let \(D_H\subseteq D\) be the collection of heavy dangerous pairs. Now, for each heavy pair \(\rho\), by the AM-GM inequality, we have that \(r_\rho+b_\rho\geq 2\sqrt{r_\rho b_\rho}\geq 10\) and \(\rho\) forms the part of size 2 in \(\binom{r_\rho + b_\rho}{10}\) copies of \(K_{2,10}\). Therefore, by the assumed conclusion of Lemma 8 [item:K210-count], \[\sum_{\rho\in D_H}\frac{r_\rho b_\rho}{25}\leq \sum_{\rho\in D_H} \left(\frac{r_\rho +b_\rho}{10}\right)^2 \leq \sum_{\rho\in D_H} \left(\frac{r_\rho +b_\rho}{10}\right)^{10} \leq \sum_{\rho\in D_H} \binom{r_\rho +b_\rho}{10}\leq N_{K_{2,10}}(G_1)\leq n^{11}p^{18}\leq \frac{t}{50},\] where in the last inequality we used that \(n^{11}p^{18}\ll n^7p^{10}\leq t\) due to the fact that \(p\ll n^{-1/2}\). Hence \(\sum_{\rho\in D\setminus D_H}r_\rho b_\rho\geq t/2\) and, as each \(\rho\in D\setminus D_H\) has \(r_\rho b_\rho\leq 25\), we indeed obtain \(|D|\geq |D\setminus D_H|\geq t/50\). ◻

Proof of Proposition 27. Fix some \(G_1\) satisfying properties [item:bound32max32deg] and [item:K210-count] of Lemma 8 (which occur a.a.s.) and some colouring \(\varphi \colon E(G_1)\to \{\mathrm{red},\mathrm{blue}\}\) that contains at least \(t\) copies of \(C_{rbbbb}\). A copy \(K\) of \(K_{1,2}\) in \(G_1\) with vertices \(w,u_1,u_2\) (so that \(K\) is formed from edges \(wu_i\) for \(i=1,2\)) is dangerous if there are distinct vertices \(w_1,w_2\in V(G)\setminus \{w,u_1,u_2\}\) such that \(u_1u_2,u_1w_1,w_1w,ww_2,w_2u_2\in E(G_1)\), \(\varphi(u_1u_2)=\mathrm{red}\) and \(\varphi(u_1w_1)=\varphi(w_1w)=\varphi(ww_2)=\varphi(w_2u_2)=\mathrm{blue}\). We say that \(K\) hosts this copy of \(C_{rbbbb}\) on vertices \(u_1,u_2,w_2,w,w_1\). See Figure 6 for a depiction.

Moreover, for such a dangerous copy \(K\) of \(K_{1,2}\), we define \(x^K_1\) to be the number of choices of \(w_1\) such that \(\varphi(u_1w_1)=\varphi(w_1w)=\mathrm{blue}\) and \(x^K_2\) to be the number of choices of \(w_2\) such that \(\varphi(u_2w_2)=\varphi(w_2w)=\mathrm{blue}\). Therefore, each \(K\) hosts at most \(x_1^Kx_2^K\) copies of \(C_{rbbbb}\) (this is not equality as some choices could have \(w_1=w_2\)). Taking \(\mathcal{K}\) to be the collection of dangerous copies of \(K_{1,2}\) on \(V(G)\), we then have that \(\sum_{K\in \mathcal{K}}x^K_1x^K_2\geq t\). As in the proof of Proposition 26, our aim is to prove that \(\mathcal{K}\) is large. Define a copy \(K\) to be heavy if \(m^K \mathrel{\vcenter{:}}=\max\{x^K_1,x^K_2\} \ge 10\) and let \(\mathcal{K}_H\) be the collection of heavy dangerous copies of \(K_{1,2}\). We then have that \[\sum_{K\in \mathcal{K}_H}x_1^Kx_2^K\leq \sum_{K\in \mathcal{K}_H}(m^K)^2\leq \sum_{K\in \mathcal{K}_H}100\left(\frac{m^K}{10}\right)^{10}\leq 100\sum_{K\in \mathcal{K}_H}\binom{m^K}{10}.\] We claim that the sum in the right-hand side of the above inequality is at most \(N_{K_{2,10}^+}(G_1)\), where \(K^+_{2,10}\) is the graph obtained from \(K_{2,10}\) by adding a pendant edge to one of its vertices of degree 10. Indeed, fixing some \(K\) in the summand, label the vertices \(u_1, u_2\) and \(w\) as we did above and suppose that \(m^K\) is achieved by \(x_i^K\) for \(i\in[2]\) (if \(x_1^K=x^K_2\) then choose \(i\) arbitrarily). Then, for every set \(W_i\) of \(10\) vertices that can play the role of \(w_i\) in the sense that they are all connected to both \(u_i\) and \(w\) by blue edges in \(G_1\), we get a copy of \(K^+_{2,10}\) on the vertices \(w,u_1,u_2\) and \(W_i\). This gives \(\binom{m^K}{10}\) copies of \(K^+_{2,10}\) in the summand corresponding to \(K\); these copies are distinct, as each copy of \(K^+_{2,10}\) determines \(K\) completely. So we have that \[\sum_{K\in \mathcal{K}_H}x_1^Kx_2^K\leq 100N_{K^+_{2,10}}(G_1)\leq 100\cdot n^{11}p^{18}\cdot 4np \leq 400 n^{12}p^{19}\leq t/2,\] where we used properties [item:bound32max32deg] and [item:K210-count] of Lemma 8 to bound \(N_{K^+_{2,10}}(G_1)\) and we used that \(n^{12}p^{19}\ll n^7p^9\leq t\) in the last inequality. This implies that \(\sum_{K\in \mathcal{K}\setminus \mathcal{K}_H}x^K_1x^K_2\geq t/2\) and as every \(K\in \mathcal{K}\setminus \mathcal{K}_H\) has \(x^K_1x^K_2\leq 9^2\le 100\), we have that \(|\mathcal{K}|\geq |\mathcal{K}\setminus \mathcal{K}_H|\geq t/200\).

Now, taking \(G_2\sim G_{n,q}\), for each dangerous copy \(K\in \mathcal{K}\), let \(I_K \mathrel{\vcenter{:}}= \mathbb{1}[K\subseteq G_2]\) be the indicator random variable for the event that both edges of \(K\) appear in \(G_2\) and let \(X \mathrel{\vcenter{:}}= \sum_{K\in \mathcal{K}} I_K\). As each dangerous copy of \(K_{1,2}\) appears with probability \(q^2\), we have that \(\mu \mathrel{\vcenter{:}}= \mathbb{E}[X] \geq tq^2/200\gg 1\). Moreover, writing \(K \sim K'\) when a pair \(K, K'\) of dangerous copies of \(K_{1,2}\) share at least one edge, we have \[\Delta\mathrel{\vcenter{:}}=\sum_{K\sim K'}\mathbb{E}[I_KI_{K'}]\leq \mu \cdot \big(1 + 4\Delta(G_1)q\big) \leq 2\max\{ \mu, 8npq\mu\},\] using again the assumed conclusion of Lemma 8 [item:bound32max32deg] in \(G_1\). Indeed, given some copy \(K\) of \(K_{1,2}\), we can obtain an upper bound on the number of dangerous \(K'\) that intersect \(K\) (but are not equal to \(K\)) by the number of choices of an edge \(e\) of \(K\) and a \(G_1\)-neighbour of one of the endpoints of \(e\). Using that \[\frac{\mu^2}{npq\mu}\geq \frac{tq}{200np}\geq \frac{t^{1/2}}{200np}\geq \frac{n^{5/2}p^{7/2}}{200}\gg 1,\] it follows from Janson’s inequality (Lemma 6) that \[\Pr[X = 0] \le \exp\left(-\frac{\mu^2}{2\Delta}\right) \ll 1.\] Therefore, a.a.s.there is a dangerous copy of \(K_{1,2}\), on vertices \(w,u_1,u_2\) say, such that \(E(K)=\{wu_1,wu_2\}\subseteq E(G_2)\). This precludes the possibility of extending \(\varphi\) to \(G_2\). Indeed, as \(K\) is dangerous, it hosts some copy of \(C_{rbbbb}\) in \(G\) (under \(\varphi\)). If either \(wu_1\) or \(wu_2\) are coloured blue, then they will form a blue triangle with edges in the copy of \(C_{rbbbb}\) whilst if they are both red then there is a red triangle formed with the edge \(u_1u_2\). This completes the proof. ◻

Proof. For every ordered pair \(x, y\) of distinct vertices, let \(V_{x,y}\) denote the number of \(z\) such that \(\psi(xz) = \mathrm{red}\) and \(\psi(yz) = \mathrm{blue}\). Letting \(C\) be the number of copies of \(C_{rrbb}\), we have, by convexity, \[C = \sum_{x,y} \binom{V_{x,y}}{2} \ge n(n-1) \cdot \binom{\bar{V}}{2},\] where \[\bar{V} = \frac{1}{n(n-1)} \cdot \sum_{x,y} V_{x,y}.\] Observe that, if \(a,b,c,d\) are four distinct vertices such that \(\psi(ab) = \mathrm{red}\) and \(\psi(cd) = \mathrm{blue}\), then either \(ab\) and \(bc\) or \(bc\) and \(cd\) are counted by \(V_{a,c}\) or \(V_{b,d}\), respectively. This implies that, for all large \(n\), \[\bar{V} \ge \frac{1}{n(n-1)} \cdot \frac{\beta n^2 \cdot (\beta n^2 - 2n)}{2n} \ge \frac{\beta^2 n}{4},\] which gives the claimed lower bound on \(C\). ◻

Proof of Proposition 28. We can assume that \(0<\beta<1/4\). Let \(\mathcal{H}\) be the \(4\)-uniform hypergraph with vertex set \(E(K_n) \times \{\mathrm{red},\mathrm{blue}\}\) whose edges are all copies of \(C_{rrbb}\) in \(K_n\), that is, sets of the form \[\big\{(uv,\mathrm{red}), (uw,\mathrm{red}), (vx,\mathrm{blue}), (wx,\mathrm{blue})\big\},\] where \(u\), \(v\), \(w\), and \(x\) are any four distinct vertices of \(K_n\). Observe that \[v(\mathcal{H}) = 2\binom{n}{2}, \quad e(\mathcal{H}) = 12 \cdot \binom{n}{4}, \quad \Delta_2(\mathcal{H}) \le n, \quad \Delta_3(\mathcal{H}) = \Delta_4(\mathcal{H}) = 1.\]

Let \(\varepsilon\mathrel{\vcenter{:}}= \lambda_{\ref{lem:balanced-colouring}}(\beta/2)/2\) and let \(\delta>0\) and \(t\in \mathbb{N}\) be the constants provided by Theorem [thm:containers] invoked with \(k = 4\) and \(K = 1\). Set \[\gamma \mathrel{\vcenter{:}}= \min\left\{\varepsilon, \frac{\beta}{32}\right\}, \qquad \sigma \mathrel{\vcenter{:}}= \min\left\{\frac{\beta}{4t}, \frac{\gamma^2}{2^t}\right\} \qquad \text{and} \qquad \lambda \mathrel{\vcenter{:}}= \frac{\delta \sigma^4}{4}.\] Let \(\mathcal{I}(\mathcal{H})\) be the family of all sets \(I \subseteq V(\mathcal{H})\) that induce fewer than \(\lambda n^4p^4\) edges of \(\mathcal{H}\). Since \(p \gg n^{-2/3}\), we may apply Theorem [thm:containers] to \(\mathcal{H}\) with \(\tau \mathrel{\vcenter{:}}= \sigma p\) to obtain a function \(f \colon \mathcal{P}(V(\mathcal{H}))^t \to \mathcal{P}(V(\mathcal{H}))\) such that:

1. For every \(I \in \mathcal{I}(\mathcal{H})\), there are \(S_1, \dotsc, S_t \subseteq V(\mathcal{H})\) each of size at most \(\tau v(\mathcal{H})\) such that \(S_1 \cup \dotsb \cup S_t \subseteq I \subseteq f(S_1, \dotsc, S_t)\).

2. For each \(S_1, \dotsc, S_t \subseteq V(\mathcal{H})\), the set \(f(S_1, \dotsc, S_t)\) induces fewer than \(\varepsilon n^4\) edges in \(\mathcal{H}\).

Suppose that \(\varphi\) is a bad colouring of \(G\), that is, a colouring with \(|\varphi^{-1}(c)| \ge \beta n^2p\) for both \(c \in \{\mathrm{red}, \mathrm{blue}\}\) but fewer than \(\lambda n^4p^4\) copies of \(C_{rrbb}\). Then \(\varphi \in \mathcal{I}(\mathcal{H})\) and thus \(\varphi \subseteq f(S_1, \dotsc, S_t)\) for some \(S_1, \dotsc, S_t \subseteq \varphi\). We will call such \(\mathbf{S}\mathrel{\vcenter{:}}= (S_1, \dotsc, S_t)\) the signature of \(\varphi\) and denote it by \(\mathrm{sig}(\varphi)\). Denote by \(\pi \colon V(\mathcal{H}) \to E(K_n)\) the projection to the first coordinate and, with slight abuse of notation, let \(\pi(\mathbf{S}) \mathrel{\vcenter{:}}= \pi(S_1 \cup \dotsb \cup S_t)\); note that \(\pi(\mathrm{sig}(\varphi)) \subseteq G\).

Using Claim 30, we may conclude that \[\begin{align} \Pr\big[\text{G has a bad colouring}\big] & \le \sum_{\mathbf{S}} \Pr\big[\text{G has a bad colouring \varphi with \mathrm{sig}(\varphi) = \mathbf{S}}\big] \\ & \le \exp(-\gamma n^2p) \cdot \sum_{\mathbf{S}} \Pr\big[\pi(\mathbf{S}) \subseteq G\big]. \end{align}\] Finally, since there are at most \(2^{t|U|}\) sequences \(\mathbf{S}\mathrel{\vcenter{:}}= (S_1, \dotsc, S_t)\) satisfying \(\pi(\mathbf{S}) = U\), we have \[\sum_{\mathbf{S}} \Pr\big[\pi(\mathbf{S}) \subseteq G\big] \le \sum_{u \le t\tau v(\mathcal{H})} \binom{\binom{n}{2}}{u} \cdot 2^{tu} \cdot p^u \le \sum_{u \le t \sigma n^2p} \left(\frac{2^ten^2p}{u}\right)^u \le n^2 \left(\frac{2^te}{t\sigma}\right)^{t\sigma n^2p} \le e^{\gamma n^2p/2},\] for \(n\) sufficiently large, where the penultimate inequality follows from the fact that, for every \(a > 0\), the function \(u \mapsto (ea/u)^u\) is increasing when \(u \in (0,a]\) and the last inequality follows from the fact that \(t\sigma\log (2^te/t\sigma)\leq \gamma/4\) due to our choice of \(\sigma\). Hence we have that a.a.s.there are no bad colourings of \(G\), concluding the proof. ◻

Proof of Theorem 31. Let \(\beta, \zeta>0\) be the constants from the statement of Proposition 32. Further, let \(\lambda>0\) be the constant output by Proposition 28 with input \(\beta\) and let \(t_1\mathrel{\vcenter{:}}=\lambda n^4p^4\geq n^7p^{10}\) and \(t_2\mathrel{\vcenter{:}}=\zeta n^6p^7\geq n^7p^9\). Now fixing \(G_1\sim G_{n,p}\) and \(G_2\sim G_{n,q}\), we have that a.a.s.the conclusions of Propositions 26 with \(t_{\ref{prop:32many32Crrbb}}=t_1\), 27 with \(t_{\ref{prop:32many32Crbbbb}}=t_2\), 28 and 32 all hold. We claim that this implies the theorem. Indeed, consider some \(K_3\)-free colouring \(\varphi \colon E(G_1) \to \{\mathrm{red}, \mathrm{blue}\}\). Suppose first that \(\left| \varphi ^{-1}(c)\right| \ge \beta n^2p\) for both \(c\in \{\mathrm{red},\mathrm{blue}\}\). By the assumed conclusion of Proposition 28, there are at least \(t_1\) copies of \(C_{rrbb}\) induced by \(\varphi\). Since \(q\gg n^{-3}p^{-7/2}\gg t_1^{-1}\), the assumed conclusion of Proposition 26 gives that \(\varphi\) cannot be extended to \(G_2\) whilst avoiding monochromatic triangles. Likewise, if \(|\varphi^{-1}(\mathrm{red})|<\beta n^2p\), then Proposition 32 gives that there are at least \(t_2\) copies of \(C_{rbbbb}\) induced by \(\varphi\) and Proposition 27 then gives that we cannot extend \(\varphi\) to \(G_2\) without getting monochromatic triangles, using that \(q \gg t_2^{-1/2}\). Since both colours play symmetric roles, the same conclusion holds under the assumption \(|\varphi^{-1}(\mathrm{blue})| < \beta n^2p\). This covers all colourings and completes the proof. ◻

Proof. Suppose that \(T\) satisfies the assumptions of the lemma. We can assume that \(0<c<1/10\) and we fix some \(\varepsilon\in (0, c^2)\) and \(\beta \in (0, \varepsilon c/8)\). Consider the following iterative process of peeling off vertices:

We claim that the process terminates after fewer than \(n/2\) steps and thus outputs an appropriate \(S\). Suppose for a contradiction that this is not the case and that the process is still running after \(n/2\) steps. We will show that this contradicts our upper bound on \(e(T)\). Firstly, note that \[t_{n/4}\ge \frac{n}{4} \cdot \frac{cnp}{\log (n^2p)-\log(t_{n/2})} \ge \frac{n}{4} \cdot \frac{cnp}{\log (n^2p)} \ge \frac{cn^2p}{2^3\log n},\] using here that \(t_{n/2}\ge 1\) due to our assumption on \(T\). Now, define \(\tau_0\mathrel{\vcenter{:}}= 0\) and \[\tau_i\mathrel{\vcenter{:}}=\min\left\{\tau:t_{n/4-\tau}\ge 2^{i-3}\frac{cn^2p}{\log n}\right\}\] for \(i=1, 2,\ldots, k \mathrel{\vcenter{:}}= \log_2 (\varepsilon\log n)\).

Note that the claim implies that \[e(T)=t_0\ge t_{n/4-\tau_k}\ge 2^{k-3}\frac{cn^2p}{\log n}=\frac{\varepsilon cn^2p}{2^3}>\beta n^2p,\] contradicting our upper bound on \(e(T)\). It thus remains to prove the claim.

For this, note that, for each \(0\le i \le k-1\) and all \(\tau\in \mathbb{N}\) with \(\tau\le n/4-\tau_i\), we have that \[t_{n/4-\tau_i-\tau} - t_{n/4-\tau_i} \ge \tau \cdot \frac{cnp}{\log (n^2p)- \log(t_{n/4-\tau_i}) } \ge \tau \cdot \frac{cnp}{\log (2^{3-i}c^{-1}\log n) }.\] Consequently, for \(i \in \{0,\dotsc,k-1\}\), \[\tau_{i+1}-\tau_i\le 2^{i-2} \cdot \frac{cn^2p}{\log n} \cdot \frac{\log\left(2^{3-i}c^{-1}\log n\right)}{cnp}= \frac{2^i n \left(\log\big(2^{3}c^{-1}\log n\big)-i \log 2\right)}{4\log n}\] and so \[\begin{align} \tau_k&=\tau_0+\sum_{i=0}^{k-1}(\tau_{i+1}-\tau_i) \\ &\le \frac{n}{4\log n}\left(\sum_{i=0}^{k-1} 2^{i} \log \big(2^{3}c^{-1}\log n\big) - \log 2 \cdot \sum_{i=0}^{k-1} i2^{i}\right)\\ &\le \frac{n}{4\log n}\left(2^{k} \log \big(2^3c^{-1}\log n\big)-\log 2 \cdot (k-2)2^k\right) \\ & = \frac{2^kn}{4 \log n} \log (2^{5-k}c^{-1}\log n) \\ &\le \frac{\varepsilon n}{4} \log \left(2^5c^{-1}\varepsilon^{-1} \right) \leq \frac{n}{4}, \end{align}\] as required, where we used our upper bounds on \(\varepsilon\) and \(c\) in the final inequality. ◻

Proof of Proposition 32. Let \(\theta\) be the constant from the statement of Lemma 8 [item:many32K3], let \(\zeta = \theta/2^{10}\), let \(c = 2^{-17}\) and let \(\beta \mathrel{\vcenter{:}}= \beta_{\ref{lem:5-cycle-preprocessing}}(c)\) be the constant from the statement of Lemma 33. Define \(\mathcal{S}\) to be the set of graphs \(S\) such that \(\theta n^3p^3/8\le e(S)< \beta n^2p\) and \(\Delta(S)\le\frac{cnp}{\log (n^2p)-\log(e(S))}\). Given an \(S\in \mathcal{S}\), let \(B(S)\) be the event that for \(G \sim G_{n,p}\), the graph \(G\cup S\) contains fewer than \(\zeta n^6p^7\) copies of \(C_5\) whose vertices all lie in \(V(S)\) and that have one edge in \(S\) and four edges of \(G \setminus S\). The following key claim bounds the probability of \(B(S)\) for all \(S\in \mathcal{S}\).

Before proving this claim, let us see how it implies the proposition. Firstly, let \(\mathcal{F}\) be the family of all graphs \(T\) on \(V(G)\) that satisfy the following:

1. \(e(T) < \beta n^2p\);

2. for every \(U\subseteq V(G)\) with \(|U|\ge \frac{n}{2}\), we have that \(e(T[U])\geq \theta|U|^3p^3\).

Now, if \(G\) satisfies property [item:many32K3] of Lemma 8, then every \(K_3\)-free colouring \(\varphi \colon E(G) \to \{\mathrm{red}, \mathrm{blue}\}\) that colours fewer than \(\beta n^2 p\) edges red satisfies \(\varphi^{-1}(\mathrm{red}) \in \mathcal{F}\). Indeed, [item:many32K3] gives a collection of at least \(\theta|U|^3p^3\) edge-disjoint triangles in each \(U\subseteq V(G)\) with \(|U|\geq \frac{n}{2}\) and at least one edge in each triangle must be coloured red. Further, Lemma 33 implies that, for every \(T\in \mathcal{F}\), there is some \(S=S(T)\in \mathcal{S}\) such that \(S=T[W]\) for some \(W \subseteq V(G)\) with \(|W| \ge n/2\); indeed, the fact that \(T\in \mathcal{F}\) gives that \(e(S)\geq \theta n^3p^3/8\). This implies that, if there is a \(K_3\)-free \(\varphi \colon E(G) \to \{\mathrm{red}, \mathrm{blue}\}\) with \(|\varphi^{-1}(\mathrm{red})| < \beta n^2p\) and fewer than \(\zeta n^6p^7\) copies of \(C_{rbbbb}\) (and \(G\) satisfies property [item:many32K3] of Lemma 8), then there is some \(S\in \mathcal{S}\) such that \(B(S)\) occurs and \(S\subseteq G\). Indeed, \(T \mathrel{\vcenter{:}}= \varphi^{-1}(\mathrm{red}) \in \mathcal{F}\) and \(B(S(T))\) occurs as otherwise we get at least \(\zeta n^6p^7\) copies of \(C_5\) on \(V(S)\) each of which has exactly one edge in \(S\) and the other 4 edges in \(G\setminus S\) and hence gives a copy of \(C_{rbbbb}\) in \(G\). Finally, note that, for each \(S\in \mathcal{S}\), the events \(B(S)\) and \(S\subseteq G\) are independent. Therefore, the probability that \(G\) has a colouring \(\varphi \colon E(G) \to \{\mathrm{red}, \mathrm{blue}\}\) with \(|\varphi^{-1}(\mathrm{red})| < \beta n^2p\) and fewer than \(\zeta n^6p^7\) copies of \(C_{rbbbb}\) is less than \[\sum_{S \in \mathcal{S}} \Pr[B(S) \wedge S \subseteq G] + \Pr[G\notin~\ref{item:many32K3}] \le \sum_{S \in \mathcal{S}} \Pr[B(S)]\cdot\Pr[S \subseteq G] + \Pr[G\notin~\ref{item:many32K3}].\]

By Lemma 8, we have that \(\Pr[G\notin\ref{item:many32K3}]\ll 1\). We split the sum over \(S \in \mathcal{S}\) depending on \(e(S)=s\). As there are at most \(2^n \binom{\binom{n}{2}}{s}\) graphs \(S \in \mathcal{S}\) with \(s\) edges (the factor of \(2^n\) bounds the number of choices for \(V(S)\)), appealing to Claim 35, we therefore have that \[\begin{align} \sum_{S \in \mathcal{S}} \Pr[B(S)]\cdot\Pr[S \subseteq G] & \le \sum_{ s} 2^n \binom{\binom{n}{2}}{s} \cdot \left(\frac{s}{n^2p} \right)^{2s} \cdot p^s \\ & \le \sum_{s} 2^n \cdot \left(\frac{en^2}{2s} \cdot \left(\frac{s}{n^2p}\right)^2 \cdot p\right)^s \\ & \le \sum_{s} 2^n \cdot \left(\frac{es}{n^2p}\right)^s \ll 1, \end{align}\] where the sum goes over all \(s \in (\theta n^3p^3/8, \beta n^2p)\) and, in the last inequality, we used \[s\log\left(\frac{n^2p}{s}\right)\ge s\ge \theta n^3p^3/8 \gg n.\] Therefore, it remains only to establish Claim 35.

The proof of Proposition 32 is now complete. ◻

Proof of Theorem 36. Let \(\beta, \zeta > 0\) be the constants from the statement of Proposition 37. Further, let \(\lambda>0\) be the constant output by Proposition 28 with input \(\beta\), let \(t\mathrel{\vcenter{:}}= \zeta n^6p^8\) and note that \(t \leq \lambda n^4p^4\). Now, with \(G_1\sim G_{n,p}\) and \(G_2\sim G_{n,q}\), we have that a.a.s.the conclusions of Propositions 26, 28 and 32 all hold. In particular, a.a.s.any \(K_3\)-free colouring \(\varphi \colon E(G_1) \to \{\mathrm{red}, \mathrm{blue}\}\) gives rise to at least \(t\) copies of \(C_{rrbb}\). Indeed, this follows from Proposition 28 if \(\left| \varphi ^{-1}(c)\right| \ge \beta n^2p\) for both \(c\in \{\mathrm{red},\mathrm{blue}\}\), or from Proposition 37 if \(|\varphi^{-1}(c)|<\beta n^2p\) for some \(c\in \{\mathrm{red},\mathrm{blue}\}\). The conclusion of the theorem then follows from Proposition 26 as \(q\gg t^{-1}\). ◻

Proof. By convexity, we have that \[X_2(S) = \sum _{v\in V} \binom{d_{S}(v)}{2} \ge n \cdot \binom{\sum_{v \in V} d_{S}(v)/n}{2} = n \cdot \binom{2e(S)/n}{2} \ge \frac{3e(S)^2}{2n},\] where the last inequality holds due to our assumption that \(e(S) \ge 2n\). ◻

Proof. For each pair of vertices \(\rho\in \binom{[n]}{2}=E(K_n)\), let \(d_\rho\) be the number of copies of \(K_{1,2}\) in \(S\) that form a triangle with \(\rho\) and call \(\rho\) heavy if \(d_\rho\geq 10\). Then \(\Pi=\Pi(S)\subseteq E(K_n)\) are the pairs \(\rho\in E(K_n)\) such that \(d_\rho\geq 1\) and let \(\Pi_H\subseteq \Pi\) be the heavy pairs. Then we have that \[\label{eq:heavy32uppper32sum} \sum_{\rho \in \Pi_H} \frac{d_\rho}{10} \leq \sum_{\rho\in \Pi_H}\left(\frac{d_\rho}{10}\right)^{10} \leq \sum_{\rho\in \Pi_H}\binom{d_\rho}{10}=N_{K_{2,10}}(S) \leq n^{11}p^{18}\ll n^5p^6,\tag{7}\] using that property [item:K210-count] of Lemma 8 holds in \(S\) in the penultimate inequality and the fact that \(p\ll n^{-1/2}\) in the final inequality. On the other hand, \[\label{eq:X232lower32sum} \sum_{\rho \in \Pi}d_\rho= X_{2}(S)\geq \frac{3s^2}{2n}\geq \frac{\theta^2 n^5p^6}{4},\tag{8}\] by appealing to Lemma 40 and our lower bound on \(s=e(S)\). Combining 7 and 8 then gives that \(\sum_{\rho \in \Pi\setminus \Pi_H}d_\rho\geq 5X_2(S)/6\) and so \[|\Pi(S)|\geq |\Pi\setminus \Pi_H|\geq \frac{1}{10}\sum_{\rho\in \Pi\setminus \Pi_H}d_\rho\geq \frac{X_2(S)}{12}\geq \frac{s^2}{8n},\] using Lemma 40, which completes the proof. ◻

Proof. Fix some \(T \in \mathcal{F}\) and denote \(t \mathrel{\vcenter{:}}= e(T)\). Now for any subgraph \(S\subseteq T\), we define \[\begin{align} \Delta_1(\mathcal{X}_S)&\mathrel{\vcenter{:}}=|\{K,K'\in\mathcal{X}_S: K\cup K' \text{ is a path with } 3 \text{ edges }\}|\cdot p^3 \text{ and } \\ \Delta_2(\mathcal{X}_S)&\mathrel{\vcenter{:}}=|\{K,K'\in\mathcal{X}_S: K\cup K' \text{ is a copy of } K_{1,3}\}|\cdot p^3, \end{align}\] and we note that, for every \(S\), we have \(\Delta(\mathcal{X}_S)=\Delta_1(\mathcal{X}_S)+\Delta_2(\mathcal{X}_S)+\mu(\mathcal{X}_S)\). Indeed, the sum in the definition of \(\Delta(\mathcal{X}_S)\) ranges over all pairs \(K,K'\in \mathcal{X}_S\) that intersect in at least one edge. If they intersect in two edges, then \(K=K'\) and the contribution to \(\Delta(\mathcal{X}_S)\) is counted by \(\mu(\mathcal{X}_S)\) and if they intersect in precisely one edge, then their union is either a path, in which case they are counted by \(\Delta_1(\mathcal{X}_S)\), or a star in which case they are counted by \(\Delta_2(\mathcal{X}_S)\). The following claim is the key step in proving the lemma.

With Claim 43, the lemma follows quickly. Indeed, fix \(S\subseteq T\) as output by the claim and note that \[\label{eq:mu32split32min} \frac{\mu(\mathcal{X}_S)^2}{\Delta(\mathcal{X}_S)}=\frac{\mu(\mathcal{X}_S)^2}{\Delta_1(\mathcal{X}_S)+\Delta_2(\mathcal{X}_S)+\mu(\mathcal{X}_S)} \geq \frac{1}{3} \min\left\{\frac{\mu(\mathcal{X}_{S})^2}{\Delta_1(\mathcal{X}_S)}, \frac{\mu(\mathcal{X}_{S})^2}{\Delta_2(\mathcal{X}_S)}, \mu(\mathcal{X}_S)\right\}.\tag{10}\] Firstly, suppose that the minimum is achieved by the last term. In this case we have that \(\frac{\mu(\mathcal{X}_S)^2}{\Delta(\mathcal{X}_S)}\geq \frac{\mu(\mathcal{X}_S)}{3}\) and the conclusion of the lemma is satisfied, with \(S\) satisfying [type:a] if \(\frac{\mu(\mathcal{X}_S)}{3} \geq 10t\log \left( \frac{2n^2p}{t} \right)\) and [type:b] otherwise. Likewise, if the minimum is achieved by the middle term, then by Claim 43 we have that \(\frac{\mu(\mathcal{X}_S)^2}{\Delta(\mathcal{X}_S)}\) satisfies [type:a]. It remains to consider the case where the minimum is achieved by the first term. For this, note that we have \(\Delta_1(\mathcal{X}_S)\leq 4 |\Pi(S)|^2p^3\). Indeed, it \(v_1v_2v_3v_4\) is a path of length three in \(S\) labeled so that \(K\) is the path \(v_1v_2v_3\) and \(K'\) is the path \(v_2v_3v_4\), see Figure 8, then \(v_1v_3, v_2v_4\in \Pi(S)\) and thus we can count the number of pairs \(K,K'\) whose union is a path with three edges by the number of pairs in \(\Pi(S)\) with a labelling of the endpoints of each pair. Using 9 , we therefore have that \[\frac{\mu(\mathcal{X}_{S})^2}{\Delta_1(\mathcal{X}_S)}\geq \frac{|\Pi(S)|^2 n^2p^4 }{5 |\Pi(S)|^2p^3}\geq \frac{n^2p}{5}= t \log \left( \frac{2n^2p}{t} \right) \cdot \frac{n^2p}{5t}\cdot \log ^{-1} \left( \frac{2n^2p}{t}\right) \ge 30t \log \left( \frac{2n^2p}{t} \right),\] using here that \(t<\beta n^2p\) (property [cond:Ta] of Definition 38) and the fact that \(\beta<2^{-100}\). Therefore, we also satisfy part [type:a] of the lemma when the minimum in 10 is achieved by the first term.

It remains to prove Claim 43, which we do now.

Proof of Claim 43. In order to derive the lower bound in Claim 43, we need to upper bound \(\Delta_2(\mathcal{X}_S)\) and hence we need an upper bound on the count of pairs \(K,K'\in \mathcal{X}_S\) such that \(K\cup K'\) forms a copy of \(K_{1,3}\). Given such a pair \(K\) and \(K'\), denote the vertex of degree three in \(K\cup K'\) by \(u\) and the remaining vertices by \(w_1,w_2,w_3\) so that \(K\) lies on vertices \(u,w_1,w_2\), \(K'\) lies on vertices \(u,w_2,w_3\) and thus \(w_1w_2, w_2w_3 \in \Pi(S)\), see Figure 9. Hence, we have that \[\label{eq:Delta32232Xs} \Delta_2(\mathcal{X}_S)\leq X_2(\Pi(S))np^3,\tag{11}\] where \(X_2(\Pi(S))\) is the number of copies of \(K_{1,2}\) in \(\Pi(S)\) when considered as a graph on \(n\) vertices. Indeed, the number of possible pairs \(K,K'\) with \(K\cup K'\) a copy of \(K_{1,3}\) can be bounded by choosing a copy of \(K_{1,2}\) in \(\Pi(S)\) and a choice of vertex \(u\) (at most \(n\) choices). We proceed by splitting our analysis into cases, depending on whether or not \(T\) contains a large subgraph with maximum degree at most \(d \mathrel{\vcenter{:}}=\sqrt{\frac{tp}{2000\log \left( 2n^2p/t \right)}}\).

Case 1. \(T\) contains a subgraph with at least \(t/2\) edges and maximum degree at most \(d\).

We let \(S\) be one such subgraph. Note that \(X_{2}(\Pi(S))\le |\Pi(S)|\Delta(\Pi(S))\) where \(\Delta(\Pi(S))\) is the maximum degree of a vertex in \(\Pi(S)\) when considered as a graph on \(n\) vertices. Since \(\Delta(\Pi(S))\le \Delta(S)^2\leq d^2\), appealing to 9 and 11 , we have that \[\begin{align} \frac{\mu(\mathcal{X}_S)^2}{\Delta_2(\mathcal{X}_S)} & \ge \frac{|\Pi(S)|^2 n^2p^4}{2|\Pi(S)|d^2np^3} \ge \frac{1000|\Pi(S)|n \log(2n^2p/t)}{t} \geq 30 t \log\left(\frac{2n^2p}{t}\right) , \end{align}\] as claimed, where we used Lemma 41, noting that the conditions are satisfied as \(S\subseteq T\in \mathcal{F}\) and \(e(S)\geq t/2\).

Case 2. Every subgraph of \(T\) with maximum degree at most \(d\) has fewer than \(t/2\) edges. In this case, we define \(S = T\) as the subgraph with the desired properties. First, we claim that \[\label{eq:X2T-strong-LB} |\Pi(T)| \ge \frac{td}{24}.\tag{12}\] Indeed, let \(H\subseteq T\) be a maximal subgraph with respect to inclusion such that \(\Delta (H) \le d\). By our assumption, \(e(H) < t/2\). By the definition of \(H\), for any \(e \in E(T)\setminus E(H)\), one of its endpoints has degree at least \(d+1\) when added to \(H\) and hence \(e\) is contained in at least \(d\) copies of \(K_{1,2}\) with edges in \(H\). Summing over all edges in \(E(T)\setminus E(H)\) gives that \(X_2(T)\geq td/2\) and 12 follows from Lemma 41. We will also show that \[\label{eq:X4T-upper} X_2(\Pi(T)) \le 20 |\Pi(T)| tp.\tag{13}\] We claim that this suffices to prove Claim 43. Indeed, appealing to 9 , 11 and 12 , we get that \[\begin{align} \frac{\mu(\mathcal{X}_T)^2}{\Delta_2(\mathcal{X}_T)} &{\ge} \frac{|\Pi(T)|^2 n^2p^4 }{40|\Pi(T)| tp \cdot np^3} {\ge} \frac{|\Pi(T)| n}{40t} {\ge} \frac{dn}{1000} = \frac{1}{1000}\cdot \sqrt{\frac{tp}{2000\log \left( 2n^2p/t\right)}} \cdot n \\ & \ge 30t \log \left( \frac{2n^2p}{t} \right) \cdot \sqrt{\frac{n^2p}{2^{50}t}\cdot \log ^{-3} \left( \frac{2n^2p}{t}\right)} \ge 30t \log \left( \frac{2n^2p}{t} \right) , \end{align}\] as desired, using that \(t<\beta n^2p\) and the fact that \(\beta \le 2^{-100}\) in the last inequality here.

To show that 13 holds, note first that \(X_2(\Pi(T))\) is at most the number of paths \(w_1wzw_2\) in \(K_n\) such that \(w_1w \in \Pi(T)\) and \(wz, zw_2 \in T\), see Figure 10. Consequently, denoting by \(d_{\Pi}(v)\) the number of neighbours of \(v\) in \(\Pi(T)\), we have \[\label{eq:X2upper1} X_2(\Pi(T))\leq \sum_{e=wz\in T} d_\Pi(w) d_T(z)=\sum_{w\in [n]}\sum_{z\in [n]} d_\Pi(w) d_T(z) \mathbb{1}[wz\in T].\tag{14}\]

We will split this sum further by grouping together vertices depending on their degrees. To this end, for \(0 \le \alpha \le \log_2(np)\) and \(0\le \beta \le 2\log _2(np)+1\) let \[A_\alpha \mathrel{\vcenter{:}}= \left\{ z\in V(T) : \frac{d_T(z)}{2np} \in \left[ 2^{-\alpha-1},2^{-\alpha} \right] \right\} , \qquad B_\beta \mathrel{\vcenter{:}}= \left\{ w\in V(T) : \frac{d_{\Pi}(w)}{4n^2p^2} \in \left[ 2^{-\beta-1},2^{-\beta} \right] \right\},\] and note that the sets \(A_\alpha\) partition the vertices with non-zero degree in \(T\) and similarly the sets \(B_\beta\) partition the vertices with non-zero degree in \(\Pi\), using here that \(d_\Pi(w)\leq \Delta(\Pi(S))\leq \Delta(T)^2\leq 4n^2p^2\) for all \(w\in V(T)\) due to the fact that \(T\in \mathcal{F}(\beta,p)\) and so \(\Delta(T)\leq 2np\) (see Definition 38). Hence, returning to the upper bound 14 , we have that \[\label{eq:X2upper2} X_2(\Pi(T)) \le \sum_{\alpha=0}^{\log _2(np)} \sum_{\beta=0}^{2\log _2(np)+1} e_T(A_\alpha,B_\beta) \cdot 8n^3p^3 2^{-\alpha-\beta}.\tag{15}\] We now turn to bounding \(e_T(A_\alpha,B_\beta)\) for each \(0 \le \alpha \le \log_2(np)\) and \(0\le \beta \le 2\log _2(np)+1\). For each such \(\alpha\) and \(\beta\), set \[a_\alpha \mathrel{\vcenter{:}}= \frac{2^{\alpha+1} t}{np}, \qquad b_\beta \mathrel{\vcenter{:}}= \frac{2^{\beta} |\Pi(T)|}{n^2p^2},\] and note that \(|A_\alpha|\le a_\alpha\) and \(|B_\beta|\le b_\beta\). Indeed, \(2^{-\alpha}np|A_\alpha|\leq \sum_{z\in V}d_T(z)\leq 2t,\) and similarly for \(|B_\beta|\). Moreover \[a_\alpha = \frac{2^{\alpha+1} t}{np} \ge \frac{t}{np} \ge \theta n^2p^2 \gg \frac{(\log n)^7}{p},\] using that \(t\geq \theta n^3p^3\) as \(T\in \mathcal{F}\) (see Definition 38) and the fact that \(p\geq n^{-3/5}\). Similarly, we have that \[b_\beta= \frac{2^\beta |\Pi(T)|}{n^2p^2} \ge \frac{td}{24n^2p^2} \geq \frac{t^{3/2}p^{1/2}}{1200n^2p^2\log(2n^2p/t)}\geq \frac{\theta^{3/2} n^{5/2}p^{3}}{1200\log(2n^2p/t)} \gg \frac{(\log n)^7}{p},\] where we used 12 to lower bound \(|\Pi(T)|\) as well as our lower bounds on \(t\) and \(p\). Now as \(T\in \mathcal{F}(\beta;p)\) has property [item:eAB-concentration] of Lemma 8, see Definition 38, \[e_T(A_\alpha, B_\beta) \le |A_\alpha|\cdot |B_\beta| \cdot p + \frac{a_\alpha \cdot b_\beta \cdot p}{\log ^3 n} \le |A_\alpha|\cdot |B_\beta| \cdot p + \frac{2^{\alpha+\beta+1} t |\Pi(T)|}{n^3p^2\log ^3 n},\] for all \(\alpha, \beta\) in our ranges of interest. Therefore, plugging these upper bounds into 15 , we get \[\begin{align} X_2(\Pi(T)) & \le \sum_{\alpha=0}^{\log _2(np)} \sum_{\beta=0}^{2\log _2(np)+1} \left( |A_\alpha|\cdot |B_\beta| \cdot p + \frac{2^{\alpha+\beta+1} t |\Pi(T)|}{n^3p^2\log ^3 n} \right) \cdot 8n^3p^3 2^{-\alpha-\beta} \\ & \le \frac{16|\Pi(T)|\cdot tp}{\log n} + 8p \cdot \left( \sum _{\alpha=0}^{\log _2(np)} |A_\alpha|\cdot 2^{-\alpha}np \right) \cdot \left( \sum _{\beta=0}^{2\log _2(np)+1} |B_\beta| \cdot 2^{-\beta} n^2 p^2 \right) \\ \\ & \le |\Pi(T)|\cdot tp + 8p\cdot \left(\sum_{z\in [n]}d_T(z)\right) \cdot \left(\sum_{w\in [n]}d_\Pi(w)/2 \right)\\ & \le |\Pi(T)|\cdot tp + 8p\cdot 2t \cdot |\Pi(T)| \le 20|\Pi(T)| tp, \end{align}\] establishing 13 and completing the proof of this case, the claim and the lemma. ◻

 ◻

Proof. Suppose that \(T\in \mathcal{F}(\beta;p)\) is of type [type:b], let \(S \mathrel{\vcenter{:}}= S(T)\subseteq T\) be the graph output by Lemma 42 when applied to \(T\) and let \(s \mathrel{\vcenter{:}}= e(S)\geq t/2\). If [item:p-small] did not hold, then 9 , Lemma 41 and the fact that \(t\geq \theta n^3p^3\) (see Definition 38) would imply that, if \(C = C(\theta)\) is sufficiently large, \[\frac{\mu(\mathcal{X}_S)}{3}\geq \frac{|\Pi(S)|np^2}{4} \geq \frac{s^2p^2}{32} \geq \frac{t^2p^2}{128} \geq \frac{\theta tn^3p^5}{128} \ge \frac{C^5\theta t \log n}{128} \ge 10t\log\left(\frac{2n^2p}{t}\right),\] contradicting the fact that \(S\) satisfies part [type:b] of Lemma 42. Similarly, if [item:eT-small] did not hold, then, for some positive constant \(c\), we would have, using that \(p\gg n^{-3/5}\), \[\frac{\mu(\mathcal{X}_S)}{3} \geq \frac{t^2p^2}{128}\geq \frac{ctn^3p^5\log n}{128}\gg t \log n,\] again contradicting the fact that \(S\) satisfies part [type:b] of Lemma 42. This means that both [item:p-small] and [item:eT-small] must hold. Finally, the third assertion [item:lower32log32bd] follows from the other two. Indeed, we have that \(p\ll n^{-7/12}(\log n)^{-1/2}\) from part [item:p-small] and so using [item:eT-small], we get that \[\frac{2n^2p}{t}\geq \frac{2}{np^2\log n}\gg n^{1/6}.\qedhere\] ◻

Proof of Proposition 37. Let \(\alpha = 1/6400\), \(\beta \mathrel{\vcenter{:}}= 2^{-100}\) and let \(\zeta \mathrel{\vcenter{:}}= \min\{\alpha \theta^2 / 96, \alpha \theta / (18C^5)\}\), where \(C = C(\theta)\) is the constant from the statement of Lemma 44. Let \(G\sim G_{n,p}\), let \(\mathcal{F}\mathrel{\vcenter{:}}= \mathcal{F}(\beta;p)\) be the collection of graphs from Definition 38 and let \(\mathcal{H}\) be the collection of \(n\)-vertex graphs that satisfy properties [item:bound32max32deg]–[item:eAB-concentration] of Lemma 8. Further, let \(\mathcal{F}_{\ref{type:a}}, \mathcal{F}_{\ref{type:b}}\subseteq \mathcal{F}\) be the graphs of types [type:a] and [type:b], respectively. Now, for a graph \(R \subseteq K_n\), let \(A(R)\) be the event that \(R = \varphi^{-1}(\mathrm{red})\) for some \(K_3\)-free colouring \(\varphi \colon E(G) \to \{\mathrm{red}, \mathrm{blue}\}\) of \(G\) with fewer than \(\zeta n^6p^8\) copies of \(C_{rrbb}\). As \(\Pr[G\notin \mathcal{H}]\ll 1\), due to Lemma 8, it suffices to show that a.a.s.the event \(\bigcup\{A(R) : e(R) < \beta n^2p\} \cap \{G\in \mathcal{H}\}\) does not occur. To this end, we first claim that for any \(R\subseteq K_n\) with \(e(R)<\beta n^2p\), the event \(A(R) \cap \{G\in \mathcal{H}\}\) is empty unless \(R \in \mathcal{F}\). To see this, suppose that \(G\in \mathcal{H}\) and the event \(A(R)\) happens for some \(R\) with \(e(R)<\beta n^2 p\). As properties [item:bound32max32deg]–[item:K210-count] and [item:eAB-concentration] of Lemma 8 are all monotone decreasing, the graph \(R \subseteq G \in \mathcal{H}\) must satisfy condition [cond:Tb] of Definition 38. Moreover, the upper bound on \(e(R)\) in condition [cond:Ta] of Definition 38 is satisfied by assumption. As for the lower bound, property [item:many32K3] of Lemma 8 supplies a collection of at least \(\theta n^3p^3\) edge-disjoint triangles in \(G\) and each colours class of every \(K_3\)-free colouring of \(G\) must contain at least one edge from each triangle in this collection. Therefore, it remains to show that a.a.s.no event \(A(T)\cap \{G\in \mathcal{H}\}\) occurs with \(T\in \mathcal{F}=\mathcal{F}_{\ref{type:a}}\cup \mathcal{F}_{\ref{type:b}}\). We first deal with the type [type:a] graphs \(T\).

Using Claim 45 and appealing to a union bound, we thus have that \[\begin{align} \Pr\big[ A(T) \cap \{G\in \mathcal{H}\} \text{ for some T\in \mathcal{F}_{\ref{type:a}}} \big] & \le \sum _{T \in \mathcal{F}_{\ref{type:a}}} \Pr\big[ A(T) \big] \le \sum _{T \in \mathcal{F}_{\ref{type:a}}} p^{e(T)} \cdot \left( \frac{e(T)}{2n^2p} \right) ^{e(T)} \\ & \le \sum^{\beta n^2p}_{t = \theta n^3p^3} \binom{\binom{n}{2}}{t} \cdot p^t \cdot \left( \frac{t}{2n^2p} \right) ^t \leq \beta n^2p\left( \frac{e}{4} \right) ^{n} \ll 1. \end{align}\]

It remains to consider the events \(A(T) \cap \{G\in \mathcal{H}\}\) for type [type:b] graphs \(T\in \mathcal{F}_{\ref{type:b}}\). More precisely, we need to show that a.a.s.\(G\) does not belong to the family \(\mathcal{H}'\) defined by \[\mathcal{H}'\mathrel{\vcenter{:}}=\left\{H\in \mathcal{H}: \exists \varphi\colon E(H)\rightarrow\{\mathrm{red},\mathrm{blue}\} \text{ with } \varphi^{-1}(\mathrm{red})\in \mathcal{F}_{\ref{type:b}} \text{ and fewer than } \zeta n^6p^8 \text{ copies of } C_{rrbb}\right\}.\] In order to do this, for each \(H\in \mathcal{H}'\), we will identify some \(\ell=\ell(H)\in \mathbb{N}\) and a pair of increasing sequences \({\boldsymbol{J}}(H)=(J_0,J_1,\ldots, J_\ell)\) and \({\boldsymbol{R}}(H)=(R_0,R_1,\ldots,R_\ell)\) of subgraphs of \(H\); we will refer to this pair as the stamp of \(H\) and denote it by \({\boldsymbol{S}}(H)=({\boldsymbol{J}}(H), {\boldsymbol{R}}(H))\). Our proof will then provide an upper bound on the probability that \({\boldsymbol{S}}(G)=\boldsymbol{S}\), for any given stamp \(\boldsymbol{S}\), that is strong enough to survive a union bound over all possible stamps \({\boldsymbol{S}}\). Before proceeding, we remark that, by Lemma 44, we can assume that \(p \le Cn^{-3/5} \log ^{1/5}n\), as otherwise \(\mathcal{F}_{\ref{type:b}}=\emptyset\) and so \(\mathcal{H}'=\emptyset\).

Now, for each \(H\in \mathcal{H}'\), we define \(\ell(H)\) and construct the sequences \({\boldsymbol{J}}={\boldsymbol{J}}(H)\) and \({\boldsymbol{R}}={\boldsymbol{R}}(H)\) (and hence the stamp \({\boldsymbol{S}}(H)\)) by considering the following process:

1. Fix some \(K_3\)-free colouring \(\varphi\colon E(H)\rightarrow\{\mathrm{red},\mathrm{blue}\}\) with fewer than \(\zeta n^6p^8\) copies of \(C_{rrbb}\) and \(T\mathrel{\vcenter{:}}=\varphi^{-1}(\mathrm{red})\in \mathcal{F}_{\ref{type:b}}\).

2. Choose a collection \(\mathcal{C}\) of \(c_0\mathrel{\vcenter{:}}= \theta n^3p^3\) edge-disjoint triangles in \(H\) (this is possible as \(H\in \mathcal{H}\) and so it satisfies property [item:many32K3] of Lemma 8), fix \(J_0\) to be the collection of edges featuring in \(\mathcal{C}\) and \(R_0 \mathrel{\vcenter{:}}= J_0\cap T\) to be the collection of edges in \(J_0\) which are coloured red by \(\varphi\).

At this point note that, for any \(n\)-vertex graph \(R\) with \(R_0 \subseteq R\subseteq T\), we have that \(R\in \mathcal{F}\). Indeed, \(|R|\geq |R_0|\geq c_0= \theta n^3p^3\), as there is at least one red edge in each triangle in \(\mathcal{C}\), and the other conditions of Definition 38 follow from the fact that \(R\subseteq T\in \mathcal{F}_{\ref{type:b}}\subseteq \mathcal{F}\). We now continue to form our sequences. We will maintain that \(J_{i-1}\subseteq J_i\) for all \(i\geq 1\) and define \(R_i \mathrel{\vcenter{:}}= J_i\cap T\) to be the collection of edges in \(J_i\) that are coloured red by \(\varphi\) (as is the case with \(R_0\subseteq J_0\)).

3. Suppose that \(i \ge 0\) and that \(J_i\) and \(R_i\) have already been defined. As \(R_0\subseteq R_i\subseteq T\), we have that \(R_i\in \mathcal{F}\). In particular, Lemma 42 gives us \(S_i \mathrel{\vcenter{:}}= S(R_i)\) such that \(e(S_i)\geq e(R_i)/2\). Now fix \[\label{eq:Midef} M_i\mathrel{\vcenter{:}}=\alpha \min\left\{ |\Pi(S_i)|np^2,e(R_i)\log\left(\frac{2n^2p}{e(R_i)} \right) \right\},\tag{16}\] recalling the definition of \(\Pi(S_i)\) from Definition 39. Let \(\mathcal{X}(H,J_i,S_i)\subseteq \mathcal{X}_{S_i}\) be the set of copies of \(K_{1,2}\) in \(H\setminus J_i\) that avoid the edges of \(J_i\) and form a \(4\)-cycle with some copy of \(K_{1,2}\) in \(S_i\). Moreover, let \(\mathcal{Z}\) be a largest collection of edge-disjoint copies of \(K_{1,2}\) in \(\mathcal{X}(H,J_i,S_i)\). If \(|\mathcal{Z}|< M_i\) then terminate the process and fix \(\ell(H)\mathrel{\vcenter{:}}= i\). Otherwise, if \(|\mathcal{Z}|\geq M_i\), then choose some \(\mathcal{Z}'\subseteq \mathcal{Z}\) with \(|\mathcal{Z}'|=M_i\), let \(J_{i+1}\) be the graph obtained by adding the edges in copies of \(K_{1,2}\) in \(\mathcal{Z}'\) to \(J_i\) and let \(R_{i+1}=J_{i+1}\cap T\). Repeat step [step:32third] with \(i+1\) replacing \(i\).

We begin by collecting some observations about the process with the following claims.

Since \(n^6p^8 \gg n^3p^3\), by our assumption that \(p \gg n^{-3/5}\), Claim 46 implies that \(e(R_\ell) \ge \ell n^3p^3\). Consequently, since \(R_\ell\subseteq T\in \mathcal{F}_{\ref{type:b}}\), we must have that \(\ell=\ell(H)\leq \log n\).

We are finally in a position to bound the probability that \({\boldsymbol{S}}(G) = {\boldsymbol{S}}\) for each possible stamp \({\boldsymbol{S}}=({\boldsymbol{J}}, {\boldsymbol{R}})\). Recall the definition of \(\mathcal{H}'\) and let \[{\boldsymbol{\mathcal{S}}}=\left\{{\boldsymbol{S}}(H)=({\boldsymbol{J}}(H), {\boldsymbol{R}}(H)): H\in \mathcal{H}'\right\}\] be the set of stamps obtained by running the above process on all possible graphs \(H\in \mathcal{H}'\). Further, for \(0\leq k \leq \log n\), let \({\boldsymbol{\mathcal{S}}}^k\mathrel{\vcenter{:}}=\{{\boldsymbol{S}}(H): H\in \mathcal{H}', \ell(H)=k\}\subseteq {\boldsymbol{\mathcal{S}}}\) be the stamps of length \(k\).

Since \({\boldsymbol{S}}(G)\) is only defined for \(G \in \mathcal{H}'\), the event that \({\boldsymbol{S}}(G)={\boldsymbol{S}}\) implicitly implies that \(G\in \mathcal{H}'\).

It remains to perform a union bound over all possible stamps \({\boldsymbol{S}}\in{\boldsymbol{\mathcal{S}}}\). We have that \[\begin{align} \Pr[G\in \mathcal{H}']=\sum_{{\boldsymbol{S}}\in{\boldsymbol{\mathcal{S}}}}\Pr[{\boldsymbol{S}}(G)={\boldsymbol{S}}]= \sum^{\log n}_{k=0}\underbrace{\sum_{{\boldsymbol{S}}\in{\boldsymbol{\mathcal{S}}^k}}\Pr[{\boldsymbol{S}}(G)={\boldsymbol{S}}]}_{\Sigma^k}. \end{align}\] In order to get a grasp on \(\Sigma^k\), consider the following random process that constructs increasing random sequences \({\boldsymbol{J}^*}=(J^*_0,\dotsc,J^*_k)\) and \({\boldsymbol{R}^*}=(R_0^*,\dotsc,R_k^*)\) of subgraphs of \(K_n\):

The key observation is that, for any \({\boldsymbol{S}}=((J_0,\ldots,J_k),(R_0,\ldots,R_k))\in {\boldsymbol{\mathcal{S}}}^k\), \[\Pr\big(({\boldsymbol{J}^*},{\boldsymbol{R}^*})={\boldsymbol{S}}\big) \ge q^*({\boldsymbol{S}})\mathrel{\vcenter{:}}=\left(\dbinom{\binom{n}{3}}{c_0} 2^{3c_0}{ \prod_{i=0}^{k-1} }\left( \dbinom{|\Pi(S_i)|n}{\alpha |\Pi(S_i)|np^2} 2^{2\alpha |\Pi(S_i)|np^2}\right)\right)^{-1},\] where, for each \(i\), we denote by \(S_i=S(R_i)\) the graph output by Lemma 42 with input \(R_i\). Since clearly \(\sum_{{\boldsymbol{S}}\in {\boldsymbol{\mathcal{S}}}^k} q^*({\boldsymbol{S}})\leq 1\), we have \[\Sigma^k \le \frac{\sum_{{\boldsymbol{S}}\in {\boldsymbol{\mathcal{S}}}^k} \Pr[{\boldsymbol{S}}(G) = {\boldsymbol{S}}]}{\sum_{{\boldsymbol{S}}\in {\boldsymbol{\mathcal{S}}}^k} q^*({\boldsymbol{S}})} \leq \max \big\{ \Pr[{\boldsymbol{S}}(G) = {\boldsymbol{S}}] \cdot q^*({\boldsymbol{S}})^{-1} : {\boldsymbol{S}} \in {\boldsymbol{S}}^k\big\}.\] Now, fix some \({\boldsymbol{S}}=((J_0,\ldots,J_k),(R_0,\ldots,R_k))\in {\boldsymbol{\mathcal{S}}}^k\) and let \(S_i\mathrel{\vcenter{:}}= S(R_i)\) and \(M_i\mathrel{\vcenter{:}}=\alpha |\Pi(S_i)|np^2\) for each \(i \in \{0, \dotsc, k-1\}\). By Claims 47 and 48, we have that \(e(J_k)=3c_0+\sum_{i=0}^{k-1}2M_i\) and thus \[\begin{align} \Pr[{\boldsymbol{S}}(G)={\boldsymbol{S}}] \cdot q^*({\boldsymbol{S}})^{-1} &\leq p^{e(J_k)} \exp(-\zeta n^3p^5 e(J_k)) \cdot \left(\frac{8en^3/6}{\theta n^3p^3}\right)^{c_0} \prod_{i=0}^{k-1} \left(\frac{4e|\Pi(S_i)|n }{\alpha |\Pi(S_i)|np^2}\right)^{M_i} \\ & \leq \exp({-\zeta n^3p^5 e(J_k)}) \cdot \left(\frac{4}{\theta}\right)^{c_0} \prod_{i=0}^{k-1} \left( \frac{4e}{\alpha}\right)^{M_i} \\ &\leq \exp\left(- e(J_k) \cdot \left(\zeta n^3p^5 + \log \theta + \log \alpha \right)\right) \le \exp(-e(J_k)), \end{align}\] as \(n^3p^5\gg 1\). Since \(e(J_k)\geq c_0\gg n\), we conclude that \(\Sigma^k \le e^{-n}\) and, consequently, \(\Pr(G \in \mathcal{H}') \ll 1\). ◻

Derivation of Theorem [thm:containers] from Theorem 49. Let \(\mathcal{H}\) be a nonempty \(k\)-uniform hypergraph with vertex set \(V\) and let \(\varepsilon>0\) and \(K\in\mathbb{N}\). We set \(s \mathrel{\vcenter{:}}= s_{\ref{thm:containers-Saxton-Thomason}}(k, \varepsilon)\) to be the constant output by Theorem 49 with input \(k\) and \(\varepsilon\) and let \[L \mathrel{\vcenter{:}}= \left\lceil \frac{12k!2^{\binom{k}{2}}K}{\varepsilon} \right\rceil, \qquad t \mathrel{\vcenter{:}}= 2Ls^2, \qquad \text{and} \qquad \delta \mathrel{\vcenter{:}}= 24 \varepsilon k! k L^k.\] Suppose that the maximum degrees of \(\mathcal{H}\) satisfy the assumptions of the theorem for some \(\tau\le 1/t\). Note that, for every \(j \in \{2, \dotsc, k\}\), \[\delta_j(\mathcal{H}, L \tau) \leq \frac{(L \tau)^{1-j}}{ke(\mathcal{H})} \cdot v(\mathcal{H}) \Delta_j(\mathcal{H}) \le \frac{KL^{1-j}}{k}\] and thus, as \(L \ge 2\), \[\delta(\mathcal{H}, L\tau) \le 2^{\binom{k}{2}-1} \cdot \sum_{j=2}^{k}\frac{KL^{1-j}}{k} \le \frac{2^{\binom{k}{2}}K}{L} \le \frac{\varepsilon}{12k!}.\] Consequently, Theorem 49, invoked with \(\tau_{\ref{thm:containers-Saxton-Thomason}} = L\tau\), implies that there exist a function \(C \colon \mathcal{P}(V)^s \to \mathcal{P}(V)\) that satisfies conditions [item:containers-ST-1] and [item:containers-ST-2] of that theorem. Here, we used that \(\tau \le 1/t\) implies that \(L\tau<1/2\). Now define \(f \colon \mathcal{P}(V)^t \to \mathcal{P}(V)\) by letting \[f(S_1, \dotsc, S_t) \mathrel{\vcenter{:}}= C\big(S_1 \cup \dotsb \cup S_{t/s}, \dotsc, S_{(s-1)t/s+1} \cup \dotsb \cup S_t\big).\] If \(I \subseteq V\) satisfies \[e(\mathcal{H}[I]) \le \delta \tau^k e(\mathcal{H}) \le 24\varepsilon k!k (L \tau)^k e(\mathcal{H}),\] then there are \(T_1, \dotsc, T_s \subseteq I\), with \(|T_i| \le s L\tau |V|\) for each \(i\), such that \(I \subseteq C(T_1, \dotsc, T_s)\). This gives the assertion of part [item:almostindep] of the theorem, as we may partition each \(T_i\) into \(t/s\) sets \(S_{t(i-1)/s+1}, \dotsc, S_{t(i+1)/s}\), each of size at most \(\lceil s/t \cdot sL\tau |V| \rceil \le \tau |V|\). Part [item:containersparse] of the theorem follows directly from our definition of \(f\) and part [item:containers-ST-2] of Theorem 49. ◻