The size-Ramsey number of cubic graphs

2021/10/05 by David Conlon, Conlon, David, Rajko Nenadov +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2110.01897

openalex publication_date 2021/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 C n 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.

Cited by

• Size-Ramsey numbers of tight paths
• Combinatorial theorems relative to sparse sets

Related

• Ramsey graphs induce subgraphs of many different sizes
• Ramsey graphs induce subgraphs of quadratically many sizes
• Three early problems on size Ramsey numbers
• On bounded degree graphs with large size-Ramsey numbers
• Ramsey numbers and the size of graphs