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 π.
Keywords
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
Open Access
