On a conjecture of Conlon, Fox and Wigderson

For graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest positive integer $N$ such that any red/blue edge coloring 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<\alpha <1$, the random lower bound $r(B_{\lceil \alpha n\rceil },B_n)\ge (\sqrt{\alpha }+1{)}^{2}n+o(n)$ is not tight. In other words, there exists some constant $\beta >(\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 <1\mathrm{/}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\mathrm{/}4\le \alpha \le 1$. Moreover, we show that for any $1\mathrm{/}6\le \alpha \le 1\mathrm{/}4$ and large $n$, $r(B_{\lceil \alpha n\rceil },B_n)\le (\frac{3}{2}+3\alpha )n+o(n)$, where the inequality is asymptotically tight when $\alpha =1\mathrm{/}6$ or $1\mathrm{/}4$. We also give a lower bound of $r(B_{\lceil \alpha n\rceil },B_n)$ for $1\mathrm{/}6\le \alpha <\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.