Status
On this page
Status
Topics
Status
On this page
Status
Topics
A pairwise balanced design for is a collection of sets such that and every pair of distinct elements is contained in exactly one .
Is there a constant and, for all large , a pairwise balanced design such that
for all ?
Source: erdosproblems.com/665
No claim settles this problem.
Open on erdosproblems.com (label OPEN; page last edited 18 January 2026). The site records the question as Erdős and Larson's, and Erdős's wider one, for the slowest-growing such that for all large some pairwise balanced design has for every block: Erdős and Larson [ErLa82] reach for some , and under a Cramér-type bound on prime gaps; Shrikhande and Singhi [ShSi85] embed every large design with blocks of size at least in a projective plane, so the answer is no if every projective plane has prime power order, and, with the largest gap between consecutive primes up to , the prime power conjecture gives . The conditional negative answer is recorded as the accepted conditional claim Shrikhande and Singhi 1985; no unconditional result settles the question.