***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Matija Bucic (Princeton)

Thursday 28th October, 3:00 in Fine Hall 224.

Title:  Tight Ramsey bounds for multiple copies of a graph

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.


		----------------------------------

Next week: TBA

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)