Ramsey Numbers of Books and Quasirandomness
The book graph B^((k))_n consists of n copies of K_(k+1) joined along a common K_k. The Ramsey numbers of B^((k))_n are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed k, thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi's regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom.
Additional Information© 2022 Springer. Received 04 January 2020; Revised 11 November 2020; Published 10 March 2022. We would like to thank Freddie Illingworth for pointing out an error in an earlier draft of this paper. We would also like to thank the anonymous referees for their careful reviews and helpful suggestions. Research supported by ERC Starting Grant 676632 and NSF Award DMS-2054452. Research supported by a Packard Fellowship and by NSF Career Award DMS-1352121. Research supported by NSF GRFP Grant DGE-1656518.
Submitted - 2001.00407.pdf