Séminaire CAESAR
de combinatoire additive
Séance du 9 juin 2011
(10 heures 30, Jussieu, couloir 15-25, salle 102):
David CONLON
(Cambridge, Grande-Bretagne)
Combinatorial theorems in sparse random sets
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 0 to 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.
Retour à la page d'accueil du
séminaire