Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 20, 2022 | Submitted
Journal Article Open

The size‐Ramsey number of cubic graphs

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
Files (490.3 kB)
Name Size Download all
md5:564de593a8c11ebe26ddf915fbc6ebe0
490.3 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 24, 2023