2016/05/10 by Balogh, József, Liu, Hong, Sharifzadeh, Maryam
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1605.03172
Addressing a question of Cameron and Erd\Ho 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 2O(rk(n)), where rk(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 rk(n) to the sparse random setting. To achieve these bounds, we establish a new supersaturation result, which roughly states that sets of size Θ(rk(n)) contain superlinearly many k-term arithmetic progressions. For integers r and k, Erd\Ho 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.