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

Andrzej Dudek, Pawel Pralat

Published 2014-05-07, updated 2014-06-11Version 2

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\H{o}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.