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

Kohayakawa, Yoshiharu; Łuczak, Tomasz; Rödl, Vojtěch

Acta Arith. 75, No. 2, 133-163 (1996).

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.

Reviewer: R.Vohra (Columbus/Ohio)

MSC:

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

Keywords:

three term arithmetic progression; Szemeredi regularity lemma