OPEN
This is open, and cannot be resolved with a finite computation.
Find, for all large $n$, a non-trivial pairwise balanced block design $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ such that, for all $t$, there are $O(n^{1/2})$ many $i$ such that $\lvert A_i\rvert=t$.
$A_1,\ldots,A_m$ is a pairwise balanced block design if every pair in $\{1,\ldots,n\}$ is contained in exactly one of the $A_i$.
Erdős
[Er81] writes 'this will be probably not be very difficult to prove but so far I was not successful'.
Erdős and de Bruijn
[dBEr48] proved that if $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ is a pairwise balanced block design then $m\geq n$, and this implies there must be some $t$ such that there are $\gg n^{1/2}$ many $t$ with $\lvert A_i\rvert=t$.
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 #734, https://www.erdosproblems.com/734, accessed 2026-01-16
