Problem 665

Erdős Problem #665: declared status 'open'. Formalized: no. 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$? Current best: 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 (see [723]), 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. Prize: no. Tags: combinatorics.