Skip to content

Erdős Problem #732

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: combinatorics.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

What block-size sequences are possible in a pairwise-balanced design? Given n points, choose blocks so that every unordered pair is contained in exactly one block. The question Erdős #732 asks for a classification and, separately, for at least \(\exp(c\sqrt{n}\log n)\) distinct compatible sorted size sequences.

A small example

For n=4, all six unordered vertex pairs form a design with six size-2 blocks, hence the sequence (2,2,2,2,2,2) is compatible. For n=7, the seven Fano triples {j,j+1,j+3} modulo 7 each meet every unordered point pair exactly once, so the sequence (3,3,3,3,3,3,3) is compatible.

What is known

Counting pairs inside blocks forces \(\sum_i\binom{X_i}{2}=\binom{n}{2}\), an elementary necessary condition. The maintained source credits Erdős with an upper \(\exp(O(\sqrt{n}\log n))\) for the number of sorted compatible sequences and Noga Alon with the matching exponential-scale lower bound \(2^{(1/2+o(1))\sqrt{n}\log n}\). Thus the counting lower-bound question is PROVED. This does not amount to a general constructive necessary-and-sufficient criterion for an arbitrary proposed sequence.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition PARTIAL. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: Alon's exponential-scale lower bound on block-size sequence counts does not characterize which individual sequences are realizable.

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

Source-lock the author's exact count theorem and definition of distinct sequences. Explore whether the pair-count condition has additional necessary restrictions, using exact-cover enumeration for small n. Complete critical mathematical review, protected batch publication and deployed math rendering before V2 editorial admission.

Sources and claim boundaries

Maintained #732; authenticated GCL original issue return; historical Erdős [Er81] and Alon's proof not read in full. No original theorem discovery or GCL proof certificate.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2003 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction