Skip to content

Erdős Problem #776

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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

An antichain is a family of subsets of \({1,\ldots,n}\) in which no two different members contain one another. Ordinarily, Sperner's theorem asks how many members an antichain can have. Erdős and Trotter asked a different question: how many different sizes can occur if every occurring size must appear at least \(r\) times?

Write \(g(n,r)\) for the largest number of occupied sizes. For every fixed \(r\geq2\), large enough \(n\) permits \(n-3\) sizes, but not \(n-2\). What is the threshold \(n_0(r)\) after which that is always possible? A 2026 paper settles its asymptotic behavior and two exact cases, but leaves the precise threshold open in general.

A small example

When \(n=4\) and \(r=2\), take the two sets \(\{1,2\}\) and \(\{3,4\}\). They are incomparable, both have size two, and so form a valid antichain with one occupied level of multiplicity two.

In contrast, \(\{1\}\) and \(\{1,3\}\) are comparable and cannot belong to the same antichain, even though their sizes differ. The desired construction must occupy many levels without creating any inclusion between members on those levels. This is why choosing many subsets of each cardinality is not enough.

What is known

Yixin He and Quanyu Tang, An Erdős–Trotter problem on antichains with multiplicity r on each occurring level, arXiv:2602.09803v2 (21 March 2026), state on pp. 1–2 that

\[ n_0(2)=3,\qquad n_0(3)=8, \]

and prove in Theorems 1.4 and 1.5, for \(r\geq4\),

\[ 2r+2\leq n_0(r)\leq 2r+2\log_2 r+O(\log_2\log_2 r). \]

In particular,

\[ \frac{n_0(r)}{r}\longrightarrow 2. \]

This answers the leading-order growth question while not determining each exact integer \(n_0(r)\) for \(r\geq4\). A crucial point is the definition of threshold: \(n_0(r)\) is the smallest integer such that every larger \(n\) admits the target family, not merely one favorable value of \(n\).

The paper records a further source distinction on p. 2, Remark 1.2. The historical Erdős–Trotter formulation required exactly \(r\) sets at each occupied level, whereas the Guy/maintained-catalogue version says at least \(r\). These yield the same extremal \(g(n,r)\): from an antichain with at least \(r\) sets at a level, select any \(r\) of them and discard the rest. Removing sets cannot create an inclusion relation, and no occupied size disappears. This proves equivalence without guessing.

GCL's current state

The authenticated original source return remains in its original BOUNDED_TASK_DESIGNED state. This is an editorially reviewed explanatory article in protected EC-BULK-005-R7, subject to that PR's protected merge. Original research theorem proofs and any external formalizations are attributed to their authors, not newly GCL-certified. The historical source and proof-review limitations recorded in the return remain applicable.

What remains

Build a bounded SAT or backtracking oracle for \(g(n,r)\), checking the antichain condition and cardinality multiplicities, and compare small cases with the paper's Appendix A. Verify the equivalence of exactly and at least \(r\) independently. Audit the full 1981 original and the computation behind \(n_0(3)=8\). No finite list of successful \(n\) establishes the eventual-for-every \(n\) threshold.

Sources and claim boundaries

  • Erdős problem #776, source return #2047.
  • Y. He and Q. Tang, arXiv:2602.09803v2, Problem 1.1, Remark 1.2, Definition 1.3 and Theorems 1.4–1.5 (pp. 1–2); Appendix A for exact small cases.
  • Historical [Er81i]/[Gu83] original statements are cited by the authors, but independent historical source review remains pending. no independent theorem proof certification.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2047 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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