Published July 20, 2022
| Version Submitted
Journal Article
Open
The size‐Ramsey number of cubic graphs
Creators
-
1.
California Institute of Technology
-
2.
Google (Switzerland)
-
3.
ETH Zurich
Abstract
We show that the size-Ramsey number of any cubic graph with n vertices is O(n^(8/5)), improving a bound of n^(5/3+o(1)) due to Kohayakawa, Rödl, Schacht, and Szemerédi. The heart of the argument is to show that there is a constant C such that a random graph with Cn vertices where every edge is chosen independently with probability p⩾C_n^(−2/5) is with high probability Ramsey for any cubic graph with n vertices. This latter result is best possible up to the constant.
Additional Information
© 2022 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. Version of Record online: 26 May 2022; Manuscript accepted: 22 March 2022; Manuscript revised: 02 March 2022; Manuscript received: 06 October 2021. This research has been supported by NSF Award DMS-2054452 and by the Swiss National Science Foundation under Grant Number: 200020_197138.Attached Files
Submitted - 2110.01897.pdf
Files
2110.01897.pdf
Additional details
Identifiers
- Eprint ID
- 115674
- Resolver ID
- CaltechAUTHORS:20220718-901273500
Related works
- Describes
- https://arxiv.org/abs/2110.01897 (URL)
Funding
- NSF
- DMS-2054452
- Swiss National Science Foundation (SNSF)
- 200020_197138
Dates
- Created
-
2022-07-20Created from EPrint's datestamp field
- Updated
-
2022-07-20Created from EPrint's last_modified field
Caltech Custom Metadata
- Caltech groups
- Mathematics Department