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:Special DPMMS Colloquium
SUMMARY:Combinatorial theorems in sparse sets - David Conl
on (Oxford)
DTSTART;TZID=Europe/London:20140203T151500
DTEND;TZID=Europe/London:20140203T160000
UID:TALK50594AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/50594
DESCRIPTION:Szemerédi's regularity lemma is a fundamental tool
in extremal combinatorics. However\, the original
version is only helpful in studying dense graphs.
In the 1990s\, Kohayakawa and Rödl proved an anal
ogue of Szemerédi's regularity lemma for sparse gr
aphs as part of a general program toward extending
extremal results to sparse graphs. Many of the ke
y applications of Szemerédi's regularity lemma use
an associated counting lemma. In order to prove e
xtensions of these results which also apply to spa
rse graphs\, it remained a well-known open problem
to prove a counting lemma in sparse graphs.\n\nIn
this talk\, we discuss two different counting lem
mas\, each of which complements the sparse regular
ity lemma of Kohayakawa and R\\"odl\, but in diffe
rent contexts. The first\, which is joint work wit
h Gowers\, Samotij and Schacht\, deals with the ca
se when the sparse graph is a subgraph of a random
graph\, while the second\, which is joint work wi
th Fox and Zhao\, deals with the case when the spa
rse graph is a subgraph of a pseudorandom graph. W
e use these results to prove sparse extensions of
several well-known combinatorial theorems\, includ
ing the removal lemmas for graphs and groups\, the
Erdős-Stone-Simonovits theorem and Ramsey's theor
em. In particular\, we show how these methods can
be used to give a substantially simpler proof of t
he Green-Tao theorem about primes in arithmetic pr
ogression.
LOCATION:CMS\, MR11
CONTACT:HoD Secretary\, DPMMS
END:VEVENT
END:VCALENDAR