On bounded degree graphs with large size-Ramsey numbers

Abstract

The size-Ramsey number $\hat{r}(G^{\prime })$ of a graph $G^{\prime }$ is defined as the smallest integer $m$ so that there exists a graph $G$ with $m$ edges such that every $2$-coloring of the edges of $G$ contains a monochromatic copy of $G^{\prime }$. Answering a question of Beck, Rodl and Szemeredi showed that for every $n\ge 1$ there exists a graph $G^{\prime }$ on $n$ vertices each of degree at most three, with the size-Ramsey number at least $cn{\log }^{\frac{1}{60}}n$ for a universal constant $c>0$. In this note we show that a modification of Rodl and Szemeredi's construction leads to a bound $\hat{r}(G^{\prime })\ge cn\exp (c\sqrt{\log n})$.

revised version, accepted in Combinatorica