Published August 20, 2019
| Submitted
Report
Open
The Ramsey number of books
- Creators
- Conlon, David
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.
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.Attached Files
Submitted - 1808.03157.pdf
Files
1808.03157.pdf
Files
(161.2 kB)
Name | Size | Download all |
---|---|---|
md5:ce3ffc4ad6f237cdaa59d7cdd662ddfd
|
161.2 kB | Preview Download |
Additional details
- Eprint ID
- 98030
- Resolver ID
- CaltechAUTHORS:20190819-170924800
- Royal Society
- European Research Council (ERC)
- 676632
- Gordon and Betty Moore Foundation
- Created
-
2019-08-20Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field