2021/10/27 by Conlon, David, Fox, Jacob, Wigderson, Yuval
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2110.14483
The book graph Bn(k) consists of n copies of Kk+1 joined along a common Kk. In the prequel to this paper, we studied the diagonal Ramsey number r(Bn(k), Bn(k)). Here we consider the natural off-diagonal variant r(Bcn(k), Bn(k)) 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 colorings are close to being k-partite, while, for c bounded away from 0, random colorings of an appropriate density are asymptotically optimal and all nearly-extremal colorings are quasirandom. Our investigations also open up a range of questions about what happens for intermediate values of c.