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
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
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
- Janzer, IMRN 2023, primary publisher abstract; author manuscript.
- Maintained Erdős #113; GCL issue #1382.
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.