BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Combinatorial theorems in sparse random sets - Tim
Gowers (Cambridge)
DTSTART;TZID=Europe/London:20081204T143000
DTEND;TZID=Europe/London:20081204T153000
UID:TALK13443AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/13443
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 arithmetic progressi
on of length k. Suppose that X is a random subset
of {1\,2\,...\,n} with each element chosen indepen
dently with probability p. For what values of p is
there a high probability that X is (delta\,k)-Sze
mer'edi?\n\nThere is a trivial lower bound of cn^{
-1/(k-1)} (since at this probability there will be
many fewer progressions than there are points in
the set). We match this to within a constant by a
new upper bound. There are many other conjectures
and partial results of this kind in the literature
: our method is very general and seems to deal wit
h them all. A key tool in the proof is the finite-
dimensional Hahn-Banach theorem. This is joint wor
k with David Conlon.\n
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR