Rödl–Szemerédi conjecture on superlinear size-Ramsey numbers

Let $d\geq 3$. A sequence of graphs $(G_n)$ is said to have maximum degree at most $d$ when every $G_n$ has $n$ vertices and maximum degree at most $d$. The size-Ramsey number $\hat{r}(G_n)$ is the minimum number of edges in a graph whose every edge-colouring contains a monochromatic copy of $G_n$.

Rödl–Szemerédi conjecture. For every $d\geq 3$ there exist $\varepsilon>0$ and a sequence of graphs $(G_n)$ on $n$ vertices and maximum degree at most $d$ such that

$$\hat{r}(G_n)=\Omega(n^{1+\varepsilon}).$$

This conjecture asks whether bounded-degree graphs can have size-Ramsey numbers that are genuinely superlinear in their order. The paper identifies it as a central open question in the area; the conjecture is attributed to Rödl and Szemerédi.