An alternative proof of the linearity of the size-Ramsey number of paths

Abstract

The size Ramsey number $\hat{r}(F)$ of a graph $F$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any colouring of the edges of $G$ with two colours yields a monochromatic copy of $F$. In 1983, Beck provided a beautiful argument that shows that $\hat{r}(P_n)$ is linear, solving a problem of Erdős. In this short note, we provide an alternative but elementary proof of this fact that actually gives a better bound, namely, $\hat{r}(P_n)<137n$ for $n$ sufficiently large.

to be published by Combinatorics, Probability and Computing

Cited by in corpus (8)

• Path Ramsey number for random graphs
• The size-Ramsey number of powers of bounded degree trees
• On the size-Ramsey number of grid graphs
• Size-Ramsey numbers of powers of hypergraph trees and long subdivisions
• The multicolour size-Ramsey number of powers of paths
• Large monochromatic components in expansive hypergraphs
• Monochromatic loose paths in multicolored $k$-uniform cliques
• Multicolor Size-Ramsey Number of Cycles