Ramsey size linear and generalization

Abstract

More than thirty years ago, Erdős, Faudree, Rousseau, and Schelp posed a fundamental question in extremal graph theory: What is the optimal constant $c_k$ such that $r(C_{2k+1},G)\le c_{k}m$ for any graph $G$ with $m$ edges and no isolated vertices? In this paper, we make a significant step towards answering this question by proving that $r(C_{2k+1},G)\le (2+o(1))m+p,$ where $p$ denotes the number of vertices in $G$. Additionally, we extend the work of Goddard and Kleitman and independently Sidorenko, who proved that $r(K_3,G)\le 2m+1$ for any graph $G$ with $m$ edges and no isolated vertices. We generalize their findings to the clique version, establishing that $r(K_r,G)\le c_r{m}^{(r-1)/2}$, and to the multicolor setting, showing that $r_{k+1}(K_3;G)\le c_k{m}^{(k+1)/2}.$

After submitting our paper on January 8, 2026, we just discovered that Stijn Cambie, Andrea Freschi, Patryk Morawski, Kalina Petrova, Alexey Pokrovskiy in https://doi.org/10.48550/arXiv.2601.10238 also proved c_k= 2 for sufficiently large m,