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 Theorem 27, 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 Theorem 27, 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 21 of \(p_0\), the claimed bound follows.

Both bounds follow immediately from 22 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 22 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 Theorem 30.

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 Theorem 29, 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 24 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 25, and the second follows from 24, 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 Theorem 31, that

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

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

as claimed. To bound \(|X(s)|\), recall 23 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 28, and the second step holds because \(\beta = 3^{-4r}\) and \(\lambda _0 \ge 2^{10} r^3\). Moreover, we have

by Theorem 34 and our choice of \(\lambda _0\), and therefore

for every \(s \in \mathbb {N}\), by Theorem 33 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.