Skip to content

Erdős Problem #794

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory, hypergraphs, turan number.

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

Claim: every 3-uniform hypergraph with 3n vertices and at least n^3+1 edges contains a four-vertex subhypergraph with at least three triples OR a five-vertex subhypergraph with at least seven triples. This is DISPROVED for n=3 by a 9-vertex construction.

Separate claims: the explicit nine-vertex hypergraph refutes the literal conjecture. It does not resolve the still-different sharp extremal density question related to the Frankl–Füredi construction.

A small example

Partition vertices 1..9 into X={1,2,3},Y={4,5,6},Z={7,8,9}. All XxYxZ triples (27) and X as an additional edge (one). For n=3, n^3+1=28. Exhaustively check no 4-vertex subset contains 3 triples and no 5-vertex subset contains 7; exact finite certificate is the bounded successor.

The calculation illustrates the exact definitions and hypotheses. No single finite example establishes the reported asymptotic assertion.

What is known

Live /latex/794 and indexed historical page attribute explicit example to Harris: take complete tripartite 3-graph on parts of three vertices (27 edges), plus the triple consisting of the entire first part (28 edges). Pinned registry says DISPROVED; external Lean claim not independently replayed. Frankl–Füredi [FrFu84] 2/7 density is a separate asymptotic Turán issue, not resolution of that open extremal conjecture.

Catalogue status: DISPROVED. The actual recorded source-audit disposition is SOURCE_LOCK_READY. These are different registers: a historical theorem report does not count as an independent GCL proof.

GCL's current state

The authenticated original RESULT/1 source return records SOURCE_LOCK_READY and preserves its issue-bound mathematical source observations. This explanatory article is REVIEWED under the exact-hash EC-BULK-005-R6 editorial transaction, subject to the protected merge of PR #2676. Its original source-audit status is retained. Editorial acceptance and public MathJax validation do not certify any original research theorem, external Lean file, or complete historical proof.

Unclosed mathematical proof/source qualifications: SOURCE_FOUR_FIVE_SUBGRAPH_CONVENTION_REVIEW_PENDING; EXTERNAL_LEAN_NOT_GCL_REPLAYED.

What remains

Enumerate all 126 four-sets and 126 five-sets, check local edge counts and maximal count; if true, source-lock as genuine finite refutation. Verify the logic by which 5-vertex 7-edge obstruction implies 4-vertex 3-edge and historical notation (at least/induced). Do not convert exact disproval into claim on optimal asymptotic 2/7 density.

For mathematical proof certification, the complete primary argument and any external formalization must undergo separate independent replay. The bounded finite calculation is recorded in the governed R6 fixture; editorial approval does not discharge the outstanding research obligations.

Sources and claim boundaries

  • Maintained Erdős Problem #794 and its LaTeX and bibliography, accessed 14 October 2026.
  • Authenticated source return on original GCL issue #2065. Named bibliography and the limits of historical-primary inspection are recorded there.
  • Pinned catalogue: teorth/erdosproblems at 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, original source blob 4e60263a80af6207aca494d2e1388e44fa372889.
  • Editorial decision: exact-hash reviewed explanatory article, protected R6 transaction. Mathematical theorem proof / external Lean certification: NOT CLAIMED. The original SOURCE_LOCK_READY return, primary-source attribution, and proof-review holds remain.

Catalogue and evidence provenance

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