Erdős Problem #272

declared status 'open'. Formalized: yes. Let $N\geq 1$. What is the largest $t$ such that there are $A_1,\ldots,A_t\subseteq \{1,\ldots,N\}$ with $A_i\cap A_j$ a non-empty arithmetic progression for all $i\neq j$? Current best: Simonovits and S\'{o}s [SiSo81] have shown that $t\ll N^2$. If we drop the non-empty requirement then Graham, Simonovits, and S\'{o}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\'{o}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. Prize: no. Tags: additive combinatorics, arithmetic progressions.

Notation is rendered from the stored source. The pinned checkout remains the exact record.