Math Conjectures

Erd\u0151s Degeneracy Conjecture for Extremal Numbers

OPENMajorConjectureProposed 1967 · Standard version

Canonical statement

For every integer r≥2r\ge2 and every fixed bipartite rr-degenerate graph HH,
ex⁡(n,H)=OH ⁣(n2−1/r). \operatorname{ex}(n,H)=O_H\!\left(n^{2-1/r}\right).
A graph is rr-degenerate if every nonempty subgraph has a vertex of degree at most rr.
View source LaTeX
For every integer \(r\ge2\) and every fixed bipartite \(r\)-degenerate graph \(H\),
\[
  \operatorname{ex}(n,H)=O_H\!\left(n^{2-1/r}\right).
\]
A graph is \(r\)-degenerate if every nonempty subgraph has a vertex of degree at most \(r\).
GRAPH-029:[FurediSimonovits2013Degenerate][OpenAI2026TenAdvances]
Graph theoryCombinatorics

Notes

Erdős predicted ex⁡(n,H)=O(n2−1/r)\operatorname{ex}(n,H)=O(n^{2-1/r}) for every fixed bipartite rr-degenerate graph; the history and established cases are surveyed by Füredi and Simonovits [FurediSimonovits2013Degenerate]. The August 1, 2026 manuscript claims a counterexample already for r=2r=2 [OpenAI2026TenAdvances]. It is kept as a linked Grade C refutation claim rather than an immediate status flip.

Proof-claim watch (1)

Counterexample to Erdős's degeneracy conjecture

Grade C

Full counterexample claim awaiting independent verification.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.