Erdős #272 · additive combinatorics / arithmetic progressions

Simonovits and Sós [SiSo81] have shown that $t\ll N^2$.

Erdős and Graham asked whether the maximal $t$ is achieved when we take the $A_i$ to be all arithmetic progressions in $\{1,\ldots,N\}$ containing some fixed element, 'presumably the integer $\lfloor N/2\rfloor$'. This was disproved by Simonovits and Sós [SiSo81], who observed that taking all sets containing at most $3$ elements, containing some fixed element, produces $\binom{N}{2}+1$ many such sets, which is asymptotically greater than the number of arithmetic progressions containing a fixed element, which is $\sim \frac{\pi^2}{24}N^2$.

If we drop the non-empty requirement then Graham, Simonovits, and Sós [GSS80] have shown that

and this is best possible.

Szabo [Sz99] proved that the maximal such $t$ is equal to

resolving the asymptotic question. On the other hand, Szabo showed that the conjecture of Simonovits and Sós that $\binom{n}{2}+1$ is best possible is false, giving a construction which yields

Szabo conjectures that the asymptotic $t=\binom{N}{2}+O(N)$ holds, and that in any extremal example there is an integer contained in all sets.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.