OPEN
This is open, and cannot be resolved with a finite computation.
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 (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.
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?
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #665, https://www.erdosproblems.com/665, accessed 2026-01-16
