Arithmetic progressions of length three in subsets of a random set

Abstract

For integers 1 ≤ M ≤ n, let R(n, M) denote the uniform probability space which consists of all the M-element subsets of [n] = {0, 1, ..., n-1}. It is shown that for every α > 0 there exists a constant C such that if M = M(n) ≥ C p n then, with probability tending to 1 as n → 1, the random set R ∈ R(n, M) has the property that any subset of R with at least α|R| elements contains a 3-term arithmetic progression. In particular, this result implies that for every α > 0 there exist `sparse' sets S ⊆ [n] with the property that every subset of S with at least α|S| elements contains an arithmetic progression of length three.