For each colour \(i \in [r]\), define a function \(\sigma _i \colon X \rightarrow \mathbb {R}^{\cup _i Y_i}\) as follows: for each \(x \in X\), choose a set \(N'_i(x) \subset N_i(x) \cap Y_i\) of size exactly \(p_i|Y_i|\), where \(p_i = p_i(X,Y_i)\), and set

where \(\hbox{$1\mkern -6.5mu1$}_S \in \{ 0,1\} ^{\cup _i Y_i}\) denotes the indicator function of the set \(S\). Note that, for any \(x,y\in X\),

Indeed, for every \(x,y\in X\), we have

Where the last ineqaulity follows since \(|N'_i(x)|= N'_i(y)|= p_i|Y_i|\) and both sets are subsets of \(Y_i\). Now, by Lemma 15, there exists \(\lambda \ge -1\) and colour \(\ell \in [r]\) such that

where \(U\), \(U'\) are independent random variables distributed uniformly in the set \(X\). We claim that there exists a vertex \(x \in X\) and a set \(X' \subset X\) such that,

and

for every \(y \in X'\), and

for every \(y \in X'\) and \(i \in [r]\). To see this, we let

Since \(U\) and \(U'\) are independent and uniformly distributed over \(x\), Equation 16 implies that

However, by averaging, there must then exist a vertex \(x \in X\) such that:

We can them simply pick this \(X'\) to be the desired subset. Setting \(Y'_i = N'_i(x)\) for each \(i \in [r]\), it follows that

and

for every \(i \in [r]\), as required.

Note first that if \(Y_i(s+1) = Y_i(s)\), then \(p_i(s+1) \ge p_i(s)\), since the minimum degree does not decrease when we take a subset of \(X(s)\). When we perform a colour step in colour \(i\), we have \(p_i(s+1) \ge p_i(s) - \alpha _i(s)\), by Lemma ??, and hence

by our choice of \(\alpha _i(s)\). Similarly, when we perform a density-boost step in colour \(i\) we have \(p_i(s+1) \ge p_i(s) + \lambda (s) \alpha _i(s)\), by Lemma ??, and hence

Recalling that there are at most \(t\) colour steps in colour \(i\), and that \(p_i(0) \ge p_0\), by the definition ?? of \(p_0\), the claimed bound follows.

Both bounds follow immediately from 21 and the definition of \(\alpha _i(s)\).

Since \(\lambda (j) {\gt} \lambda _0\) for every \(j \in \mathcal{B}_i(s)\), and \(p_i(s) \le 1\), it follows from 21 that

Since \(t \ge \lambda _0\) and \(\delta \le 1/4\), the claimed bound follows.

Note that \(Y_i(j+1) \ne Y_i(j)\) for at most \(t + |\mathcal{B}_i(s)|\) of the first \(s\) steps, and for those steps we have

by 14 and Lemma 19.

If \(\lambda (j) \le \lambda _0\), then by 13 and Step 2 of the algorithm we have

On the other hand, if \(\lambda (j) {\gt} \lambda _0\), then \(j \in \mathcal{B}(s)\), and we have

by 13 and Step 3 of the algorithm. Since there are at most \(rt\) colour steps, and \(\beta \ge \varepsilon \), the claimed bound follows.

Observe first that, by Lemma 18, we have

for each \(i \in [r]\). Note also that \(\lambda _0 \le \lambda (j) \le 5t/\delta \) for every \(j \in \mathcal{B}(s)\), where the lower bound holds by the definition of \(\mathcal{B}(s)\), and the upper bound by 23 and since \(\delta \le 1/4\). Now, since \(\log (1+x) \ge \min \{ x/2,1\} \) for all \(x {\gt} 0\), it follows that

where in the second inequality we used our assumption that \(t \ge \lambda _0 / \delta \). It now follows that

where the first inequality holds by 24, and the second follows from 23, since \(\delta \le 1/4\). Summing over \(i \in [r]\), we obtain the claimed bound.

Recall that we are given an \(r\)-colouring \(\chi \) of \(E(K_n)\) and a collection of sets \(X,Y_1,\ldots ,Y_r \subset V(K_n)\) with

for each \(i \in [r]\), for some \(p {\gt} 0\), \(\mu \ge 2^{10} r^3\) and \(t,m \in \mathbb {N}\) with \(t \ge \mu ^5 / p\), and moreover

for every \(x \in X\) and \(i \in [r]\). We will run the multicolour book algorithm with

where \(C = 4r^{3/2}\) (as before), and show that it ends with

and therefore produces a monochromatic \((t,m)\)-book.

To do so, we just need to bound the sizes of the sets \(X(s)\) and \(Y_i(s)\) from below. Observe that \(t \ge \lambda _0\) and \(\delta \le 1/4\), and therefore, by Lemma 20, that

for every \(i \in [r]\) and \(s \in \mathbb {N}\). Since \(p_0 \ge p\), by 26 and the definition of \(p_0\), it follows that

where the first inequality holds by Lemma 21, and the second by 25 and 27. Noting that \(p^{|\mathcal{B}_i(s)|} \ge e^{-2^{12} r^3 t / \mu ^2}\), by 27, and that \(\delta / p = 1/\mu ^2\), it follows that

as claimed. To bound \(|X(s)|\), recall 22 and observe that

where the first step holds because \(\varepsilon = (\beta / r) e^{- C \sqrt{\lambda _0 + 1}}\) and \(|\mathcal{B}(s)| \le rt\), by 27, and the second step holds because \(\beta = 3^{-4r}\) and \(\lambda _0 \ge 2^{10} r^3\). Moreover, we have

by Lemma 23 and our choice of \(\lambda _0\), and therefore

for every \(s \in \mathbb {N}\), by Lemma 22 and since \(\mu \ge 2^{10} r^3\) and \(C = 4r^{3/2}\). It follows that the algorithm produces a monochromatic \((t,m)\)-book, as claimed.