Problem 146

If $H$ is bipartite and is $r$ -degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$ , then

\mathrm{ex}(n;H) \ll n^{2-1/r}.

Source: erdosproblems.com/146

Graph theory
Turán numbers

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN). The status-defining source is Theorem 1.2 of Chapter 10 of OpenAI's technical report Ten Advances in Mathematics and Theoretical Computer Science (August 6, 2026 version; result page): there exist a fixed connected bipartite $2$ -degenerate graph $H$ and constants $c,\varepsilon>0$ with $\mathrm{ex}(n,H)\ge c\,n^{3/2+\varepsilon}$ for all sufficiently large $n$ , which fails the conjectured $O(n^{2-1/2})=O(n^{3/2})$ at $r=2$ . Its author is OpenAI; the announcement attributes the arguments to an internal model and manuscript preparation to humans working with that model. The site labels the problem DISPROVED (LEAN) and credits the result (page last edited 31 August 2026; the community database lists the status as of its last update, dated 2 August 2026, without recording when the state changed). This is a source-supported solution accepted by the site, distinct from a claim of journal refereeing: no refereed publication and no independent expert review of the argument was found. The accompanying Lean file, at a pinned commit, has not been built or audited by the corpus, and no kernel credit is claimed. The claim page OpenAI's Theorem 1.2 records the result, its postings and the site's acceptance, the curator's credit being its only acceptance evidence (listed as reviewed), and the frontmatter standing is derived from it; a refereed version, an independent whole-argument review or a build of the formal proof checked against the problem's statement would add evidence, and none was found. The partial result in the other direction is [AKS03]: $\mathrm{ex}(n;H)\le h^{1/2r}n^{2-1/4r}$ for every bipartite $r$ -degenerate $H$ of order $h$ (Theorem 3.5), and the conjectured exponent when one side of the bipartition has all degrees at most $r$ (Corollary 2.3), the case of the statement that holds, recorded as an accepted partial claim on its claim page (Alon, Krivelevich and Sudakov, 2003).

OpenAI26: OpenAI, Ten Advances in Mathematics and Theoretical Computer Science, technical report announced 1 August 2026, PDF revised 6 August 2026 (253 pages; the public file whose PDF pages are cited); Chapter 10, Counterexamples to the Compactness and Degeneracy Conjectures for Extremal Numbers, printed pp. 236--249 (PDF pp. 240--253); Theorem 1.2, printed pp. 237--238; Section 6 (the graph), p. 245; Proposition 8.1, p. 246; proof, pp. 247--248. Library home: OpenAI 2026, chapter card chapter_10/.
AKS03: Alon, Noga and Krivelevich, Michael and Sudakov, Benny, Turán numbers of bipartite graphs and related Ramsey-type questions. Combin. Probab. Comput. 12 (2003), no. 5--6, 477--494, doi:10.1017/S0963548303005741 (Crossref record); Theorem 3.5, p. 483; Corollary 2.3, p. 480; the attribution remark, p. 484. Library home: Alon and Sudakov 2003.
ErSi84: Erdős, P. and Simonovits, M., Cube-supersaturated graphs and related problems. Progress in graph theory (Waterloo, Ont., 1982) (1984), 203--218. Library home: Erdős and Simonovits 1984 (Rényi archive scan; pp. 203--207 and 218 are the pages cited); the site's origin key, see the Formulation note.
Er67: Erdős, P., Some recent results on extremal problems in graph theory. Theory of Graphs (International Symposium, Rome, 1966), Gordon and Breach, New York (1967), 117--123. Library home: Erdős 1967 (the Rényi archive's scan 1967-22.pdf, with the French version on pp. 124--130; the conjecture on pp. 119--120; the card carries the row for this problem): the source [AKS03] (its [9]) and [OpenAI26] (its [Erd67]) cite for the conjecture.
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397--406. Not held.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350. Chapter I, the sentence after displays (1) and (2), printed p. 334: "If degree 2 is replaced by degree $r$ then presumably the exponent $\tfrac32$ must be replaced by $2-\tfrac1r$ ", the statement as a presumption, without a prize of its own (the prizes on the same page attach to (1) and (2), the equivalence of Problem 113). Library home: Erdős 1993.
Er97c: Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I, Algorithms Combin. 13, Springer (1997), 47--67; display (4.5) with its companion and the prize offers, printed p. 64; [OpenAI26] cites it (its [Erd97]) for the conjecture beside [Er67]. Library home: Erdős 1997; paged at Erdős 1997, Display (4.5).
Ja23b: Janzer, Oliver, Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3. Int. Math. Res. Not. IMRN 2023 (2023), 8478--8494. Context for the related equivalence conjecture (Problem 113); library home Janzer 2023 (not used on this page).

Problem 146

Status

Proof claims

Discussion