{"id":"arxiv/2603.25453","url":"https://arxiv.org/abs/2603.25453","tags":["math.CO"],"score":0,"title":"Ramsey size linear and generalization","domain":"math.CO","source":"arxiv","authors":["Eng Keat Hng","Meng Ji","Ander Lamaison"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-26","reactions":{}}