Combinatorial theorems in sparse random sets
Add to your list(s)
Download to your calendar using vCal
 Tim Gowers (Cambridge)
 Thursday 04 December 2008, 14:3015: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 deltaX 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/(k1)} (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 finitedimensional HahnBanach theorem. This is joint work with David Conlon.
This talk is part of the Combinatorics Seminar series.
This talk is included in these lists:
Note that exdirectory lists are not shown.
