Size bounds for three-term-progression-intersecting families
Follow the latest progress by email.
How large can a family of subsets of [n] be if every pairwise intersection contains a nontrivial three-term arithmetic progression? Simonovits and Sós conjectured a maximum of 2^(n−3).
Why it matters and what counts as progress
Why it matters: The restriction combines pairwise intersection with arithmetic structure, beyond the elementary half-density bound.
What counts as progress: A fixed improvement below 2^(n−1), a sharper universal bound toward 2^(n−3), or a family exceeding the conjectured value.
How the problem developed
- 1986 · Conjecture [1]
Miklós Simonovits and Vera T. Sós Chung, Graham, Frankl and Shearer recorded the Simonovits–Sós conjecture that a 3AP-intersecting family of subsets of [n] has size at most 2^(n−3).
Peter Keevash Proved the first bound below the trivial half of all subsets: |F| ≤ (1/2−c)2^n for an absolute c>0. The conjectured 2^(n−3) bound remains open.
AI contribution
A non-trivial bound for 3AP-intersecting families
For an absolute c>0, every family of subsets of [n] whose pairwise intersections contain a nontrivial three-term arithmetic progression has size at most (1/2−c)2^n. Keevash also proves this for 3-uniform hypergraphs with bounded pair-codegree.
Sources
Website timeline
Publication dates and editorial changes.