CaltechAUTHORS
  A Caltech Library Service

The Ramsey number of books

Conlon, David (2019) The Ramsey number of books. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170924800

[img] PDF - Submitted Version
See Usage Policy.

161kB

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

Abstract

We show that in every two-colouring of the edges of the complete graph K_N there is a monochromatic K_k which can be extended in at least (1 + o_(k)(1))2^(-k)N ways to a monochromatic K_(k+1). This result is asymptotically best possible, as may be seen by considering a random colouring. Equivalently, defining the book B_n^(k) to be the graph consisting of n copies of K_(k+1) all sharing a common K_k, we show that the Ramsey number r(B_n^(k)) = 2^(k)n + o_(k)(n). In this form, our result answers a question of Erdős, Faudree, Rousseau and Schelp and establishes an asymptotic version of a conjecture of Thomason.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1808.03157arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:Research supported by a Royal Society University Research Fellowship and ERC Starting Grant 676632. This paper was partially written while I was visiting the California Institute of Technology as a Moore Distinguished Scholar and I am extremely grateful for their kind support. I am also much indebted to Jacob Fox, Lisa Sauermann and Yuval Wigderson for pointing out a subtle error in the first version of this paper. Finally, I would like to thank the anonymous reviewers for several helpful remarks which improved the presentation.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
European Research Council (ERC)676632
Gordon and Betty Moore FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20190819-170924800
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-170924800
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98030
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 23:12
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page