Off-diagonal book Ramsey numbers

Conlon D, Fox J, Wigderson Y. 2023. Off-diagonal book Ramsey numbers. Combinatorics, Probability and Computing. 32(3), 516–545.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Conlon, David; Fox, Jacob; Wigderson, YuvalISTA
Abstract
The book graph 𝐡(π‘˜) 𝑛 consists of 𝑛 copies of πΎπ‘˜+1 joined along a common πΎπ‘˜. In the prequel to this paper, we studied the diagonal Ramsey number π‘Ÿβ‘(𝐡(π‘˜) 𝑛,𝐡(π‘˜) 𝑛). Here we consider the natural off-diagonal variant π‘Ÿβ‘(𝐡(π‘˜) 𝑐⁒𝑛,𝐡(π‘˜) 𝑛) for fixed 𝑐 ∈(0,1]. In this more general setting, we show that an interesting dichotomy emerges: for very small 𝑐, a simple π‘˜-partite construction dictates the Ramsey function and all nearly-extremal colourings are close to being π‘˜-partite, while, for 𝑐 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 𝑐.
Mathematics Subject Classification
Publishing Year
Date Published
2023-05-01
Journal Title
Combinatorics, Probability and Computing
Publisher
Cambridge University Press
Volume
32
Issue
3
Page
516-545
ISSN
eISSN
IST-REx-ID

Cite this

Conlon D, Fox J, Wigderson Y. Off-diagonal book Ramsey numbers. Combinatorics, Probability and Computing. 2023;32(3):516-545. doi:10.1017/s0963548322000360
Conlon, D., Fox, J., & Wigderson, Y. (2023). Off-diagonal book Ramsey numbers. Combinatorics, Probability and Computing. Cambridge University Press. https://doi.org/10.1017/s0963548322000360
Conlon, David, Jacob Fox, and Yuval Wigderson. β€œOff-Diagonal Book Ramsey Numbers.” Combinatorics, Probability and Computing. Cambridge University Press, 2023. https://doi.org/10.1017/s0963548322000360.
D. Conlon, J. Fox, and Y. Wigderson, β€œOff-diagonal book Ramsey numbers,” Combinatorics, Probability and Computing, vol. 32, no. 3. Cambridge University Press, pp. 516–545, 2023.
Conlon D, Fox J, Wigderson Y. 2023. Off-diagonal book Ramsey numbers. Combinatorics, Probability and Computing. 32(3), 516–545.
Conlon, David, et al. β€œOff-Diagonal Book Ramsey Numbers.” Combinatorics, Probability and Computing, vol. 32, no. 3, Cambridge University Press, 2023, pp. 516–45, doi:10.1017/s0963548322000360.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Metadata Export

Sources

arXiv 2110.14483

Search this title in

Google Scholar