Erdős Problem #734

declared status 'open'. Formalized: no. 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$. Current best: Erd\H{o}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$. Prize: no. Tags: combinatorics.

Notation is rendered from the stored source. The pinned checkout remains the exact record.