CONNECT

# EVENT

Image Picker for Section 0
Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel

â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹â€‹

 Speaker: Matija Bucic (Princeton University and Institute for Advanced Study) 23 Speaker: Matija Bucic (Princeton University and Institute for Advanced Study) 3/10/2022 6:00:00 PM 3/10/2022 7:00:00 PM GP0|#76dcda40-cab3-49f1-997a-050403489abd;L0|#076dcda40-cab3-49f1-997a-050403489abd|Seminar;GTSet|#40f43609-b3a6-498e-b810-f62732269299;GPP|#7ae17a5c-653c-4d0b-96a7-3b708b59814d;GP0|#ad970a66-03c4-4487-8932-f6d1c08a065c;L0|#0ad970a66-03c4-4487-8932-f6d1c08a065c|Natural Sciences;GTSet|#40f43609-b3a6-498e-b810-f62732269299;GPP|#0966b27d-0d92-4427-a0f9-4bff115e8219 Seminar

Title: Tight Ramsey bounds for multiple copies of a graph

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.â€‹â€‹â€‹

Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel
Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel
Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel
Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel
Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel
Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel
Original
50%
66%
100%
Fixed Portrait 1
Fixed Portrait 2
Cancel