BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Combinatorial theorems in sparse random sets - Tim Gowers (Cambrid
 ge)
DTSTART:20081204T143000Z
DTEND:20081204T153000Z
UID:TALK13443@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:Let us call a set X of integers (delta\,k)-Szemer'edi if every
  subset Y of X that contains at least delta|X| elements contains an arithm
 etic progression of length k. Suppose that X is a random subset of {1\,2\,
 ...\,n} with each element chosen independently with probability p. For wha
 t values of p is there a high probability that X is (delta\,k)-Szemer'edi?
 \n\nThere is a trivial lower bound of cn^{-1/(k-1)} (since at this probabi
 lity there will be many fewer progressions than there are points in the se
 t). We match this to within a constant by a new upper bound. There are man
 y other conjectures and partial results of this kind in the literature: ou
 r method is very general and seems to deal with them all. A key tool in th
 e proof is the finite-dimensional Hahn-Banach theorem. This is joint work 
 with David Conlon.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR