PROVED
This has been solved in the affirmative.
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\}$?
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].
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
JoshuaB
|
|
I am working on formalising the results on this problem
|
None
|
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #732, https://www.erdosproblems.com/732, accessed 2026-04-11
