Logo
All Random Solved Random Open
OPEN
Is there some constant $c$ such that for every $n$ there are $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ such that $\lvert A_i\rvert >n^{1/2}-c$ for all $i$, and $\lvert A_i\cap A_j\rvert \leq 1$ for all $i\neq j$, and every pair $1\leq x<y\leq n$ has $\{x,y\}\subseteq A_i$ for some $i$?
A problem of Erdős and Larson [ErLa82].

Shrikhande and Singhi [ShSi85] have proved that the answer is no conditional on the conjecture that the order of every projective plane is a prime power, by proving that every pairwise balanced design on $n$ points in which each block is of size $\geq n^{1/2}-c$ can be embedded in a projective plane of order $n+i$ for some $i\leq c+2$, if $n$ is sufficiently large.

Erdős asks if this is false for constant, for which functions $h(n)$ will the condition $\lvert A_i\rvert \geq n^{1/2}-h(n)$ make the conjecture true?