Answers are grounded in this paper and cite their sources.
For a graph and an integer , we let denote the disjoint union of copies of . In 1975, Burr, Erdős and Spencer initiated the study of Ramsey numbers for , one of few instances for which Ramsey numbers are now known precisely. They showed that there is a constant such that , provided is sufficiently large. Subsequently, Burr gave an implicit way of computing and noted that this long‐term behaviour occurs when is triply exponential in . Very recently, Bucić and Sudakov revived the problem and established an essentially tight bound on by showing follows this behaviour already when the number of copies is just a single exponential. We provide significantly stronger bounds on in case is a sparse graph, most notably of bounded maximum degree. These are relatable to the current state‐of‐the‐art bounds on and (in a way) tight. Our methods rely on a beautiful classic proof of Graham, Rödl and Ruciński, with an emphasis on developing an efficient absorbing method for bounded degree graphs.
No takes yet. Share an insight, caveat, or question.
Sulser et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: