On a conjecture of Conlon, Fox, and Wigderson

Abstract

For graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest positive integer $N$ such that any red/blue edge colouring of the complete graph $K_N$ contains either a red $G$ or a blue $H$. A book $B_n$ is a graph consisting of $n$ triangles all sharing a common edge.

Recently, Conlon, Fox, and Wigderson conjectured that for any $0\lt \alpha \lt 1$, the random lower bound $r(B_{\lceil \alpha n\rceil },B_n)\ge (\sqrt{\alpha }+1)^2n+o(n)$ is not tight. In other words, there exists some constant $\beta \gt (\sqrt{\alpha }+1)^2$ such that $r(B_{\lceil \alpha n\rceil },B_n)\ge \beta n$ for all sufficiently large $n$. This conjecture holds for every $\alpha \lt 1/6$ by a result of Nikiforov and Rousseau from 2005, which says that in this range $r(B_{\lceil \alpha n\rceil },B_n)=2n+3$ for all sufficiently large $n$.

We disprove the conjecture of Conlon, Fox, and Wigderson. Indeed, we show that the random lower bound is asymptotically tight for every $1/4\leq \alpha \leq 1$. Moreover, we show that for any $1/6\leq \alpha \le 1/4$ and large $n$, $r(B_{\lceil \alpha n\rceil }, B_n)\le \left (\frac 32+3\alpha \right ) n+o(n)$, where the inequality is asymptotically tight when $\alpha =1/6$ or $1/4$. We also give a lower bound of $r(B_{\lceil \alpha n\rceil }, B_n)$ for $1/6\le \alpha \lt \frac{52-16\sqrt{3}}{121}\approx 0.2007$, showing that the random lower bound is not tight, i.e., the conjecture of Conlon, Fox, and Wigderson holds in this interval.

1. Introduction

For graphs $G$ and $H$ , the Ramsey number $r(G,H)$ is the smallest positive integer $N$ such that any red/blue edge colouring of the complete graph $K_N$ contains either a red $G$ or a blue $H$ . A central problem in extremal graph theory is to determine the Ramsey number $r(G,H)$ .

Let $B_{n}^{(k)}$ be the book graph consisting of $n$ copies of $K_{k+1}$ , all sharing a common $K_k$ . We always call $n$ the size of the book. When $k=2$ , we write $B_{n}$ instead of $B_{n}^{(2)}$ . Books have attracted a great deal of attention in graph Ramsey theory, see, for example, the recent breakthrough of Campos, Griffiths, Morris and Sahasrabudhe [1].

For the diagonal Ramsey number of books, Erdős, Faudree, Rousseau and Schelp [2] and independently Thomason [3] proved that $(2^k+o(1))n\le r(B_n^{(k)},B_n^{(k)})\le 4^kn.$ In particular, Rousseau and Sheehan [4] showed that $r(B_n,B_n)=4n+2$ if $4n+1$ is a prime power. Recently, a breakthrough result of Conlon [5] established that for each $k\ge 2$ ,

\begin{align*} r(B_n^{(k)},B_n^{(k)})=2^kn+o(n), \end{align*}

which confirms a conjecture of Thomason [3] asymptotically and also gives an answer to a problem proposed by Erdős, Faudree, Rousseau and Schelp [2]. The error term $o(n)$ of the upper bound has been improved to $O\big (\frac{n}{(\log \log \log n)^{1/25}}\big )$ by Conlon, Fox, and Wigderson [6] using a different method, in particular avoiding the use of the full regularity lemma.

For the off-diagonal Ramsey number of books, a simple lower bound is as follows: for any $k,m,n\in \mathbb{N}$ with $m\le n$ ,

(1) \begin{align} r(B_{m}^{(k)},B_n^{(k)})\ge k(n+k-1)+1. \end{align}

Indeed, this follows from an observation of Chvátal and Harary [7] which states that if $H$ is connected, then $r(G,H)\ge (\chi (G)-1)(|V(H)|-1)+1$ . We say that $H$ is $G$ -good if this inequality is tight. Burr and Erdős [8] initiated the study of such Ramsey goodness problems; the reader is referred to the survey of Conlon, Fox, and Sudakov [9] for a detailed history of the area. Among these results, Nikiforov and Rousseau [10] obtained extremely general results. In particular, they proved the following theorem; see Fox, He and Wigderson [11] for a new proof avoiding the application of the regularity lemma.

Theorem 1.1 (Nikiforov and Rousseau [10]). For every $k\ge 2$ , there exists some $\alpha _0\in (0,1)$ such that, for any $0\lt \alpha \le \alpha _0$ and sufficiently large $n$ ,

\begin{equation*} r(B_{\lceil \alpha n\rceil }^{(k)},B_n^{(k)})= k(n+k-1)+1. \end{equation*}

Since we are concerned with the asymptotic behaviour of the Ramsey number, we always omit the ceiling and floor signs henceforth.

We know that $\alpha _0$ in Theorem 1.1 is always small. In fact, if $\alpha$ is sufficiently far from $0$ , then the situation of the lower bound is much different. As pointed out by Conlon, Fox, and Wigderson [12], we can get a random lower bound for $r(B_{\alpha n}^{(k)},B_n^{(k)})$ as follows (one can also see [13] for the special case of $k=2$ ). Indeed, for any $k\in \mathbb{N}$ and $0\lt \alpha \le 1$ , let $p=\frac 1{\alpha ^{1/k}+1}$ and $N=(p^{-k}-o(1))n$ . Then we randomly and independently colour every edge of $K_N$ blue with probability $p$ and red with probability $1-p$ . A standard application of the Chernoff bound yields that the probability containing a blue $B_n^{(k)}$ or a red $B_{\alpha n}^{(k)}$ is $o(1)$ . Therefore, for any $k\in \mathbb{N}$ and $0\lt \alpha \le 1$ ,

\begin{equation*} r(B_{\alpha n}^{(k)},B_n^{(k)})\ge (\alpha ^{1/k}+1)^kn-o(n). \end{equation*}

A simple calculation implies that for large $k$ , if $\alpha \gt ((1+o(1))\frac{\log k}k)^k$ , then the above lower bound is much larger than that of (1), where the logarithm is to base $e$ .

Furthermore, Conlon, Fox, and Wigderson [12] show that the random lower bound becomes asymptotically tight at this point.

Theorem 1.2 (Conlon, Fox, and Wigderson [12]). For every $k\ge 2$ , there exists some $\alpha _1=\alpha _1(k)\in (0,1]$ such that, for any fixed $\alpha _1\le \alpha \le 1$ ,

\begin{equation*} r(B_{\alpha n}^{(k)},B_n^{(k)})= (\alpha ^{1/k}+1)^kn+o(n). \end{equation*}

Moreover, one may take $\alpha _1(k)=((1+o(1))\frac{\log k}k)^k$ .

From Theorem 1.1 and Theorem 1.2, we know that for every $k\ge 2$ , there exist $\alpha _0,\alpha _1\in (0,1]$ such that the following holds:

1. (i) if $0\lt \alpha \le \alpha _0$ , then $r(B_{\alpha n}^{(k)},B_n^{(k)})= k(n+k-1)+1$ ;

2. (ii) if $\alpha _1\le \alpha \le 1$ , then $r(B_{\alpha n}^{(k)},B_n^{(k)})= (\alpha ^{1/k}+1)^kn+o(n).$

However, the values of $\alpha _0$ and $\alpha _1$ are not very clear in general. Moreover, although Theorem 1.2 shows that the random lower bound becomes asymptotically tight when $k\to \infty$ , it does not say anything non-trivial in the simplest case $k=2$ except when $\alpha =1$ .

Nikiforov and Rousseau [14] proved that

(2) \begin{align} \text{for any fixed $\alpha \lt 1/6$ and all large $n$, $r(B_{\alpha n},B_n)=2n+3$,} \end{align}

which implies the Ramsey goodness of large books. Moreover, the constant $1/6$ is asymptotically best possible, i.e., for any $\alpha \gt 1/6$ and all large $n$ ,

\begin{equation*}r(B_{\alpha n},B_n)\gt 2n+3.\end{equation*}

Recently, the second author together with Chen and You [13] proved that for all large $m\le n$ , $r(B_m, B_n)\le 2(m+n)+o(n).$ However, the behaviour of $r(B_{\alpha n},B_n)$ is still not well-understood for $1/6\le \alpha \lt 1$ .

More recently, Conlon, Fox, and Wigderson [12, Conjecture 6.1] proposed the following conjecture, which would imply that the random lower bound $r(B_{\alpha n},B_n)\ge (\sqrt{\alpha }+1)^2n-o(n)$ is not tight for any $\alpha \lt 1$ .

Conjecture 1.3 (Conlon, Fox, and Wigderson [12]). For every $\alpha \lt 1$ , the random lower bound for $r(B_{\alpha n},B_n)$ is not tight. In other words, there exists some $\beta \gt (\sqrt{\alpha }+1)^2$ such that $r(B_{\alpha n},B_n)\ge \beta n$ for all $n$ sufficiently large.

Note that Conjecture 1.3 holds for any $\alpha \le 1/6$ , by (2). However, in this paper, we disprove Conjecture 1.3 by showing that the random lower bound is asymptotically tight for any $1/4\leq \alpha \leq 1$ .

Theorem 1.4. For any fixed $1/4\leq \alpha \leq 1$ and sufficiently large $n$ ,

\begin{equation*}r(B_{\alpha n}, B_n)=(\sqrt {\alpha }+1)^2 n+o(n).\end{equation*}

Moreover, we give an upper bound of $r(B_{\alpha n}, B_n)$ for $1/6\leq \alpha \le 1/4$ .

Theorem 1.5. For any fixed $1/6\leq \alpha \le 1/4$ and sufficiently large $n$ ,

\begin{equation*}r(B_{\alpha n}, B_n)\le \left (3/2+3\alpha \right ) n+o(n).\end{equation*}

The inequality is asymptotically tight when $\alpha =1/6$ or $1/4$ .

We also have the following lower bound.

Theorem 1.6. Let $1/6\le \alpha \le \frac{52-16\sqrt{3}}{121}\approx 0.2007$ be fixed, and let $p=\frac{1-\sqrt{\alpha (3-2\alpha )}}{1-2\alpha }$ . Then for all sufficiently large $n$ ,

\begin{equation*}r(B_{\alpha n}, B_n)\geq \frac {3n}{1+2p^2}-o(n).\end{equation*}

The inequality is asymptotically tight when $\alpha =1/6$ .

Remark 1.7. Since $\frac{3}{1+2p^2}\gt (\sqrt{\alpha }+1)^2$ for any $1/6\le \alpha \lt \frac{52-16\sqrt{3}}{121}$ , we have that Conjecture 1.3 holds in this interval.

1.1. Notation

For a book $B_n$ , we refer to the common edge as the base of the book $B_n$ . For a graph $G=(V,E)$ with vertex set $V$ and edge set $E$ , we write $bk_G$ for the size of the largest book in a graph $G$ . Let $uv$ denote an edge of $G$ . For $X \subseteq V$ , $e(X)$ is the number of edges in $X$ . For two disjoint subsets $X,Y\subseteq V$ , $e_G(X,Y)$ denotes the number of edges between $X$ and $Y$ . The neighbourhood of a vertex $v$ in $U\subseteq V$ is denoted by $N_G(v,U)$ , and $\deg _G(v,U)=|N_G(v,U)|$ and the degree of $v$ in $G$ is $\deg _G(v)=|N_G(v,V)|$ . Let $X \sqcup Y$ denote the disjoint union of $X$ and $Y$ . Let $[n]=\{1,2,\dots,n\}$ , and $[m,n]=\{m,m+1,\dots,n\}$ . We always delete the subscriptions if there is no confusion from the context.

The rest of the paper is organised as follows. In Section 2, we will collect several useful lemmas. In Sections 3 and 4, we shall present the proofs of Theorems 1.4, 1.5 and 1.6. Finally, we will have some discussion in Section 5.

2. Preliminaries

The proofs rely on the regularity method [15], which is a powerful tool in extremal graph theory. There are many important applications of the regularity lemma, and we refer the reader to the nice surveys [16–18] and many other recent references.

Let $G=(V,E)$ be a graph. For two vertex sets $A,B\subseteq V(G)$ , we call $d(A,B)=\frac{e(A,B)}{|A||B|}$ the density of the pair $(A,B)$ . Let $\varepsilon \gt 0$ , a pair $(A,B)$ is said to be $\varepsilon$ -regular if $|d(A,B)-d(X,Y)|\le \varepsilon$ for every $X\subseteq A$ , $Y\subseteq B$ with $|X|\ge \varepsilon |A|$ and $|Y|\ge \varepsilon |B|$ . Also, a subset $A$ is said to be $\varepsilon$ -regular if the pair $(A,A)$ is $\varepsilon$ -regular.

Given a graph $G$ , an equitable $\varepsilon$ -regular partition $V(G)=\sqcup _{i=1}^k V_i$ of $G$ is a partition of $V(G)$ such that (i) $||V_i|-|V_j||\le 1$ for all distinct $i$ and $j$ ; (ii) each $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.

When establishing the asymptotic order of $r(B^{(k)}_n,B^{(k)}_n)$ , Conlon [5, Lemma 3] applied a refined version of the regularity lemma which guarantees a regular subset in each part of the partition for any graph. We will use the following refined regularity lemma due to Conlon, Fox, and Wigderson [6, Lemma 2.1], which is a strengthening of that due to Conlon [5] and the usual version of Szemerédi’s regularity lemma [15].

Lemma 2.1 (Conlon, Fox, and Wigderson [6]).For every $\varepsilon \gt 0$ and $M_0\in \mathbb{N}$ , there is some $M=M(\varepsilon, M_0)\gt M_0$ such that for every graph $G$ , there is an equitable $\varepsilon$ -regular partition $V(G)=\sqcup _{i=1}^k V_i$ where $M_0\le k\le M$ .

We will use the following version of the counting lemma, proved by Conlon [5, Lemma 5]. (A similar counting lemma was proved by Nikiforov and Rousseau [14, Corollary 11], but they required all of the clusters to be different.) For the general local counting lemma, see Rödl and Schacht [18, Theorem 18].

Lemma 2.2 (Conlon [5]). For any $\delta \gt 0$ , there is $\varepsilon \gt 0$ such that if $U_{1},U_{2}$ (not necessarily distinct), $W_{1},\ldots,W_{l}$ are vertex sets with $(U_{1},U_{2})$ $\varepsilon$ -regular of density at least $\delta$ and $(U_{i},W_{j})$ $\varepsilon$ -regular of density $d_{ij}$ for all $i\in [2]$ and $j\in [l]$ , then there exists an edge $u_1 u_2$ where $u_1\in U_1$ and $u_2\in U_2$ such that $u_1$ and $u_2$ have at least $\sum ^{l}_{j=1}(d_{1j}d_{2j}-\delta )|W_{j}|$ common neighbours in $\sqcup _{j=1}^l W_j$ .

We will also use the following well-known Turán’s bound.

Lemma 2.3 (Turán [19]). For any graph $G$ of order $n$ with average degree $d$ , the independence number $\alpha (G)$ is at least $\frac{n}{1+d}.$

3. Proofs of Theorem 1.4 and Theorem 1.5

In the following, for a red/blue edge colouring of $K_N$ , we always use $R/B$ to denote the subgraph induced by all red/blue edges. For every $i,j, (i \neq j$ ), let $d_{ij}$ be the red density of the pair $(V_i, V_j)$ , i.e., $d_{ij}=\frac{e_R(V_i, V_j)}{|V_i||V_j|}$ .

We will use the following definition introduced by Conlon, Fox, and Wigderson [12].

Definition 3.1. Fix parameters $\ell \in \mathbb{N}$ and $\varepsilon,\gamma \in (0,1)$ and suppose that we are given a red/blue colouring of $E(K_N)$ . Then an $\ell$ -tuple of pairwise disjoint vertex sets $V_1,\ldots, V_\ell \subseteq V(K_N)$ is called an $(\ell,\varepsilon,\gamma )$ -red-blocked configuration if the following properties are satisfied:

1. 1. Each $V_i$ is $\varepsilon$ -regular with itself,

2. 2. Each $V_i$ has internal red density at least $\gamma$ , and

3. 3. For all $i\neq j$ , the pair $(V_i,V_j)$ is $\varepsilon$ -regular and has blue density at least $\gamma$ .

Similarly, we say that $V_1,\ldots, V_\ell$ is an $(\ell,\varepsilon,\gamma )$ -blue-blocked configuration if properties (1–3) hold, but the roles of red and blue interchanged.

We first have a specific structure as in the following lemma, where the proof relies on the refined regularity lemma due to Conlon, Fox, and Wigderson [6] together with the idea from Nikiforov and Rousseau [14].

Lemma 3.2. Let $1/6\leq \alpha \leq 1$ , $\varepsilon,\gamma \in (0,1)$ where $\varepsilon$ is sufficiently small in terms of $\gamma$ , and $n$ is a large integer. Consider a red/blue edge colouring of $K_N$ and an equitable $\varepsilon$ -regular partition of $V(R)$ guaranteed by Lemma 2.1 with $N=(x+y\alpha )n+o(n)$ , where $x+y=xy$ , $1\leq x\leq y\leq 2x$ . If $R$ is $B_n$ -free and $B$ is $B_{\alpha n}$ -free, then the following two properties hold:

1. (1) there exists no $(3,\varepsilon,\gamma )$ -red-blocked configuration;

2. (2) there exists no $(2,\varepsilon,\gamma )$ -blue-blocked configuration.

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.

Now, we are ready to give proofs for Theorem 1.4 and Theorem 1.5.

Proof sketches of Theorem 1.4 and Theorem 1.5. Consider a red/blue edge colouring of $K_N$ for some suitable $N$ . On the contrary, we suppose that $bk_R\lt n$ and $bk_B\lt \alpha n$ . Firstly, we apply the refined regularity lemma due to Conlon, Fox, and Wigderson [6] to obtain an equitable $\varepsilon$ -regular partition of $V(R)$ which guarantees the regularity of each cluster with itself. Secondly, from the assumption that $bk_R\lt n$ and $bk_B\lt \alpha n$ , Lemma 3.2 implies that there are no $(3,\varepsilon,\gamma )$ -red-blocked and $(2,\varepsilon,\gamma )$ -blue-blocked configurations, which are the bases for subsequent calculations of the corresponding book sizes. According to the densities of clusters, we partition these clusters into red clusters and blue clusters. For Theorem 1.4, applying the counting lemma due to Conlon [5] to a single red/blue cluster, and combining with Turán’s bound on the subgraph $H$ defined on the red clusters, we finally obtain $2bk_R+bk_B\ge 2n + \alpha n$ , which leads to a contradiction. For Theorem 1.5, based on the lower bounds of the book sizes of $R/B$ , we need to consider the total blue/red densities between red-cluster sets and blue-cluster sets. The situation is more complicated and the computation is much more technical.

The reason we have some improvements is that the specific structure, i.e., there exists no $(3,\varepsilon,\gamma )$ -red-blocked and $(2,\varepsilon,\gamma )$ -blue-blocked configurations, is more in line with the essence for 2-books than the structure that no $(2,\varepsilon,\gamma )$ -red-blocked and $(2,\varepsilon,\gamma )$ -blue-blocked configurations used by Conlon, Fox, and Wigderson [12]. In particular, the refined regularity lemma by Conlon, Fox, and Wigderson [6] is a key ingredient of the proofs.

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.

4. Proof of Theorem 1.6

Let $\frac 16\le \alpha \le \frac{52-16\sqrt{3}}{121}$ be fixed, and $p=\frac{1-\sqrt{\alpha (3-2\alpha )}}{1-2\alpha }$ , and $N=(\frac{3}{1+2p^2}-\eta )n$ , where $\eta \gt 0$ is sufficiently small and $n$ is sufficiently large. We shall show that for sufficiently large $N$ there exists a partially random red/blue colouring of the edges of $K_{N}$ for which

\begin{equation*}bk_{R}\lt n,\quad \text {and} \quad bk_{B}\lt \alpha n.\end{equation*}

For convenience, assume that $N$ is divisible by 3. Partition $[N]$ into three sets $A_{1},A_{2},A_{3}$ , each with $N/3$ vertices, and colour the graphs induced by $A_{1},A_{2},A_{3}$ in red. Then edges of the form $uv$ where $u\in A_i,v\in A_{j}$ $(1\le i\lt j\le 3)$ are independently coloured red with probability $p$ and blue with probability $1-p$ . For $u,v\in A_{i}$ , the size of the red book with base $uv$ is a random variable with expected value

(23) \begin{align} \frac{N}{3}-2+\frac{2N}{3}p^2\leq \frac N3(1+2p^2)= \frac 13\left (\frac{3}{1+2p^2}-\eta \right )(1+2p^2)n=\left (1-\frac{(1+2p^2)\eta }{3}\right )n. \end{align}

Now suppose $u\in A_{i}$ and $v\in A_{j}$ where $i\neq j$ . If $uv$ is a blue edge, the size of the blue book with base $uv$ is a random variable with expected value

\begin{align*} \frac{N}{3}(1-p)^2= \frac 13\left (\frac{3}{1+2p^2}-\eta \right )(1-p)^2n=\left (\frac{(1-p)^2}{1+2p^2}-\frac{(1-p)^2\eta }{3}\right )n= \left (1-\frac{(1+2p^2)\eta }{3}\right )\alpha n, \end{align*}

by noting that $\alpha =\frac{(1-p)^2}{1+2p^2}$ .

By noting (23), if $uv$ is a red edge, then the size of the red book with base $uv$ is a random variable with expected value

\begin{align*} \frac N3 p^2+\left (\frac{2N}{3}-2\right )p\leq \frac{N}{3}-2+\frac{2N}{3}p^2\leq \left (1-\frac{(1+2p^2)\eta }{3}\right )n. \end{align*}

We will use the following version of the Chernoff bound [20, Corollary 2.4 and Theorem 2.8]: let $X_1, \ldots, X_t$ be independent random variables taking values in {0,1} and let $X=\sum _{i=1}^t X_i$ . If $x\geq c\mathbb{E}(X)$ for some $c\gt 1$ , then $\mathrm{Pr}(X\geq x)\leq e^{-c'x}$ , where $c'=\ln c-1+\frac 1c$ .

Plugging in $c=1/(1-\frac{(1+2p^2)\eta }{3})$ , since $y=\ln x-1+\frac 1x$ is increasing when $x\geq 1$ , we find that $c'\gt 0$ . Since $\mathrm{Pr}(X_1\geq n)\leq e^{-c'n}$ and $\mathrm{Pr}(X_2\geq \alpha n)\leq e^{-c'\alpha n}$ , where $X_1$ denotes the size of a red book and $X_2$ denotes the size of a blue book, applying a union bound over all edges, we obtain that the probability that there is a red book $B_n$ or a blue book $B_{\alpha n}$ tends to 0 as $n\to \infty$ . Thus for large enough $N$ the desired red/blue colouring of the edges of $K_{N}$ exists.

5. Concluding remarks

From the result of Nikiforov and Rousseau [14], we know the exact value of $r(B_{\alpha n}, B_n)$ for $0\lt \alpha \lt 1/6$ ; and from Theorem 1.4, we know the asymptotic behaviour of $r(B_{\alpha n}, B_n)$ for $1/4\le \alpha \le 1$ , i.e., the random lower bound $r(B_{\alpha n},B_n)\ge (\sqrt{\alpha }+1)^2n+o(n)$ is asymptotically tight for $1/4\le \alpha \le 1$ . Moreover, the asymptotic behaviour of $r(B_{n}, B_n)$ is already known from a more general result, see [5,6]. For the remaining cases, when $1/6\le \alpha \le 1/4$ , we only know that $r(B_{\alpha n}, B_n)\le (\frac 32+3\alpha )n+o(n)$ from Theorem 1.5. We do not know whether this upper bound is asymptotically tight or not for any $1/6\lt \alpha \lt 1/4$ . Note that for any $1/6\lt \alpha \lt 1/4$ ,

\begin{equation*}3/2+3\alpha \gt (\sqrt {\alpha }+1)^2,\end{equation*}

therefore, if $r(B_{\alpha n}, B_n)= (\frac 32+3\alpha )n+o(n)$ holds in this interval, then it means that Conjecture 1.3 proposed by Conlon, Fox, and Wigderson [12] indeed holds in this interval. In particular, we already know that for any $\frac 16\le \alpha \lt \frac{52-16\sqrt{3}}{121}\approx 0.2007$ , Conjecture 1.3 holds from Theorem 1.6.