Conlon, David and Nenadov, Rajko and Trujić, Miloš (2022) The size‐Ramsey number of cubic graphs. Bulletin of the London Mathematical Society . ISSN 0024-6093. doi:10.1112/blms.12682. (In Press) https://resolver.caltech.edu/CaltechAUTHORS:20220718-901273500
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Submitted Version
See Usage Policy. 490kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220718-901273500
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.
| Item Type: | Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| 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. | |||||||||
| Funders: |
| |||||||||
| DOI: | 10.1112/blms.12682 | |||||||||
| Record Number: | CaltechAUTHORS:20220718-901273500 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20220718-901273500 | |||||||||
| Official Citation: | Conlon, D., Nenadov, R. and Trujić, M. (2022), The size-Ramsey number of cubic graphs. Bull. London Math. Soc. https://doi.org/10.1112/blms.12682 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 115674 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 20 Jul 2022 17:29 | |||||||||
| Last Modified: | 20 Jul 2022 17:29 |
Repository Staff Only: item control page
