Logo
All Random Solved Random Open
SOLVED
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$?

This would imply in particular that in a finite geometry there is always a blocking set which meets every line in $O(1)$ many points.

In [Er81] the condition $\lvert A_i\cap A_j\rvert\leq 1$ for all $i\neq j$ is replaced by every two points in $\{1,\ldots,n\}$ being contained in exactly one $A_i$, that is, $A_1,\ldots,A_m$ is a pairwise balanced block design (and the condition $c<1$ is omitted).

Alon has proved that the answer is no: 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$. (The construction is to take random subsets of the lines of a projective plane.)

The weaker version that Erdős posed in [Er81] remains open, although Alon conjectures the answer there to also be no.