Book Ramsey numbers via algebraic constructions

Abstract

Let $B_n$ denote the book graph consisting of $n$ triangles sharing a common edge. Few exact values of $R(B_n,B_n)$ have been obtained since Rousseau and Sheehan (1978) proved, using Paley graphs, $R(B_n,B_n)=4n+2$ whenever $4n+1$ is a prime power. In this paper, we obtain $R(B_n,B_n)=4n+1$ for infinitely many $n$ by constructing new families of strongly regular graphs. Moreover, we prove that $R(B_{n-2},B_n)\le 4n-3$ for every $n\ge 3$ with $n\ne 6$, removing the original condition $n\equiv 2(\mathrm{mod}3)$ due to Rousseau and Sheehan. In particular, if there exists a symmetric Hadamard matrix of order $2n-2$ with all diagonal entries equal to $1$, then $R(B_{n-2},B_n)=4n-3$. As an application, we show that this equality holds for every $n=2^{2\ell -1}+1$ with $\ell \ge 1$.

12 pages