Erdős Problem #147
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 graph \(H\), the Turán number \(\mathrm{ex}(n,H)\) is the maximum number of edges among all \(n\) vertex graphs containing no copy of \(H\). Erdős and Simonovits conjectured that if \(H\) is bipartite with minimum degree \(r\ge3\), then for some constant \(\epsilon=\epsilon(H)>0\),
The lower-bound inequality is existential over dense \(H\) free graphs, whereas a matching upper bound for a carefully chosen \(H\) can disprove this assertion.
A small example
For \(r=3\), the predicted exponent is \(2-1/(3-1)=3/2\), with a strict power improvement \(n^\epsilon\). A 3-regular bipartite graph has minimum degree three, but it is not enough to know that some such \(H\) exists: one must show its Turán number grows too slowly for any prescribed positive improvement over \(3/2\).
Janzer's construction supplies, for every fixed small \(\delta>0\), a 3-regular bipartite graph \(H\) with \(\mathrm{ex}(n,H)\ll n^{4/3+\delta}\). Choosing \(\delta=1/12\) gives the exponent \(17/12<3/2\). Thus even the unamplified \(3/2\) lower scale fails for that \(H\).
What is known
DISPROVED. Oliver Janzer, Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3, International Mathematics Research Notices (2023), 8478–8494, gives the \(r=3\) counterexample. His separate 2023 paper Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles provides the failure for all even \(r\ge4\).
The maintained Erdős #147 distinguishes the disproved conjectured exponent \(2-1/(r-1)\) from a different probabilistic lower exponent \(2-2/r+\epsilon\). Janzer proposes the latter as the sharp scale for suitably chosen regular bipartite \(H\); proving that conjecture for even values of \(r\) does not settle its remaining odd-degree versions.
GCL's current state
The pinned and maintained catalogues record #147 DISPROVED. The original authenticated issue is #1416. The \(r=3\) exponent contradiction follows immediately from the stated primary theorem and was checked, but the full 2023 extremal construction has not been independently reproduced.
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
A bounded task formalizes the implication from Janzer's \(n^{4/3+\delta}\) upper estimate to the failure of every \(n^{3/2+\epsilon}\) lower estimate for its selected \(H\). Acceptance: verify positive constants, dependence on the fixed graph \(H\), the \(\delta=1/12\) exponent calculation, and the exact universal versus existential order. Stop before promoting the still-conjectural sharp exponent for all degrees.
Sources and claim boundaries
- Janzer, arXiv:2109.06110, primary \(r=3\) disproof.
- Erdős #147, Janzer's even-degree result and open successor conjecture.
- GCL original issue #1416.
No new counterexample, full extremal-proof replay or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1416 — 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.