Combinatorial Theorems in Random Sets

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I
Topic:Combinatorial Theorems in Random Sets
Speaker:David Conlon
Affiliation:University of Cambridge
Date:Monday, November 22
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/conlon

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.