Problem Statement
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$.
Categories:
Combinatorics
Progress
$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$.
Source: erdosproblems.com/734 | Last verified: January 16, 2026