Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Tight Ramsey bounds for multiple copies of a graph

Matija Bucic (Princeton, IAS)

Location:  Hill Center Room 705
Date & time: Monday, 22 November 2021 at 2:00PM - 3:00PM

Abstract: 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 a long history. Despite this there are very 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|. We obtain 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.

Joint work with B. Sudakov.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.