Small subsets without $k$-term arithmetic progressions

Abstract

Szemerédi's theorem implies that there are $2^{o(n)}$ subsets of $[n]$ which do not contain a $k$-term arithmetic progression. A sparse analogue of this statement was obtained by Balogh, Morris, and Samotij, using the hypergraph container method: For any $\beta >0$ there exists $C>0$, such that if $m\ge C{n}^{1-1/(k-1)}$ then there are at most ${\beta }^m\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ $m$-element subsets of $\{1,\dots ,n\}$ without a $k$-term arithmetic progression. We give a short, inductive proof of this result. Consequently, this provides a short proof of the Szemerédi's theorem in random subsets of integers.

6 pages. Companion note to the paper "A new proof of the KLR conjecture" [arXiv:2108.05687]