Browse Teach Curate

Constructing Large 3-Free Sets: Methods and Empirical Bounds

Survey of how large a subset of {1,...,n} can be while avoiding 3-term arithmetic progressions: exact small-n values via intelligent backtracking, upper bounds from Roth-type theorems and linear programming, and lower-bound constructions (base-3, base-5, Kruskal-DeMillo, block, and Behrend sphere methods), with empirical comparisons of when asymptotically better methods actually win and applications to queens domination, matrix multiplication, and communication complexity.

Starscream Text

Finding Large Sets Without Arithmetic Progressions of Length Three: An Empirical View and Survey II

There has been much work on the following question: given n how large can a subset of {1,...,n} be that has no arithmetic progressions of length 3. We call such sets 3-free. Most of the work has been…