Computer Science/Discrete Mathematics Seminar I

The famous theorem of Szemerédi says that for any natural number k and any a > 0 there exists n such that if N >= n then any subset A of the set [N] ={1,2,...,N} of size |A| >= a N contains an arithmetic progression of length k. We consider the question of when such a theorem holds in a random set. More precisely, we say that a set X is (a, k)-Szemerédi if every subset Y of X that contains at least a|X| elements contains an arithmetic progression of length k. Let [N]_p be the random set formed by taking each element of [N] independently with probability p. We prove that there is a threshold at about p = N^{-1/(k-1)} where the probability that [ N]_p is (a, k)-Szemerédi changes from being almost surely 0 to almost surely 1. There are many other similar problems within combinatorics. For example, Turán's theorem and Ramsey's theorem may be relativised, but until now the precise probability thresholds were not known. Our method seems to apply to all such questions, in each case giving the correct threshold. This is joint work with Tim Gowers.