Skip to content

Erdős Problem #713

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

For every bipartite graph G the Erdős–Simonovits question asks whether ex(n,G)~c n^α for some c>0 and α∈[1,2), and whether α must be rational. A weaker recorded version only asks ex(n,G) asymptotic up to constant factors to a power. The source's literal universal scope needs a degeneracy qualification: for G=K_2 (a single edge), ex(n,G)=0 for every n≥2, incompatible with c>0, α≥1. Intended discussion evidently concerns suitable nontrivial bipartite forbidden graphs; the exact original hypotheses must be source-locked. The meaningful nondegenerate problem remains OPEN.

A small example

For G=C_4=K_{2,2}, classical extremal theory gives ex(n,C_4)=(1/2+o(1))n^(3/2): an exponent α=3/2 and positive constant 1/2 are known. For G=K_2, any graph with even one edge contains G, so ex(n,K_2)=0 identically, an exact counterexample to the UNQUALIFIED wording. These do not refute a carefully restricted nondegenerate Erdős–Simonovits conjecture.

What is known

The maintained source (updated 2026-03-07) differentiates the original claim that α belongs to special forms 1+1/k or 2−1/k (already DISPROVED by Erdős–Simonovits 1970) from the still-OPEN existence/rationality question for a general bipartite G. Frankl–Füredi 1987 and Füredi–Gerbner 2021 provide counterexamples to analogous pure-power behaviour for uniform hypergraphs of uniformity at least five; these hypergraph results do NOT settle graph r=2. No GCL pinned Formal Conjectures file for #713, despite metadata reporting a later formalized statement. Full primary ErSi70 and related papers not independently reviewed.

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: The literal all-bipartite-graph domain includes degenerate cases with extremal exponent 0; restrict nondegenerate domains before assessing open pure-power/rationality.

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-713-DEGENERATE-GRAPH-SOURCE-LOCK. Examine original ErSi70 p379 and ErSi84 definitions to identify excluded trivial graphs, isolated vertices and single-edge cases. Prove exact ex(n,K_2)=0; for connected cycles or graphs with at least two edges, tabulate known exponents and constants with the historical theorem hypotheses. Acceptance is a source-faithful quantified formulation and one verified small counterfixture, not a claim to solve the nondegenerate question.

Sources and claim boundaries

Maintained Erdős #713; authenticated original issue #1984. 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: #1984 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_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