The number of subsets of integers with no k-term arithmetic progression

الأصل · EN

Addressing a question of Cameron and Erd s, we show that, for infinitely many values of n, the number of subsets of {1,2,, n} that do not contain a k-term arithmetic progression is at most 2ᵒ⁽ʳᵏ⁽ⁿ⁾⁾, where rₖ(n) is the maximum cardinality of a subset of {1,2,, n} without a k-term arithmetic progression. This bound is optimal up to a constant factor in the exponent. For all values of n, we prove a weaker bound, which is nevertheless sufficient to transfer the current best upper bound on rₖ(n) to the sparse random setting. To achieve these bounds, we establish a new supersaturation result, which roughly states that sets of size Θ(rₖ(n)) contain superlinearly many k-term arithmetic progressions. For integers r and k, Erd s asked whether there is a set of integers S with no (k+1)-term arithmetic progression, but such that any r-coloring of S yields a monochromatic k-term arithmetic progression. Nešetřil and Rödl, and independently Spencer, answered this question affirmatively. We show the following density version: for every k≥ 3 and δ>0, there exists a reasonably dense subset of primes S with no (k+1)-term arithmetic progression, yet every U S of size |U|≥δ|S| contains a k-term arithmetic progression. Our proof uses the hypergraph container method, which has proven to be a very powerful tool in extremal combinatorics. The idea behind the container method is to have a small certificate set to describe a large independent set. We give two further applications in the appendix using this idea.