Problem #559: Let $\hat{R}(G)$ denote the size Ramsey number, the minimal...

---

Progress

A problem of Beck, and perhaps also Erdős, although I cannot now find a reference in which Erdős himself discusses this problem - it is asked by Beck in [Be83b], a paper which answers a related question of Erdős [720].

Beck [Be83b] proved this when $G$ is a path. Friedman and Pippenger [FrPi87] proved this when $G$ is a tree. Haxell, Kohayakawa, and Luczak [HKL95] proved this when $G$ is a cycle. An alternative proof when $G$ is a cycle (with better constants) was given by Javadi, Khoeini, Omidi, and Pokrovskiy [JKOP19].

This was disproved for $d=3$ by Rödl and Szemerédi [RoSz00], who constructed a graph on $n$ vertices with maximum degree $3$ such that\[\hat{R}(G)\gg n(\log n)^{c}\]for some absolute constant $c>0$. Tikhomirov [Ti22b] has improved this to\[\hat{R}(G)\gg n\exp(c\sqrt{\log n}).\]It is an interesting question how large $\hat{R}(G)$ can be if $G$ has maximum degree $3$. Kohayakawa, Rödl, Schacht, and Szemerédi [KRSS11] proved an upper bound of $\leq n^{5/3+o(1)}$ and Conlon, Nenadov, and Trujić [CNT22] proved $\ll n^{8/5}$. The best known upper bound of $\leq n^{3/2+o(1)}$ is due to Draganić and Petrova [DrPe22].

See also the entry in the graphs problem collection.