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
![]() |
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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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: |
| ||||||||||||
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