Proof. Let $N=(x+y\alpha +\eta )n$ where $\eta \gt 0$ is sufficiently small. Consider a red/blue edge colouring of $K_N$ on vertex set $[N]$ . We assume that $\gamma \gt 0$ is taken sufficiently small in terms of $\eta$ . Set $\delta =\gamma ^2/2$ . Note that $\varepsilon$ is sufficiently small in terms of $\delta$ , since $\varepsilon$ is sufficiently small in terms of $\gamma$ .

By Lemma 2.1, there is an equitable $\varepsilon$ -regular partition $[N]=\sqcup _{i=1}^k V_i$ for the red graph $R$ , i.e., (i) $||V_i|-|V_j||\le 1$ for all distinct $i$ and $j$ ; (ii) each part $V_{i}$ is $\varepsilon$ -regular; and (iii) for every $1\le i\le k$ , there are at most $\varepsilon k$ values $1\le j\le k$ such that the pair $(V_i, V_j)$ is not $\varepsilon$ -regular. Because the colours are complementary, the same conclusion holds for the blue graph. For convenience, we may assume $|V_i|=N/k\,{=:}\,t$ for all $i\in [k]$ . By the assumption that $R$ is $B_n$ -free and $B$ is $B_{\alpha n}$ -free, we have

(3) \begin{align} bk_R&\lt \frac{1}{x+y\alpha +\eta }N=\frac{1}{x+y\alpha +\eta }kt\le \left (\frac{1}{x+y\alpha }-\gamma \right )kt, \end{align}

(4) \begin{align} bk_B&\lt \frac{\alpha }{x+y\alpha +\eta }N=\frac{\alpha }{x+y\alpha +\eta }kt\le \alpha \left (\frac{1}{x+y\alpha }-\gamma \right )kt. \end{align}

Now we shall prove that there exists no $(3,\varepsilon,\gamma )$ -red-blocked configuration. On the contrary, we may assume that $V_1,V_2,V_3$ is a $(3,\varepsilon,\gamma )$ -red-blocked configuration. Let $M$ be the set of all $s\in [k]\setminus [3]$ such that every pair $(V_i,V_s)$ for $i\in [3]$ is $\varepsilon$ -regular; clearly, $|M|\ge (k-3)-3\varepsilon k\geq (1-4\varepsilon )k$ .

We compute the maximum size of the red books with bases in $E(V_i)$ for $i\in [3]$ . Since the red density of the pair $(V_i,V_s)$ is $d_{is}$ , we apply Lemma 2.2 to obtain that

(5) \begin{align} bk_R\ge \sum \limits _{s\in M} (d_{is}^2-\delta )t. \end{align}

On the other hand, applying Lemma 2.2, we obtain that the maximum size $S$ of the blue books with bases in $E(V_1,V_2)$ satisfies

(6) \begin{align} bk_B\ge S\ge \sum \limits _{s\in M}((1-d_{1s})(1-d_{2s})-\delta )t. \end{align}

Considering in turn $(V_1,V_3)$ and $(V_2,V_3)$ , we obtain exactly in the same way,

(7) \begin{align} bk_B\ge \sum \limits _{s\in M}((1-d_{1s})(1-d_{3s})-\delta )t, \end{align}

(8) \begin{align} bk_B\ge \sum \limits _{s\in M}((1-d_{2s})(1-d_{3s})-\delta )t. \end{align}

Let

\begin{equation*}d_s=\sum _{i=1}^3d_{is},\;\;\text {and} \;\;d_0=\frac {1}{|M|}\sum \limits _{s\in M}d_s.\end{equation*}

Adding (6), (7), and (8) each multiplied by $y/3$ together with (5) for each $i\in [3]$ multiplied by $x/3$ , noting $2x\ge y$ , and applying Cauchy’s inequality to the double sum we obtain

\begin{align*} y\cdot bk_B+x\cdot bk_R \geq & \frac{y}{3}\sum \limits _{s\in M}\left (3-2d_s+\sum \limits _{1\le i\lt j\le 3}d_{is}d_{js}-3\delta \right )t+\frac{x}{3}\sum _{s\in M}\left (\sum _{i=1}^3d_{is}^2-3\delta \right )t \\[3pt] \ge & \sum _{s\in M}\left (\frac{y}{3}\left (3-2d_s+\frac{d_s^2}{2}-\frac{1}{2}\sum _{i=1}^3d_{is}^2\right ) +\frac{x}{3}\sum _{i=1}^3d_{is}^2\right )t-(x+y)\delta kt \\[3pt] \geq & \sum _{s\in M}\left (\frac{y}{3}\left (3-2d_s+\frac{d_s^2}{2}\right )+\left (\frac{x}{3}-\frac y6\right )\cdot \frac 13{d_s^2}\right )t-(x+y)\delta kt \\[3pt] =&\sum _{s\in M}\left (\frac{y}{3}\left (3-2d_s\right )+\frac{x+y}{9}{d_s^2}\right )t-(x+y)\delta kt \\[3pt] \geq & |M|\left (\frac{y}{3}\left (3-2d_0\right )+\frac{x+y}{9}{d_0^2}\right )t-(x+y)\delta kt. \end{align*}

Therefore, from (3) and (4), we obtain that

\begin{align*} |M|\left (\frac{y}{3}\left (3-2d_0\right )+\frac{x+y}{9}{d_0^2}\right )t-(x+y)\delta kt \lt \left (y\alpha \left (\frac{1}{x+y\alpha }-\gamma \right )+ x\left (\frac{1}{x+y\alpha }-\gamma \right )\right )kt. \end{align*}

Since $|M|\geq (1-4\varepsilon )k$ , we have

\begin{equation*}(1-4\varepsilon )\left (\frac {x+y}{9}d_0^2-\frac {2y}{3}d_0+y\right )-(x+y)\delta \lt 1-(x+y\alpha )\gamma .\end{equation*}

Thus, by noting $\delta =\gamma ^2/2$ , $\varepsilon$ is sufficiently small in terms of $\gamma$ , we have

\begin{align*} \frac{x+y}{9}d_0^2-\frac{2y}{3}d_0+y-1\lt \frac{1-(x+y\alpha )\gamma +(x+y)\delta }{1-4\varepsilon }-1= \frac{-(x+y\alpha )\gamma +(x+y)\gamma ^2/2+4\varepsilon }{1-4\varepsilon }. \end{align*}

This leads to a contradiction since the right-hand side is negative for sufficiently small $\gamma$ and the left-hand side is non-negative for $\frac{x+y}{9}\gt 0$ and the discriminant of the quadratic form $\Delta =(\frac{2y}{3})^2-\frac{4(x+y)(y-1)}{9}=\frac 49({-}xy+x+y)=0$ since $x+y=xy$ .

It remains to prove that there exists no $(2,\varepsilon,\gamma )$ -blue-blocked configuration. On the contrary, suppose that $V_1,V_2$ is a $(2,\varepsilon,\gamma )$ -blue-blocked configuration without loss of generality. Let $M$ be the set of all $s\in [k]\setminus [2]$ such that all pairs $(V_1, V_s)$ and $(V_2, V_s)$ are $\varepsilon$ -regular; clearly $|M|\ge (k-2)-2\varepsilon k\geq (1-3\varepsilon )k$ .

By a similar argument as aforementioned, we obtain that for $i\in [2]$ ,

(9) \begin{align} bk_B\ge \sum _{s\in M}((1-d_{is})^2-\delta )t. \end{align}

Similarly,

(10) \begin{align} bk_R\ge \sum \limits _{s\in M}(d_{1s}d_{2s}-\delta )t. \end{align}

Let $d_s=\sum _{i=1}^2 d_{is}$ , and $d_0=\frac{1}{|M|}\sum _{s\in M}d_s.$ Adding (10) multiplied by $x$ together with (9) for each $i\in [2]$ multiplied by $y/2$ , noting $x\le y$ , and applying Cauchy’s inequality to the double sum we obtain

\begin{align*} y\cdot bk_B+x\cdot bk_R \geq & \frac y2\sum _{s\in M}\left (2-2d_s+\sum _{i=1}^2 d_{is}^2-2\delta \right )t+x\sum _{s\in M}\left (d_{1s}d_{2s}-\delta \right )t \\\ge & \sum _{s\in M}\left (\frac y2(2-2d_s)+\frac{y}{2}\sum _{i=1}^2 d_{is}^2+\frac x2\left (d_s^2-\sum _{i=1}^2 d_{is}^2\right )\right )t-(x+y)\delta kt \\ \geq & \sum _{s\in M}\left (\frac y2(2-2d_s)+\frac{y+x}{2}\cdot \frac{d_s^2}{2}\right )t-(x+y)\delta kt \\ \geq & |M|\left (\frac y2(2-2d_0)+\frac{y+x}{4}d_0^2\right )t-(x+y)\delta kt. \end{align*}

Therefore, from (3) and (4), we obtain that

\begin{align*} |M|\left (\frac y2(2-2d_0)+\frac{y+x}{4}d_0^2\right )t-(x+y)\delta kt \lt \left (y\alpha \left (\frac{1}{x+y\alpha }-\gamma \right )+ x\left (\frac{1}{x+y\alpha }-\gamma \right )\right )kt. \end{align*}

Since $|M|\geq (1-3\varepsilon )k$ , we have

\begin{equation*}(1-3\varepsilon )\left (\frac {y+x}{4}d_0^2-yd_0+y\right )-(x+y)\delta \lt 1-(x+y\alpha )\gamma .\end{equation*}

Thus, by noting $\delta =\gamma ^2/2$ , $\varepsilon$ is sufficiently small in terms of $\gamma$ , we have that

\begin{align*} \frac{y+x}{4}d_0^2-yd_0+y-1\lt \frac{1-(x+y\alpha )\gamma +(x+y)\delta }{1-3\varepsilon }-1= \frac{-(x+y\alpha )\gamma +(x+y)\gamma ^2/2+3\varepsilon }{1-3\varepsilon }. \end{align*}

This leads to a contradiction since the right-hand side is negative for sufficiently small $\gamma$ and the left-hand side is non-negative for $\frac{y+x}{4}\gt 0$ and the discriminant of the quadratic form $\Delta =y^2-(y+x)(y-1)=-xy+x+y=0$ . This completes the proof of Lemma 3.2.

Proof of Theorem 1.4. Let $1/4\leq \alpha \leq 1$ be fixed, and $\eta \gt 0$ is sufficiently small and $n$ is sufficiently large. Let $N=(x+y\alpha +\eta )n$ where $x+y=xy$ , $1\leq x\leq y\leq 2x$ . Consider a red/blue edge colouring of $K_N$ on vertex set $[N]$ . Let $\gamma \gt 0$ be sufficiently small in terms of $\eta$ . Set $\delta =\gamma ^2/2$ . We assume that $\varepsilon \gt 0$ is sufficiently small in terms of $\delta$ and $\gamma$ .

By Lemma 2.1, there is an equitable $\varepsilon$ -regular partition $[N]=\sqcup _{i=1}^k V_i$ for the red graph $R$ , i.e., (i) $||V_i|-|V_j||\le 1$ for all distinct $i$ and $j$ ; (ii) each part $V_{i}$ is $\varepsilon$ -regular; and (iii) for every $1\le i\le k$ , there are at most $\varepsilon k$ values $1\le j\le k$ such that the pair $(V_i, V_j)$ is not $\varepsilon$ -regular. Because the colours are complementary, the same conclusion holds for the blue graph. For convenience, we may assume $|V_i|=N/k\,{=:}\,t$ for all $i\in [k]$ . It suffices to show that for all sufficiently large $n$ , there exists a red $B_n$ or a blue $B_{\alpha n}$ . On the contrary,

(11) \begin{align} bk_R&\lt \frac{1}{x+y\alpha +\eta }N=\frac{1}{x+y\alpha +\eta }kt\le \left (\frac{1}{x+y\alpha }-\gamma \right )kt, \end{align}

(12) \begin{align} bk_B&\lt \frac{\alpha }{x+y\alpha +\eta }N=\frac{\alpha }{x+y\alpha +\eta }kt\le \alpha \left (\frac{1}{x+y\alpha }-\gamma \right )kt. \end{align}

We call a cluster $V_{i}$ red if at least half of its internal edges are red and blue otherwise. Clearly, every cluster is either red or blue.

Now we assume that $V_1,\ldots, V_l$ are blue clusters without loss of generality and set $l=\lambda k$ , $0\le \lambda \le 1$ . To finish the proof, we will show that (11) or (12) is not true.

We first fix a blue cluster $V_i$ and compute the maximum size of the blue books whose bases lie in $E(V_i)$ . Let $M_i$ be the set of all $s\in [k]\setminus \{i\}$ such that $(V_i, V_s)$ is an $\varepsilon$ -regular pair, and let $M_{i1} =M_i\cap [l].$ Clearly, $l\ge |M_{i1}|\ge l-1-\varepsilon k\ge (\lambda -2\varepsilon )k$ since $|M_i|\ge (1-\varepsilon )k$ .

By Lemma 3.2 (2), for every $s\in M_{i1}$ , the red density $d_{is}$ of the pair $(V_i, V_s)$ satisfies $d_{is}\le \gamma$ , so the blue density of $(V_i, V_s)$ is at least $1-\gamma$ . Therefore, by Lemma 2.2 and noting $\delta =\gamma ^2/2$ , the maximum size $S$ of the blue books whose bases are in $E(V_i)$ satisfies

\begin{align*} S\ge \sum _{s\in M_{i1}}\left ((1-\gamma )^2-\delta \right )t\ge (1-2\gamma ) |M_{i1}|t. \end{align*}

Then, by noting $|M_{i1}|\ge (\lambda -2\varepsilon )k$ , we find that

(13) \begin{align} bk_B\ge S \ge (1-2\gamma )(\lambda -2\varepsilon )kt. \end{align}

Next we consider the maximum size of the red books whose bases are contained in a red cluster. Let us define the graph $H$ as follows. The vertex set of $H$ is $[l+1,k]$ and two vertices $i,j\in [l+1,k]$ are joined if and only if the red density $d_{ij}$ of the $\varepsilon$ -regular pair $(V_i, V_j)$ satisfies $d_{ij}\gt 1-\gamma .$

By Lemma 3.2 (1), the complement of $H$ is triangle-free, i.e., the independence number of $H$ is at most two, hence Lemma 2.3 implies that the average degree of $H$ is at least $(k-l)/2-1$ . So there exists a vertex $i\in [l+1,k]$ such that the degree of $i$ in $H$ is at least $(k-l)/2-1$ . Let $N_i$ be the set of all $s\in [k]\setminus \{i\}$ such that $(V_i, V_s)$ is an $\varepsilon$ -regular pair, and let $ N_{i1}=N_i\cap N_H(i).$ Clearly, $k-l\ge |N_{i1}|\ge (k-l)/2-1-\varepsilon k$ since $|N_i|\geq (1-\varepsilon )k$ .

By Lemma 2.2 and $\delta =\gamma ^2/2$ , the maximum size $S$ of the red books whose bases lie in $E(V_i)$ satisfies

\begin{align*} S\ge \sum _{s\in N_{i1}}\left ((1-\gamma )^2-\delta \right )t\geq (1-2\gamma ) |N_{i1}|t. \end{align*}

Then, by noting $|N_{i1}|\ge (k-l)/2-1-\varepsilon k\geq \left (\frac{1-\lambda }{2}-2\varepsilon \right )k$ , we find that

(14) \begin{align} bk_R\ge S \ge (1-2\gamma )\left (\frac{1-\lambda }{2}-2\varepsilon \right )kt. \end{align}

Adding (13) and (14) multiplied by $2$ , we obtain

\begin{align*} 2bk_R+bk_B\geq & (1-2\gamma )\left (1-\lambda -4\varepsilon \right )kt+(1-2\gamma )(\lambda -2\varepsilon )kt \geq (1-2\gamma -6\varepsilon ) kt \end{align*}

To prove Theorem 1.4, we take $x=\sqrt{\alpha }+1$ , $y=1+\frac{1}{\sqrt{\alpha }}$ . Since $\varepsilon$ is sufficiently small in terms of $\gamma$ and $\frac{2+\alpha }{x+y\alpha }\leq 1$ for $\frac 14\leq \alpha \leq 1$ , we have

\begin{equation*}2bk_R+bk_B\geq \left (\frac {2+\alpha }{x+y\alpha }-2\gamma -\alpha \gamma \right ) kt.\end{equation*}

It follows that either $2bk_R\geq (\frac{2}{x+y\alpha }-2\gamma ) kt$ , or $bk_B\geq (\frac{\alpha }{x+y\alpha }-\alpha \gamma ) kt,$ which contradicts (11) or (12), respectively. The proof of Theorem 1.4 is complete.

Proof of Theorem 1.5. Let $1/6\leq \alpha \leq 1/4$ be fixed, and $\eta \gt 0$ is sufficiently small and $n$ is sufficiently large. Let $N=(x+y\alpha +\eta )n$ , where $x=3/2$ and $y=3$ , so $x+y=xy$ . Consider a red/blue edge colouring of $K_N$ on vertex set $[N]$ . Let $\gamma \gt 0$ be sufficiently small in terms of $\eta$ . Set $\delta =\gamma ^2/2$ , and $\varepsilon \gt 0$ is taken sufficiently small in terms of $\delta$ and $\gamma$ .

Similarly, by Lemma 2.1, there is an equitable $\varepsilon$ -regular partition $[N]=\sqcup _{i=1}^k V_i$ for the red graph $R$ . For convenience, we may assume $|V_i|=N/k\,{=:}\,t$ for all $i\in [k]$ . It suffices to show that for all sufficiently large $n$ , there exists a red $B_n$ or a blue $B_{\alpha n}$ . On the contrary,

(15) \begin{align} bk_R&\lt \frac{1}{x+y\alpha +\eta }N=\frac{1}{x+y\alpha +\eta }kt\le \left (\frac{1}{x+y\alpha }-\gamma \right )kt, \end{align}

(16) \begin{align} bk_B&\lt \frac{\alpha }{x+y\alpha +\eta }N=\frac{\alpha }{x+y\alpha +\eta }kt\le \alpha \left (\frac{1}{x+y\alpha }-20\gamma \right )kt. \end{align}

We call a cluster $V_{i}$ red if at least half of its internal edges are red and blue otherwise. Clearly, every cluster is either red or blue. Now we assume that $V_1,\ldots, V_l$ are blue clusters without loss of generality and set $l=\lambda k$ , $0\le \lambda \le 1$ . We first consider a blue cluster $V_i$ and compute the maximum size of the blue books whose bases lie in $E(V_i)$ . Let $M_i$ be the set of all $s\in [k]\setminus \{i\}$ such that $(V_i, V_s)$ is an $\varepsilon$ -regular pair, and let

\begin{align*} M_{i1} =M_i\cap [l], \;\;\text{and}\;\; M_{i2} =M_i\cap [l+1,k]. \end{align*}

Clearly, $l\ge |M_{i1}|\ge l-1-\varepsilon k\geq (\lambda -2\varepsilon ) k$ since $|M_i|\ge (1-\varepsilon )k$ .

By Lemma 3.2 (2), for every $s\in M_{i1}$ , the red density $d_{is}$ of the pair $(V_i, V_s)$ satisfies $d_{is}\le \gamma$ , so the blue density of $(V_i, V_s)$ is at least $1-\gamma$ . Therefore, by Lemma 2.2 and noting $\delta =\gamma ^2/2$ , the maximum size $S$ of the blue books whose bases are in $E(V_i)$ satisfies

\begin{align*} S&\ge \sum _{s\in M_{i1}}\left ((1-\gamma )^2-\delta \right )t+\sum _{s\in M_{i2}}((1-d_{is})^2-\delta )t\\&\ge (1-2\gamma ) |M_{i1}|t+\sum _{s\in M_{i2}}(1-d_{is})^2 t -\delta |M_{i2}|t. \end{align*}

Then, by noting $\varepsilon$ is sufficiently small in terms of $\delta$ , $|M_{i1}|\ge (\lambda -2\varepsilon )k$ and $|M_{i2}|\leq k$ , and applying Cauchy’s inequality, we obtain

\begin{align*} bk_B\ge S \ge & (1-2\gamma )(\lambda -2\varepsilon )kt+\sum _{s\in M_{i2}}(1-d_{is})^2 t -\delta kt \\ \geq & (1-2\gamma )\lambda kt+\frac{1}{|M_{i2}|}\left (\sum _{s\in M_{i2}}(1-d_{is})\right )^2 t -2\delta kt. \end{align*}

Recall (16) and $\delta =\gamma ^2/2$ , we obtain that

(17) \begin{align} \frac{1}{|M_{i2}|}\left (\sum _{s\in M_{i2}}(1-d_{is})\right )^2 t \lt \left (\frac{\alpha }{x+y\alpha }-20\gamma -(1-2\gamma )\lambda +2\delta \right )kt \leq \left (\frac{\alpha }{x+y\alpha }-\lambda -15\gamma \right )kt. \end{align}

We may assume $\lambda \leq \frac{\alpha }{x+y\alpha }\lt 1/2$ , otherwise the right-hand side of (17) is negative, which is not possible since the left-hand side is non-negative. Since $|M_{i2}|\leq k-l=(1-\lambda )k$ , we have

\begin{equation*} \sum _{s\in M_{i2}}(1-d_{is}) \lt k\sqrt {\left (\frac {\alpha }{x+y\alpha }-\lambda -15\gamma \right )(1-\lambda )}. \end{equation*}

Summing over all $i\in [l]$ and noting that $l=\lambda k\lt k/2$ , we obtain that the total blue densities of all regular pairs $(V_i,V_s)$ where $i\in [l]$ and $s\in [l+1,k]$ satisfies that

(18) \begin{align} \sum _{i=1}^l \sum _{s\in M_{i2}}(1-d_{is}) \lt \lambda k^2\sqrt{\left (\frac{\alpha }{x+y\alpha }-\lambda -15\gamma \right )(1-\lambda )}. \end{align}

Next we consider the maximum size of the red books whose bases are contained in a red cluster. Let us define the graph $H$ as follows. The vertices of $H$ are the numbers $[l+1,k]$ and two vertices $i,j$ are joined if and only if the red density $d_{ij}$ of the $\varepsilon$ -regular pair $(V_i, V_j)$ satisfies $d_{ij}\gt 1-\gamma .$

By Lemma 3.2 (1), the complement of $H$ is triangle-free, hence Lemma 2.3 implies that the average degree of $H$ is at least $(k-l)/2-1$ . Thus, recall $l\leq k/2$ , if $k$ is sufficiently large, then

(19) \begin{align} e(H)\ge \frac{k-l}{2}\bigg (\frac{k-l}{2}-1\bigg )\geq \left (\frac{1}{4}-\varepsilon \right )(k-l)^2. \end{align}

For any $i\in [l+1,k]$ , let $N_i$ be the set of all $s\in [k]\setminus \{i\}$ such that $(V_i, V_s)$ is $\varepsilon$ -regular, and let

\begin{align*} N_{i1}=N_i\cap N_H(i), \;\;\text{and}\;\; N_{i2}=N_i\cap [l]. \end{align*}

Since $|N_i|\ge (1-\varepsilon )k$ , we have $ \deg _H(i)\ge |N_{i1}|\ge \deg _H(i)-\varepsilon k.$ Therefore, since $\varepsilon$ is sufficiently small in terms of $\delta$ , the maximum size $S_i$ of the red books whose bases lie in $E(V_i)$ satisfies

\begin{align*} S_i\ge & \sum _{s\in N_{i1}}\left ((1-\gamma )^2-\delta \right )t+\sum _{s\in N_{i2}}(d_{is}^2-\delta )t \\ \ge & (1-2\gamma )|N_{i1}|t+\sum _{s\in N_{i2}}d_{is}^2 t-\delta |N_{i2}|t \\ \ge & (1-2\gamma )\deg _H(i)t+\sum _{s\in N_{i2}}d_{is}^2 t-2\delta kt. \end{align*}

It follows that

\begin{align*} \sum _{i=l+1}^k S_i\ge & \sum _{i=l+1}^k (1-2\gamma )\deg _H(i)t+\sum _{i=l+1}^k \sum _{s\in N_{i2}}d_{is}^2 t-2\delta k(k-l)t \\ \geq & (1-2\gamma )2e(H)t+\sum _{i=l+1}^k\sum _{s\in N_{i2}}d_{is}^2 t-2\delta k(k-l)t. \end{align*}

Hence by (19) and $\varepsilon$ is sufficiently small in terms of $\delta$ , we obtain that

\begin{align*} \sum _{i=l+1}^k S_i \ge & (1-2\gamma )(1/2-2\varepsilon )(k-l)^2t+\sum _{i=l+1}^k\sum _{s\in N_{i2}}d_{is}^2 t-2\delta k(k-l)t \\ \ge & \frac{1}{2}(1-2\gamma )(k-l)^2t+\sum _{i=l+1}^k\sum _{s\in N_{i2}}d_{is}^2 t-4\delta k(k-l)t. \end{align*}

Then by noting that $|N_{i2}|\leq l=\lambda k$ and applying Cauchy’s inequality to the double sum, we have

\begin{align*} bk_R\ge \frac{1}{k-l}\sum _{i=l+1}^k S_i\ge &\frac{1}{2}(1-2\gamma )(k-l)t+\frac{1}{k-l}\sum _{i=l+1}^k\sum _{s\in N_{i2}}d_{is}^2 t-4\delta kt \\ \geq &\frac{1}{2}(1-2\gamma )(1-\lambda )kt+ \frac{1}{(k-l)l}\sum _{i=l+1}^k\left (\sum _{s\in N_{i2}}d_{is}\right )^2 t-4\delta kt \\ \geq &\frac{1}{2}(1-2\gamma )(1-\lambda )kt+ \frac{1}{(k-l)^2l}\left (\sum _{i=l+1}^k \sum _{s\in N_{i2}}d_{is}\right )^2 t-4\delta kt. \end{align*}

So we obtain

(20) \begin{align} bk_R\geq \frac{1}{2}(1-2\gamma )(1-\lambda )kt-4\delta kt. \end{align}

Recall (15), we obtain that

\begin{align*} \frac{1}{(k-l)^2l}\left (\sum _{i=l+1}^k \sum _{s\in N_{i2}}d_{is}\right )^2 t \lt &\left (\frac{1}{x+y\alpha }-\gamma \right )kt-\frac{1}{2}(1-2\gamma )(1-\lambda )kt +4\delta kt \\ \leq & \left (\frac{1}{x+y\alpha }-\frac{1-\lambda }{2}+4\delta \right )kt. \end{align*}

Recall $l=\lambda k$ , we obtain that the total red densities of all regular pairs $(V_i,V_s)$ where $i\in [l+1,k]$ and $s\in [l]$ satisfies that

(21) \begin{align} \sum _{i=l+1}^k \sum _{s\in N_{i2}} d_{is} \lt (1-\lambda )k^2\sqrt{\left (\frac{1}{x+y\alpha }-\frac{1-\lambda }{2}+4\delta \right )\lambda }. \end{align}

Therefore, adding (18) and (21), we obtain

\begin{align*} \sum _{i=1}^{l}\sum _{s\in M_{i2}}1 &=\sum _{i=1}^l \sum _{s\in M_{i2}}(1-d_{is})+\sum _{i=1}^l \sum _{s\in M_{i2}} d_{is} =\sum _{i=1}^l \sum _{s\in M_{i2}}(1-d_{is})+\sum _{i=l+1}^k \sum _{s\in N_{i2}} d_{is} \\&\lt \lambda k^2\sqrt{\left (\frac{\alpha }{x+y\alpha }-\lambda -15\gamma \right )(1-\lambda )}+ (1-\lambda )k^2\sqrt{\left (\frac{1}{x+y\alpha }-\frac{1-\lambda }{2}+4\delta \right )\lambda }. \end{align*}

Note that $\sum _{i=1}^{l}\sum _{s\in M_{i2}}1\geq (k-l)l-\varepsilon k^2=((1-\lambda )\lambda -\varepsilon )k^2$ , we have

\begin{align*} ((1-\lambda )\lambda -\varepsilon )k^2\lt \lambda k^2\sqrt{\left (\frac{\alpha }{x+y\alpha }-\lambda -15\gamma \right )(1-\lambda )} +(1-\lambda )k^2\sqrt{\left (\frac{1}{x+y\alpha }-\frac{1-\lambda }{2}+4\delta \right )\lambda }. \end{align*}

Suppose $\lambda \leq \eta/10$ , then we are done from (20) that

\begin{equation*} bk_R\geq \frac {1}{2}(1-2\gamma )(1-\lambda )kt-4\delta kt\ge \left (\frac {1}{2}-\gamma -\frac \lambda 2-4\delta \right )\left (\frac 32+3\alpha +\eta \right )n\geq n \end{equation*}

by noting $\alpha \ge 1/6$ , and $\gamma$ and $\delta$ are sufficiently small in terms of $\eta$ . Therefore, we may assume $\lambda \gt \eta/10$ .

Since $\gamma$ is sufficiently small in terms of $\lambda$ , $\alpha$ , $x$ and $y$ , and $\delta =\gamma ^2/2$ , and $\varepsilon$ is sufficiently small in terms of $\gamma$ , we obtain

\begin{align*} (1-\lambda )\lambda \lt & \lambda \sqrt{\left (\frac{\alpha }{x+y\alpha }-\lambda \right )(1-\lambda )}+(1-\lambda )\sqrt{\left (\frac{1}{x+y\alpha }-\frac{1-\lambda }{2}\right )\lambda }, \end{align*}

and consequently,

(22) \begin{align} \sqrt{(1-\lambda )\lambda }\lt \sqrt{\left (\frac{\alpha }{x+y\alpha }-\lambda \right )\lambda } +\sqrt{\left (\frac{1}{x+y\alpha }-\frac{1-\lambda }{2}\right )(1-\lambda )}. \end{align}

Since (22) makes sense, we obtain $1-\frac{2}{x+y\alpha }\leq \lambda \leq \frac{\alpha }{x+y\alpha }$ . Recall that $1/6\leq \alpha \leq 1/4$ , $x=3/2$ and $y=3$ , so $\frac{\alpha +{11}/{6}}{x+y\alpha }\leq 1$ , implying $\frac{\alpha }{x+y\alpha } \leq \frac{1}{12}+\frac{11}{12}(1-\frac{2}{x+y\alpha }) \leq \frac{1}{12}+\frac{11}{12}\lambda = \frac{1}{12}(1-\lambda )+\lambda .$ Thus $\frac{\alpha }{x+y\alpha }-\lambda \leq \frac{1}{12}(1-\lambda )$ , and so $\sqrt{(\frac{\alpha }{x+y\alpha }-\lambda )\lambda }\le \frac{1}{2\sqrt{3}}\sqrt{(1-\lambda )\lambda }$ .

Moreover, since $\frac{1}{2}-\frac{1}{x+y\alpha }\ge 0$ , we obtain that

\begin{equation*}\frac {1}{x+y\alpha }-\frac {1}{2} \leq \left (2\left (1-\frac {1}{2\sqrt {3}}\right )^2-1\right )\left (\frac {1}{2}-\frac {1}{x+y\alpha }\right ) \leq \left (\left (1-\frac {1}{2\sqrt {3}}\right )^2-\frac 12\right )\lambda .\end{equation*}

Thus $\frac{1}{x+y\alpha }-\frac{1-\lambda }{2}\leq (1-\frac{1}{2\sqrt{3}})^2\lambda$ , and so $\sqrt{(\frac{1}{x+y\alpha }-\frac{1-\lambda }{2})(1-\lambda )}\le (1-\frac{1}{2\sqrt{3}})\sqrt{(1-\lambda )\lambda }$ .

Therefore, adding these two terms, the right-hand side of (22) is at most $\sqrt{(1-\lambda )\lambda }$ , which leads to a contradiction. The proof of Theorem 1.5 is complete.