Erdős Problem #664

Let \(c<1\) be some constant and \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) be such that \(\lvert A_i\rvert >c\sqrt{n}\) for all \(i\) and \(\lvert A_i\cap A_j\rvert\leq 1\) for all \(i\neq j\). Must there exist some set \(B\) such that \(B\cap A_i\neq \emptyset\) and \(\lvert B\cap A_i\rvert \ll_c 1\) for all \(i\)? The answer is no, proved by Alon: if \(q\) is a large prime power and \(n=m=q^2+q+1\) then there exist \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that \(\lvert A_i\rvert \geq \tfrac{2}{5}\sqrt{n}\) for all \(i\) and \(\lvert A_i\cap A_j\rvert\leq 1\) for all \(i\neq j\), and yet if \(B\) has non-empty intersection with all \(A_i\) then there exists \(A_j\) such that \(\lvert B\cap A_j\rvert \gg \log n\).