Skip to content

Erdős Problem #1076

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: proved (not automatically the live result).
Subject areas: hypergraphs.

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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Consider a collection of triples drawn from an \(n\)‑element vertex set. This is a \(3\)‑uniform hypergraph. For a fixed integer \(k\ge5\), forbid every configuration with \(k\) vertices carrying \(k-2\) distinct triples.

How many triples can remain? The extremal function \(\mathrm{ex}_3(n,\mathcal F_k)\) is the maximum possible number. Erdős Problem #1076 asked whether, for every fixed \(k\),

\[ \mathrm{ex}_3(n,\mathcal F_k)\sim\frac{n^2}{6} \qquad(n\to\infty). \]

The phrase for fixed \(k\) is important. The statement does not claim the same finite threshold for arbitrary \(k\) growing with \(n\).

A small example

A simple triple system can be built from two disjoint triples on six vertices, such as \(\{1,2,3\}\) and \(\{4,5,6\}\). This has only two edges, so it cannot contain a forbidden configuration with three edges when \(k=5\).

Another useful benchmark is a linear triple system: no pair of vertices occurs in more than one triple. Each triple contains three unordered vertex pairs, and there are only \(\binom n2\) pairs altogether. Thus an elementary double count gives

\[ |E|\le\frac{1}{3}\binom n2=\frac{n(n-1)}6. \]

This pair-counting result by itself does not show that a linear triple system avoids every \(\mathcal F_k\). That avoidance property, while still reaching nearly this bound, is the difficult part.

What is known

The asymptotic conjecture was proved. The maintained catalogue credits independent results by Bohman and Warnke (2019), and Glock, Kühn, Lo and Osthus (2020). Their work constructs sufficiently sparse approximate Steiner triple systems to achieve the required asymptotic edge count while avoiding the forbidden configurations.

The question originated with Brown, Erdős and Sós in 1973 and appears in Erdős's 1974 survey on page 81. Their earlier work established the correct quadratic order but not the sharp leading constant for every fixed \(k\).

GCL's current state

Authenticated source audit #2347 fixes the precise forbidden family and separates elementary pair counting from the published existence construction. The pinned formal-conjectures provider has no protected statement for #1076.

No original 2019 or 2020 proof has been independently replayed by GCL. The status proved here reports existing mathematical literature; it does not claim a new discovery or an independently certified proof.

What remains

Editorial review should check the original Brown–Erdős–Sós formulation, then inspect the two independent asymptotic proofs for fixed‑\(k\) assumptions, design existence, and any auxiliary regularity or absorption hypotheses. Finite small systems can test the definitions but cannot verify the asymptotic construction.

Sources and claim boundaries

  • Erdős Problem #1076, proved status and detailed bibliography.
  • T. Bohman and L. Warnke, Large girth approximate Steiner triple systems, Journal of the London Mathematical Society (2019), pp. 895–913.
  • S. Glock, D. Kühn, A. Lo and D. Osthus, On a conjecture of Erdős on locally sparse Steiner triple systems, Combinatorica (2020), pp. 363–403.
  • Authenticated GCL source audit #2347.

The externally proved asymptotic statement is not yet a GCL-admitted article.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2347 — 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