The reviewed record of science sign in
Pith

arxiv: 2212.02455 · v1 · pith:CF7VZNVJ · submitted 2022-12-05 · math.CO

Ramsey numbers for multiple copies of sparse graphs

Reviewed by Pithpith:CF7VZNVJopen to challenge →

classification math.CO
keywords copiesnumbersramseybehaviourboundedboundsburrdegree
0
0 comments X
read the original abstract

For a graph $H$ and an integer $n$, we let $nH$ denote the disjoint union of $n$ copies of $H$. In 1975, Burr, Erd\H{o}s, and Spencer initiated the study of Ramsey numbers for $nH$, one of few instances for which Ramsey numbers are now known precisely. They showed that there is a constant $c = c(H)$ such that $r(nH) = (2|H| - \alpha(H))n + c$, provided $n$ is sufficiently large. Subsequently, Burr gave an implicit way of computing $c$ and noted that this long term behaviour occurs when $n$ is triply exponential in $|H|$. Very recently, Buci\'{c} and Sudakov revived the problem and established an essentially tight bound on $n$ by showing $r(nH)$ follows this behaviour already when the number of copies is just a single exponential. We provide significantly stronger bounds on $n$ in case $H$ is a sparse graph, most notably of bounded maximum degree. These are relatable to the current state of the art bounds on $r(H)$ and (in a way) tight. Our methods rely on a beautiful classic proof of Graham, R\"{o}dl, and Ruci\'{n}ski, with the emphasis on developing an efficient absorbing method for bounded degree graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.