Erdős Problem a Daythe open tracker

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
WORKING REPORT BY THIS SITE · JUL 28, 2026

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