Construct pairwise balanced designs with $O(\sqrt{n})$ blocks of every size (Erdős #734)
Statement
A collection $A_1,\ldots,A_m\subseteq\{1,\ldots,n\}$ is a pairwise balanced block design if every pair of distinct elements of $\{1,\ldots,n\}$ is contained in exactly one $A_i$. Find, for all large $n$, a non-trivial pairwise balanced block design on $\{1,\ldots,n\}$ such that, for every $t$, the number of indices $i$ with $\lvert A_i\rvert = t$ is $O(n^{1/2})$. (Non-trivial excludes the design consisting of the single block $\{1,\ldots,n\}$; the implied constant must be uniform in $n$ and $t$.)
Acceptance. FULLY RESOLVES: an explicit construction scheme, with complete proof, producing for every sufficiently large $n$ a non-trivial pairwise balanced design on $\{1,\ldots,n\}$ in which every block size occurs $O(n^{1/2})$ times (explicit constant stated); OR a proof that no such designs exist for infinitely many $n$ (refuting Erdős's expectation). Machine-checkable proof preferred, else full written proof. ADVANCES: such a construction proved for an infinite family of $n$ (e.g. $n$ of a special arithmetic or prime-power-derived form); a construction achieving $O(n^{1/2+\epsilon})$ or $O(n^{1/2}\log n)$ multiplicities for all large $n$, with proof; a sharpened unconditional lower bound improving the $\gg n^{1/2}$ multiplicity obstruction stated in the background; or explicit verified designs meeting the $O(\sqrt{n})$ target (stated constant) for every $n$ in a substantial contiguous range, delivered as data files plus an independent checker program that verifies the pair-cover and per-size counts. Deliver the construction + proof, or the design files + checker code + the verified range.
Background
A problem of Erdős [Er81, p.35], who wrote that it 'will probably not be very difficult to prove but so far I was not successful'; listed as open on erdosproblems.com/734 (fetched 2026-07-13, status 'open'). The benchmark designs all fail badly: the all-pairs design has $\binom{n}{2}$ blocks of size $2$; a projective plane of order $q$ has $n=q^2+q+1$ blocks all of the same size $q+1$; a near-pencil has $n-1$ blocks of size $2$. The $O(\sqrt{n})$ target is optimal up to the constant: de Bruijn and Erdős [dBEr48] proved every non-trivial pairwise balanced design has $m\geq n$ blocks, and (as noted on the problem page) this forces some size $t$ to occur $\gg n^{1/2}$ times. So the task is to spread the $\geq n$ blocks over $\gg\sqrt{n}$ distinct sizes with no size over-represented — for every sufficiently large $n$, not just special values. A companion Erdős–Larson problem on pairwise balanced designs with all blocks large is Erdős #665 (erdosproblems.com/665). The attacker's tool: constructive design theory — truncated projective planes, transversal designs, and Wilson-type composition to generate blocks with well-spread sizes — together with computer search producing explicit verified designs for concrete ranges of $n$ (a checker program verifies the exactly-once pair cover and the per-size counts).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #734 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #665 — companion problem on pairwise balanced designs with all blocks large | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.