Erdős Problem #146
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\), \(\mathrm{ex}(n,H)\) is the maximum number of edges in any \(n\) vertex graph with no copy of \(H\). A graph \(H\) is \(r\) degenerate when every nonempty subgraph has some vertex of degree at most \(r\). Erdős and Simonovits conjectured that every bipartite \(r\) degenerate graph satisfies
for each positive integer \(r\). A condition on degeneracy is weaker than a maximum-degree bound on an entire bipartition class.
A small example
Any tree is 1-degenerate, since every nontrivial subtree has a leaf. A cycle is 2-degenerate, since it has no subgraph of minimum degree above two. The \(r=2\) conjecture proposes an \(O(n^{3/2})\) extremal bound for every bipartite 2-degenerate \(H\); showing this bound for selected cycles or complete bipartite graphs does not establish the universal statement.
If a graph has minimum degree three in one of its subgraphs, it cannot be 2-degenerate. Therefore a counterexample must be verified against all subgraphs, not merely its average degree.
What is known
DISPROVED. The maintained Erdős #146, updated 31 August 2026, credits an OpenAI model with a connected bipartite 2-degenerate counterexample \(H\) for which
with some fixed \(c>0\). This contradicts the proposed \(O(n^{3/2})\) bound for \(r=2\). The recent upstream Formal Conjectures file cites the publicly inspectable OpenAI ten-proofs proof snapshot. Its formal theorem describes a connected bipartite 2-degenerate \(H\) and constants \(c,\epsilon>0\) with an eventual lower bound of order \(n^{3/2+\epsilon}\).
Alon, Krivelevich and Sudakov earlier proved the weaker \(O(n^{2-1/(4r)})\) bound, and the conjectured exponent in the special case where one bipartition class has maximum degree \(r\). Those positive theorems remain valid after a counterexample to the broader degeneracy claim.
GCL's current state
The pinned issue #1415 classifies #146 as disproved. The claim was checked against the currently published counterexample statement and exact named proof artifact. GCL has not independently built the external Lean project, audited its axioms or reconstructed all extremal construction estimates. Provenance of the external model result must remain explicit.
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 successor independently audits the counterexample graph's finite bipartiteness, connectedness and 2-degeneracy, then verifies how its protected extremal lower bound exceeds \(n^{3/2}\). Acceptance requires an exact source commit, a toolchain and axiom receipt for the formal theorem, and a separate graph-level checker. Stop before calling an external proof an admitted GCL kernel certification.
Sources and claim boundaries
- Erdős #146, original [ErSi84] and Alon–Krivelevich–Sudakov positive results.
- OpenAI proof artifact, externally reported formal counterexample.
- GCL original issue #1415.
No new extremal theorem, independently replayed Lean proof or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1415 — 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.