The Ramsey number of books

Abstract

We show that in every two-colouring of the edges of the complete graph $K_N$ there is a monochromatic $K_k$ which can be extended in at least $(1+o_k(1))2^{-k}N$ ways to a monochromatic $K_{k+1}$. This result is asymptotically best possible, as may be seen by considering a random colouring. Equivalently, defining the book $B_n^{(k)}$ to be the graph consisting of $n$ copies of $K_{k+1}$ all sharing a common $K_k$, we show that the Ramsey number $r(B_n^{(k)})=2^{k}n+o_k(n)$. In this form, our result answers a question of Erdős, Faudree, Rousseau and Schelp and establishes an asymptotic version of a conjecture of Thomason.

Reformatted for Advances in Combinatorics