Status
On this page
Status
Topics
Status
On this page
Status
Topics
Call a sequence block-compatible if there is a pairwise balanced block design such that for . (A pairwise block design means that every pair in is contained in exactly one of the .)
Are there necessary and sufficient conditions for to be block-compatible?
Is there some constant such that for all large there are
many block-compatible sequences for ?
Call a sequence block-compatible if there is a pairwise balanced block design such that for . (A pairwise block design means that every pair in is contained in exactly one of the .)
Is there some constant such that for all large there are
many block-compatible sequences for ?
Source: erdosproblems.com/732
An accepted solution exists. The statement is true.
Proved: the site's label PROVED describes the precise Statement. The site credits Alon's lower bound of block-compatible sequences, which answers it yes, and records Erdős's upper bound of and Erdős's remark that is necessary while a reasonable characterization seemed doubtful. See also Problem 733 for the line version.
The site's wording asks two things: for necessary and sufficient
conditions for block-compatibility, and whether at least
sequences are block-compatible for all large . The first has no yes-or-no
answer: block-compatibility is itself a necessary and sufficient condition, and
for each a finite search decides it, so, read as the site words it, it is
trivially answered, and read as a request for a reasonable characterization it
names no criterion for an answer. Erdős's own words set it apart from the
problem. In [Er81], Part VI, item 2 (p. 12 of the copy; p. 35 of the journal),
Erdős writes "One could ask: Give necessary and sufficient conditions for the
, that there should be a pairwise balanced block design
satisfying ? Trivially we must have
. Perhaps there will not be a
reasonable necessary and sufficient condition. On the other hand the following
problem should not be hopeless", and then states display (1),
for the number of
block-compatible sequences, adding that the upper bound is easy to prove and
that Erdős had no success with the lower bound. The site reads the problem the
same way: its label PROVED and its commentary credit Alon's lower bound
, record Erdős's doubt that a reasonable condition
exists, and claim no characterization; its thread (two comments of 4 October
2026, none by the curator) adds nothing on the first question. Alon's
Problem 4.2 in [Al26], which Alon identifies with Problem 732, states the
counting question alone. The change removes the sentence "Are there necessary
and sufficient conditions for to be block-compatible?" and inserts
nothing; the site asks only the lower bound of Erdős's (1), and the upper bound,
Erdős's and Alon's Section 4.3, is recorded in the Current assessment. The
answer under the site's reading is yes, by Alon's Theorem 4.5 (Theorem 2.3 of
the note), on the claim page. Under the reading the page does not adopt, the
characterization question has no claimed answer: the sum condition is necessary
and not sufficient (for the sizes satisfy it, but blocks of sizes
and on five points share two points), and the sequences satisfying it
alone far outnumber the block-compatible ones (Adenwalla's thread comment of 4
October 2026 gives their count as the coefficient of in
, reportedly of order
, against Erdős's upper bound ; a
thread comment, credited and not relied on). That question stays in Formulation
with no claim page. Results about the site's wording, credited and never
counted: none; the formal-conjectures statement file and Jingxuan Ding's Lean
development erdos732_yes (SpringSense Innovation Institute, commit
c8c4bbbd13024e4ed45a0548c75c64664501e067, announced in the thread on 4
October 2026) both state the counting question, which is the precise Statement,
and neither is built here. The page's standing judges the precise Statement.