A Caltech Library Service

Ramsey numbers of books and quasirandomness

Conlon, David and Fox, Jacob and Wigderson, Yuval (2020) Ramsey numbers of books and quasirandomness. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:Research supported in part by ERC Starting Grant 676632. Research supported by a Packard Fellowship and by NSF Career Award DMS-1352121. Research supported by NSF GRFP Grant DGE-1656518. We would like to thank Freddie Illingworth for bringing to our attention an error in an earlier draft of this paper.
Funding AgencyGrant Number
European Research Council (ERC)676632
David and Lucile Packard FoundationUNSPECIFIED
NSF Graduate Research FellowshipDGE-1656518
Record Number:CaltechAUTHORS:20200914-140122041
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105381
Deposited By: Tony Diaz
Deposited On:14 Sep 2020 21:47
Last Modified:14 Sep 2020 21:47

Repository Staff Only: item control page