Logo
All Random Solved Random Open
SOLVED
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$.

If $G$ has $n$ vertices and maximum degree $d$ then prove that \[\hat{R}(G)\ll_d n.\]

A problem of Beck and Erdős. 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.

Additional thanks to: Zach Hunter