CaltechAUTHORS
  A Caltech Library Service

Ramsey Numbers of Books and Quasirandomness

Conlon, David and Fox, Jacob and Wigderson, Yuval (2022) Ramsey Numbers of Books and Quasirandomness. Combinatorica . ISSN 0209-9683. doi:10.1007/s00493-021-4409-9. (In Press) https://resolver.caltech.edu/CaltechAUTHORS:20200914-140122041

[img] PDF - Submitted Version
See Usage Policy.

433kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200914-140122041

Abstract

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:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/s00493-021-4409-9DOIArticle
https://rdcu.be/cJzSaPublisherFree ReadCube access
https://arxiv.org/abs/2001.00407arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Wigderson, Yuval0000-0001-5909-9250
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.
Funders:
Funding AgencyGrant Number
European Research Council (ERC)676632
NSFDMS-2054452
David and Lucile Packard FoundationUNSPECIFIED
NSFDMS-1352121
NSF Graduate Research FellowshipDGE-1656518
Classification Code:Mathematics Subject Classification (2010): 05C55; 05D10
DOI:10.1007/s00493-021-4409-9
Record Number:CaltechAUTHORS:20200914-140122041
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200914-140122041
Official Citation:Conlon, D., Fox, J. & Wigderson, Y. Ramsey Numbers of Books and Quasirandomness. Combinatorica (2022). https://doi.org/10.1007/s00493-021-4409-9
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105381
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:14 Sep 2020 21:47
Last Modified:22 Mar 2022 19:02

Repository Staff Only: item control page