Problem #272: Let $N\geq 1$. What is the largest $t$ such that there are...

---

Progress

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\[t\leq \binom{N}{3}+\binom{N}{2}+\binom{N}{1}+1\]and this is best possible.

Szabo [Sz99] proved that the maximal such $t$ is equal to\[\frac{N^2}{2}+O(N^{5/3}(\log N)^3),\]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\[t \geq \binom{N}{2}+\left\lfloor\frac{N-1}{4}\right\rfloor+1.\]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.