TY - JOUR

T1 - Tight Ramsey Bounds for Multiple Copies of a Graph

AU - Bucić, Matija

AU - Sudakov, Benny

N1 - Funding Information:
*Research supported in part by NSF grant CCF-1900460. †Research supported in part by SNSF grant 200021_196965.
Publisher Copyright:
© 2023 Matija Bucić and Benny Sudakov.

PY - 2023

Y1 - 2023

N2 - The Ramsey number r(G) of a graph G is the smallest integer n such that any 2 colouring of the edges of a clique on n vertices contains a monochromatic copy of G. Determining the Ramsey number of G is a central problem of Ramsey theory with long and illustrious history. Despite this there are precious few classes of graphs G for which the value of r(G) is known exactly. One such family consists of large vertex disjoint unions of a fixed graph H, we denote such a graph, consisting of n copies of H by nH. This classical result was proved by Burr, Erdős and Spencer in 1975, who showed r(nH) = (2|H| − α(H))n + c, for some c = c(H), provided n is large enough. Since it did not follow from their arguments, Burr, Erdős and Spencer further asked to determine the number of copies we need to take in order to see this long term behaviour and the value of c. More than 30 years ago Burr gave a way of determining c(H), which only applies when the number of copies n is triple exponential in |H|. In this paper we give an essentially tight answer to this very old problem of Burr, Erdős and Spencer by showing that the long term behaviour occurs already when the number of copies is single exponential.

AB - The Ramsey number r(G) of a graph G is the smallest integer n such that any 2 colouring of the edges of a clique on n vertices contains a monochromatic copy of G. Determining the Ramsey number of G is a central problem of Ramsey theory with long and illustrious history. Despite this there are precious few classes of graphs G for which the value of r(G) is known exactly. One such family consists of large vertex disjoint unions of a fixed graph H, we denote such a graph, consisting of n copies of H by nH. This classical result was proved by Burr, Erdős and Spencer in 1975, who showed r(nH) = (2|H| − α(H))n + c, for some c = c(H), provided n is large enough. Since it did not follow from their arguments, Burr, Erdős and Spencer further asked to determine the number of copies we need to take in order to see this long term behaviour and the value of c. More than 30 years ago Burr gave a way of determining c(H), which only applies when the number of copies n is triple exponential in |H|. In this paper we give an essentially tight answer to this very old problem of Burr, Erdős and Spencer by showing that the long term behaviour occurs already when the number of copies is single exponential.

UR - http://www.scopus.com/inward/record.url?scp=85148595185&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85148595185&partnerID=8YFLogxK

U2 - 10.19086/aic.2023.1

DO - 10.19086/aic.2023.1

M3 - Article

AN - SCOPUS:85148595185

SN - 2517-5599

VL - 2023

JO - Advances in Combinatorics

JF - Advances in Combinatorics

M1 - 1

ER -