Skip to content

Erdős Problem #712

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, turan number, 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.

The question in plain language

For integers \(k>r>2\), let the extremal function

\[ \mathrm{ex}_r(n,K_k^r) \]

denote the maximum number of \(r\) element hyperedges on \(n\) labelled vertices that contain no complete \(r\) uniform hypergraph on \(k\) vertices.

Erdős asks for the limiting Turán density

\[ \pi(K_k^r)=\lim_{n\to\infty}\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}}. \]

This limit exists, but its value is OPEN in general. A literal source normalization is inconsistent: the maintained page gives the graph case \(r=2\) limit as \(\tfrac12(1-\tfrac1{k-1})\), but with denominator \(\binom{n}{2}\) the correct limit is \(1-1/(k-1)\). The extra factor \(\tfrac12\) corresponds instead to \(\mathrm{ex}(n,K_k)/n^2\).

A small example

For \(k=4\), \(r=3\), and \(n=4\) there are exactly four possible triples on four vertices. Any three avoid \(K_4^3\), while all four contain it, so \(\mathrm{ex}_3(4,K_4^3)=3\) and its normalized density is \(3/4\). For \(r=2\), \(k=4\) Turán's theorem gives \(\mathrm{ex}(n,K_4)/\binom{n}{2}\to 2/3\), not \(1/3\). These are finite/source-normalization checks, not a solution of \(\pi(K_4^3)\).

What is known

The normalized sequence \(a_n=\mathrm{ex}_r(n,K_k^r)/\binom{n}{r}\) is nonincreasing: restrict an extremal \((n+1)\) vertex hypergraph to a uniformly chosen \(n\) vertex subset, and note its expected edge count is \(\mathrm{ex}_r(n+1,K_k^r)\binom{n}{r}/\binom{n+1}{r}\); this cannot exceed \(\mathrm{ex}_r(n,K_k^r)\). Hence the nonnegative sequence has a limit. Turán's graph theorem gives the graph-case normalized density \(1-1/(k-1)\), but for \(r\ge3\), even the \(r=3\), \(k=4\) case is a famous open hypergraph Turán-density question. Pinned catalogue status OPEN, live maintained source last edited 2025-10-05. Primary historical Er71/Er74c/Er81 theorem pages not independently inspected; historical USD 500 is source metadata only.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition STATUS_CONFLICT. 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: Use hypergraph normalization binom(n,r); graph r=2 Turan density does not solve r>=3, and the source denominator correction is explicit.

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

ERDOS-712-TURAN-DENSITY-NORMALIZATION. Pin an original Erdős hypergraph statement and determine whether its graph base case is divided by \(n^2\) or \(\binom{n}{2}\). Produce a formal lemma for existence of \(\pi\) via random-vertex deletion and exact \(\mathrm{ex}_3(4,K_4^3)=3\) fixture. Acceptance is a precise corrected denominator (not a generalized solution) and historically grounded statement.

Sources and claim boundaries

Maintained Erdős #712; authenticated original issue #1983. Primary historical papers and complete formal dependencies not independently replayed. Critical source review, production merge, deployed math rendering and V2 admission remain outstanding.

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: #1983 — 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