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 > Combinatorics Seminar > Combinatorial theorems in sparse random sets

## Combinatorial theorems in sparse random setsAdd to your list(s) Download to your calendar using vCal - Tim Gowers (Cambridge)
- Thursday 04 December 2008, 14:30-15:30
- MR12.
If you have a question about this talk, please contact Andrew Thomason. 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 progression of length k. Suppose that X is a random subset of {1,2,...,n} with each element chosen independently with probability p. For what values of p is there a high probability that X is (delta,k)-Szemer’edi? There 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 with them all. A key tool in the proof is the finite-dimensional Hahn-Banach theorem. This is joint work with David Conlon. This talk is part of the Combinatorics Seminar series. ## This talk is included in these lists:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- Combinatorics Seminar
- DPMMS Lists
- DPMMS Pure Maths Seminar
- DPMMS info aggregator
- DPMMS lists
- Hanchen DaDaDash
- Interested Talks
- MR12
- School of Physical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsFilm screening - Salaam Bombay! Trinity Mathematical Society Cambridge Immunology## Other talksPlastics in the Ocean: Challenges and Solutions Deep & Heavy: Using machine learning for boosted resonance tagging and beyond Changing understandings of the human fetus over five decades of legal abortion Transcription by influenza virus RNA polymerase: molecular mechanisms, cellular aspects and inhibition Drugs and Alcohol Constraint Analysis and Optimization in Medicine Development and Supply |