Problem Statement
Call a sequence $1< X_1\leq \cdots \leq X_m\leq n$ block-compatible if there is a pairwise balanced block design $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ such that $\lvert A_i\rvert=X_i$ for $1\leq i\leq m$. (A pairwise block design means that every pair in $\{1,\ldots,n\}$ is contained in exactly one of the $A_i$.)
Are there necessary and sufficient conditions for $(X_i)$ to be block-compatible?
Is there some constant $c>0$ such that for all large $n$ there are\[\geq \exp(c n^{1/2}\log n)\]many block-compatible sequences for $\{1,\ldots,n\}$?
Are there necessary and sufficient conditions for $(X_i)$ to be block-compatible?
Is there some constant $c>0$ such that for all large $n$ there are\[\geq \exp(c n^{1/2}\log n)\]many block-compatible sequences for $\{1,\ldots,n\}$?
Categories:
Combinatorics
Progress
Erdős noted that a trivial necessary condition is $\sum_i \binom{X_i}{2}=\binom{n}{2}$, but wasn't sure if there would be a reasonable necessary and sufficient condition.He could prove that there are\[\leq \exp(O(n^{1/2}\log n))\]many block-compatible sequences for $\{1,\ldots,n\}$.
Alon has proved there are at least\[2^{(\frac{1}{2}+o(1))n^{1/2}\log n}\]many sequences which are block-compatible for $n$.
See also [733].
Source: erdosproblems.com/732 | Last verified: January 16, 2026