Skip to content

Erdős Problem #113

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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 a fixed graph \(H\), the Turán number \(\mathrm{ex}(n,H)\) is the largest possible number of edges in an \(n\) vertex graph without a copy of \(H\). Erdős and Simonovits proposed that, for a bipartite graph \(H\), the estimate

\[ \mathrm{ex}(n,H)=O_H(n^{3/2}) \]

holds if and only if \(H\) is 2-degenerate: every nonempty subgraph of \(H\) has a vertex of degree at most two.

The adjective 2-degenerate is stronger than merely having average degree below three; the definition applies to all subgraphs, not just \(H\) itself.

A small example

Every tree is 1-degenerate: any nonempty subgraph with an edge has a leaf, while edgeless subgraphs have isolated vertices. The complete bipartite graph \(K_{3,3}\) is not 2-degenerate because its minimum degree equals three. This makes 3-regular bipartite graphs natural candidates for testing the proposed reverse implication.

However, finding one dense \(H\) free graph is not the same as proving an upper bound on \(\mathrm{ex}(n,H)\) for all \(n\). A counterexample to the conjecture must violate the implication from the upper-bound property back to degeneracy.

What is known

DISPROVED. Oliver Janzer's Disproof of a Conjecture of Erdős and Simonovits on the Turán Number of Graphs with Minimum Degree 3, published in International Mathematics Research Notices 2023, 8478–8494, constructs for every \(\varepsilon>0\) a 3-regular bipartite graph \(H\) satisfying

\[ \mathrm{ex}(n,H)=O_H(n^{4/3+\varepsilon}). \]

Choose, for example, \(\varepsilon=1/12\). Then \(4/3+1/12=17/12<3/2\); thus the constructed non-2-degenerate \(H\) nevertheless has \(\mathrm{ex}(n,H)=O(n^{3/2})\). This directly refutes the “only if” half of the conjecture. The primary publisher abstract and arXiv:2109.06110 support the precise quantifiers.

GCL's current state

The pinned catalogue and maintained Erdős #113 report DISPROVED. Original task: #1382. The logical exponent reduction is independently checked. Janzer's complete graph construction and proof are not reproduced or certified in this audit.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

Formalize the elementary contradiction given a theorem supplying a 3-regular bipartite \(H\) with an \(n^{4/3+\varepsilon}\) upper estimate for any fixed \(\varepsilon>0\). Verify mechanically that a 3-regular graph has a subgraph of minimum degree three, and that \(n^{17/12}\le n^{3/2}\) for \(n\ge1\). Acceptance: quantified contradiction to the reverse implication; the deep Janzer construction remains an explicitly imported source theorem.

Sources and claim boundaries

No new extremal graph theorem, independent replay of Janzer's construction, or editorial admission is claimed.

Catalogue and evidence provenance

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