TY - JOUR

T1 - The Number of Subsets of Integers with No k -Term Arithmetic Progression

AU - Balogh, József

AU - Liu, Hong

AU - Sharifzadeh, Maryam

N1 - Funding Information:
This Research was partially supported by NSA [H98230-15-1-0002], NSF [DMS-1500121] and
Publisher Copyright:
© The Author(s) 2016. Published by Oxford University Press. All rights reserved.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - Addressing a question of Cameron and Erdos, 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, Erdos 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 Rodl, 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.

AB - Addressing a question of Cameron and Erdos, 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, Erdos 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 Rodl, 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.

UR - http://www.scopus.com/inward/record.url?scp=85031941422&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031941422&partnerID=8YFLogxK

U2 - 10.1093/imrn/rnw077

DO - 10.1093/imrn/rnw077

M3 - Article

AN - SCOPUS:85031941422

VL - 2017

SP - 6168

EP - 6186

JO - International Mathematics Research Notices

JF - International Mathematics Research Notices

SN - 1073-7928

IS - 20

ER -