BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Combinatorial theorems in sparse sets - David Conlon  (Oxford)
DTSTART:20140203T151500Z
DTEND:20140203T160000Z
UID:TALK50594@talks.cam.ac.uk
CONTACT:HoD Secretary\, DPMMS
DESCRIPTION:Szemerédi's regularity lemma is a fundamental tool in extrema
 l combinatorics. However\, the original version is only helpful in studyin
 g dense graphs. In the 1990s\, Kohayakawa and Rödl proved an analogue of 
 Szemerédi's regularity lemma for sparse graphs as part of a general progr
 am toward extending extremal results to sparse graphs. Many of the key app
 lications of Szemerédi's regularity lemma use an associated counting lemm
 a. In order to prove extensions of these results which also apply to spars
 e 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 regularity lemma of Kohayakawa 
 and R\\"odl\, but in different contexts. The first\, which is joint work w
 ith Gowers\, Samotij and Schacht\, deals with the case when the sparse gra
 ph is a subgraph of a random graph\, while the second\, which is joint wor
 k with Fox and Zhao\, deals with the case when the sparse graph is a subgr
 aph of a pseudorandom graph. We use these results to prove sparse extensio
 ns of several well-known combinatorial theorems\, including the removal le
 mmas for graphs and groups\, the Erdős-Stone-Simonovits theorem and Ramse
 y's theorem. In particular\, we show how these methods can be used to give
  a substantially simpler proof of the Green-Tao theorem about primes in ar
 ithmetic progression.
LOCATION:CMS\, MR11
END:VEVENT
END:VCALENDAR