We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Ramsey numbers for multiple copies of sparse graphs.
- Authors
Sulser, Aurelio; Trujić, Miloš
- 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ő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∣−α(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ć 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ödl and Ruciński, with an emphasis on developing an efficient absorbing method for bounded degree graphs.
- Subjects
RAMSEY numbers; SPARSE graphs; RAMSEY theory; NUMBER theory
- Publication
Journal of Graph Theory, 2024, Vol 106, Issue 4, p843
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.23100