COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |
University of Cambridge > Talks.cam > Special DPMMS Colloquium > Combinatorial theorems in sparse sets
Combinatorial theorems in sparse setsAdd to your list(s) Download to your calendar using vCal
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. |
Other listsViolence Research Center Design and use of chemical tools to modulate gene expression in cancer cells based on the targeting of DNA methyltransferase Peterhouse Theory Group CU Caving Club talks Spanish Researchers in the United Kingdom (SRUK)Other talksCambridge-Lausanne Workshop 2018 - Day 2 The Beginning of Our Universe and what we don't know about Physics Bringing Personality Theory Back to Life: On Persons-in-Context, Idiographic Strategies, and Lazarus Art speak Respiratory Problems Child Kingship from a Comparative Perspective: Boy Kings in England, Scotland, France, and Germany, 1050-1250 Migration in Science Unbiased Estimation of the Eigenvalues of Large Implicit Matrices Single Cell Seminars (August) Retinal mechanisms of non-image-forming vision Prof Kate Jones (UCL): Biodiversity & Conservation |