Off-diagonal book Ramsey numbers

Abstract

The book graph B(k)_n consists of n copies of K_(k+1) joined along a common K_k. In the prequel to this paper, we studied the diagonal Ramsey number r(B(k)_n, B(k)_n. Here we consider the natural off-diagonal variant r(B(k)_cn, B(k)_n for fixed c ∈ (0,1]. In this more general setting, we show that an interesting dichotomy emerges: for very small c, a simple k-partite construction dictates the Ramsey function and all nearly-extremal colourings are close to being k-partite, while, for c bounded away from 0, random colourings of an appropriate density are asymptotically optimal and all nearly-extremal colourings are quasirandom. Our investigations also open up a range of questions about what happens for intermediate values of c.

Files

Additional details