Two Erdős Problems on Partial Block Designs

Definitions and mathematical statement

For a positive integer $n$, let $[n]=\{1,\ldots,n\}$. A partial block design on $[n]$ is a finite family of subsets $A_1,\ldots,A_m\subseteq[n]$ satisfying $|A_i\cap A_j|\leq1$ whenever $i<j$. A pairwise balanced block design on $[n]$ is understood here in the usual sense: every block has at least two elements, and every unordered pair of distinct elements of $[n]$ lies in exactly one block. The supplied record uses the latter term without explicitly defining it; this interpretation requires source review.

The supplied statement attributes the following two questions to Erdős.

1. Is it true that \[ \begin{gathered} \forall c\in(0,1)\ \exists C=C(c)\in{\mathbb{R}}_{>0}\ \forall n,m\in{\mathbb{Z}}_{\geq1}\ \forall A_1,\ldots,A_m\subseteq[n],\\ \left[\left(\forall i,\ |A_i|>c\sqrt n\right)\ \land\ \left(\forall i<j,\ |A_i\cap A_j|\leq1\right)\right]\\ \Longrightarrow\ \exists B\subseteq[n]\ \forall i\in\{1,\ldots,m\},\quad 0<|B\cap A_i|\leq C\,? \end{gathered} \] Thus $C$ may depend on $c$, but must be independent of $n$, $m$, and the family of blocks. No requirement that every pair of points be covered is imposed in this question.
2. For $n\geq2$, a finite sequence of integers \[ n\geq x_1\geq\cdots\geq x_m\geq2,\qquad m\geq1, \] is called block-compatible for $n$ if there exists a pairwise balanced block design $A_1,\ldots,A_m$ on $[n]$ with $|A_i|=x_i$ for every $i$. Let $\mathcal S_n$ be the set of these sequences, counting each sequence once regardless of the number of designs realizing it. Is it true that \[ \exists c_0>0\ \exists n_0\in{\mathbb{Z}}_{\geq2}\ \forall n\in{\mathbb{Z}}_{\geq n_0},\qquad |\mathcal S_n|\geq\exp\!\left(c_0\sqrt n\log n\right)? \] Here $\log$ denotes the natural logarithm, and $c_0$ is an absolute constant independent of $n$, unrelated to the parameter $c$ in the first question.

These are the two questions in the supplied cleaned statement. The supplied dated literature assessment says that the separate counting lower bound has been settled, while a necessary-and-sufficient characterization of block-compatible sequences remains unresolved. That characterization is not explicitly posed in the supplied mathematical statement. Consequently, the second question is retained as a source question, without asserting that it remains open; no additional characterization problem is invented here. The registry's overall open label and its statement-verification label are supplied metadata, not independent mathematical verification.

Short English statement

The first Erdős question asks whether every partial block design whose blocks have size greater than $c\sqrt n$ admits a set meeting every block in between one and $C(c)$ points. The second asks for at least $\exp(c_0\sqrt n\log n)$ distinct realizable nonincreasing block-size sequences for every sufficiently large $n$. Supplied dated curation reports the counting bound as settled and a structural characterization as unresolved; the intended current open target therefore requires review.

Sources

• Local UnsolvedMath registry, supplied complete record: permanent ID $30006389$, source problem code catalogue entry, title "Two Erdős Problems on Partial Block Designs," in the Oberwolfach Reports Open Problems collection. The supplied statement attributes the questions to Erdős; the proposer field is empty, and the proposed year is recorded as 2025.
• Supplied report citation: Combinatorics, Probability and Computing (2026), Oberwolfach Reports, DOI 10.4171/owr/2025/42, pp. 2243--2322. https://doi.org/10.4171/owr/2025/42. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: "Oberwolfach Report 42 2025." https://oa.tib.eu/renate/bitstreams/72e281a6-ba33-4ac7-baf7-6fadd1126345/download.
• Supplied literature source: "Alon Blocking Partial Designs and Block-Compatible Sequences." https://web.math.princeton.edu/~nalon/PDFS/remark191.pdf. No further bibliographic details are supplied.
• Literature assessment date: 2026-08-22. This is supplied dated curation derived from the supplied OWR curation, not independently verified. It records status "open" and states that the counting lower bound is settled while necessary-and-sufficient conditions for block-compatible sequences remain unresolved. The supplied background expressly calls for independent verification of time-sensitive status and cited claims.