CaltechAUTHORS
  A Caltech Library Service

The size‐Ramsey number of cubic graphs

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] 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:
URLURL TypeDescription
https://doi.org/10.1112/blms.12682DOIArticle
https://arxiv.org/abs/2110.01897arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
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:
Funding AgencyGrant Number
NSFDMS-2054452
Swiss National Science Foundation (SNSF)200020_197138
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