Published March 2023 | Version Published
Journal Article Open

Off-diagonal book Ramsey numbers

  • 1. ROR icon California Institute of Technology
  • 2. ROR icon Stanford University
  • 3. ROR icon Tel Aviv University

Abstract

The book graph B(k)_n consists of n copies of K_(k+1) joined along a common K_k. In the prequel to this paper, we studied the diagonal Ramsey number r(B(k)_n, B(k)_n. Here we consider the natural off-diagonal variant r(B(k)_cn, B(k)_n for fixed c ∈ (0,1]. In this more general setting, we show that an interesting dichotomy emerges: for very small c, a simple k-partite construction dictates the Ramsey function and all nearly-extremal colourings are close to being k-partite, while, for c bounded away from 0, random colourings of an appropriate density are asymptotically optimal and all nearly-extremal colourings are quasirandom. Our investigations also open up a range of questions about what happens for intermediate values of c.

Copyright and License

© The Author(s), 2023. Published by Cambridge University Press. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.

Acknowledgement

We are grateful to the anonymous referee for helpful comments which improved the presentation of this paper.

Funding

Research supported by NSF Award DMS-2054452.
Research supported by a Packard Fellowship and by NSF Awards DMS-1800053 and DMS-2154169.
Research supported by NSF GRFP Grant DGE-1656518, NSF-BSF Grant 20196, and by ERC Consolidator Grants 863438 and 101044123.

Files

off-diagonal-book-ramsey-numbers.pdf

Files (506.2 kB)

Name Size Download all
md5:7aa1335a7d83468ac1382a3ad15a6599
506.2 kB Preview Download

Additional details

Related works

Is new version of
Discussion Paper: arXiv:2110.14483 (arXiv)

Funding

National Science Foundation
DMS-2054452
David and Lucile Packard Foundation
National Science Foundation
DMS-1800053
National Science Foundation
DMS-2154169
National Science Foundation
DGE-1656518
United States-Israel Binational Science Foundation
20196
European Research Council
863438
European Research Council
101044123

Dates

Accepted
2022-12-07
Available
2023-01-09
Published online

Caltech Custom Metadata

Caltech groups
Division of Physics, Mathematics and Astronomy (PMA)
Publication Status
Published