Arithmetic progressions of length three in subsets of a random set. (English) Zbl 0858.11009

From among the set of all subsets of size \(m\) of the integers \(\{1,2, \dots, n\}\) select one at random. Call the selected set \(A\). Given a subset \(R\) of \(\{1,2, \dots, n\}\) and a positive number \(f<1\), if \(|A|\geq f|R|\), how likely is it that \(A\) contains a three term arithmetic progression? In this paper the authors show that for every positive \(f<1\), if \(m\) is sufficiently large (at least as large as the square root of \(n)\), then \(A\) contains a three term arithmetic progression with high probability. The lower bound for \(m\) is best possible. The proof is rather long, relying on the Szemerédi regularity lemma.
The problem is motivated by the celebrated problem of Erdös and Turán on whether every sufficiently large subset of the integers \(\{1,2, \dots, n\}\) contains a \(k\)-term arithmetic progression.


11B25 Arithmetic progressions
05D99 Extremal combinatorics
11B05 Density, gaps, topology
11K99 Probabilistic theory: distribution modulo \(1\); metric theory of algorithms
Full Text: DOI EuDML