Combinatorial theorems in sparse sets

Add to your list(s) Download to your calendar using vCal

• David Conlon (Oxford)
• Monday 03 February 2014, 15:15-16:00
• CMS, MR11.

If you have a question about this talk, please contact HoD Secretary, DPMMS.

This talk has been canceled/deleted

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 analogue of Szemerédi’s regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi’s regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.

In this talk, we discuss two different counting lemmas, each of which complements the sparse regularity lemma of Kohayakawa and R\”odl, but in different contexts. The first, which is joint work with Gowers, Samotij and Schacht, deals with the case when the sparse graph is a subgraph of a random graph, while the second, which is joint work with Fox and Zhao, deals with the case when the sparse graph is a subgraph of a pseudorandom graph. We use these results to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdős-Stone-Simonovits theorem and Ramsey’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 arithmetic progression.

This talk is part of the Special DPMMS Colloquium series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.