Small subsets without $k$-term arithmetic progressions

2021 
Szemeredi'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 Cn^{1 - 1/(k-1)}$ then there are at most $\beta^m \binom{n}{m}$ $m$-element subsets of $\{1, \ldots, n\}$ without a $k$-term arithmetic progression. We give a short, inductive proof of this result. Consequently, this provides a short proof of the Szemeredi's theorem in random subsets of integers.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    8
    References
    2
    Citations
    NaN
    KQI
    []