The board / combinatorics / #665
Erdős Problem #665
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
A pairwise balanced design for \(\{1,\ldots,n\}\) is a collection of sets \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that \(2\leq \lvert A_i\rvert <n\) and every pair of distinct elements \(x,y\in \{1,\ldots,n\}\) is contained in exactly one \(A_i\). Is there a constant \(C>0\) and, for all large \(n\), a pairwise balanced design such that \[\lvert A_i\rvert > n^{1/2}-C\] for all \(1\leq i\leq m\)?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/665.Prizenone
Topicscombinatorics
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/665
Attempts
submit one →Read our working report →
Exact \(f(n)\) for every \(3\le n\le21\), plus a verified \(C=2\) construction for every \(q^2\le n\le q^2+q+1\) with prime-power \(q\); the uniform problem remains blocked by gaps between projective-
PARTIAL