Status
On this page
Status
Topics
Status
On this page
Status
Topics
If is a finite set of finite graphs then is the maximum number of edges a graph on vertices can have without containing any subgraphs from . Note that it is trivial that for every .
Is it true that, for every , there exists such that
If is a finite set of finite graphs then is the maximum number of edges a graph on vertices can have without containing any subgraphs from . Note that it is trivial that for every .
Is it true that, for every other than those of the form where is a star and is a matching, both with at least two edges, there exists such that
Source: erdosproblems.com/180
An accepted solution exists. The statement is false.
DISPROVED (LEAN), the site's label, which records the disproof of
the corrected Statement. The answer is no. The accepted claim is Theorem 1.1 of
Chapter 10 of OpenAI's 2026 report, a finite family of connected bipartite
graphs, each containing a cycle, whose joint extremal number is
while every member's is , on
its claim page (OpenAI, 2026):
the site's curator, Thomas Bloom, attached the label and credited the disproof
to an internal model at OpenAI (commentary last edited 31 August 2026), which is
the documented acceptance; the report has no refereed version, and the Lean file
the site links was not built or audited in this repository, so it gives no
formalized evidence. Wigderson's two-forest family answers the printed wording
in the negative but is a family the corrected Statement excludes, so it is
recorded as rejected on
its claim page (Wigderson, 2022):
the curator's commentary credits a thread post with it as a folklore
counterexample and does not treat it as settling the problem. The forum's
dichotomy for families of forests, which answers the question for each such
family, is a claimed partial claim on
its claim page (Kj C, 2026).
The formalization paragraph below states what the two Lean files say.
The site's wording is Conjecture 1 of Erdős and Simonovits (Combinatorica 2 (1982), p. 276), "For every finite (containing bipartite graphs as well) there exists an " with display (5), read with its two sides interchanged as the source page records; it states no exception. It fails at the two-member family of the two-edge star and the two-edge matching : for the joint extremal number is , while each member's grows linearly (Known Results gives the check). The defect is already in the printed conjecture, not the site's. The site's curator, Thomas Bloom, reads the conjecture past that family. The commentary (page last edited 31 August 2026) reports Hunter's "folklore counterexample", a star and a matching "both with at least two edges", with and , and continues "This conjecture may still hold for all other "; it then credits the disproof to an internal model at OpenAI, pointing to the remarks under Problem 575, and the label DISPROVED (LEAN) records that disproof, whose family contains neither a star nor a matching. No curator post appears in the thread. The change inserts "other than those of the form where is a star and is a matching, both with at least two edges" after "for every ", in the commentary's words; nothing else changes. The printed wording is answered no by the star-and-matching family: post 124 of the thread (19 August 2025, the account zach hunter) and Wigderson's note (p. 1, Observation, crediting Jordan Lefkowitz and reporting Simonovits's private communication that such counterexamples had long been known). That result answers the printed wording (every finite family), not the corrected Statement (every family other than a star with a matching), so it does not count toward the problem's standing; it is recorded as a rejected claim page (Wigderson, 2022). The corrected Statement is answered no by Theorem 1.1 of Chapter 10 of OpenAI's 2026 report, a family of connected bipartite graphs each containing a cycle, on its claim page (OpenAI, 2026). The commentary excludes only the two-member families: a family that adds to such a pair further members with at least two edges still has bounded joint extremal number, while each added member's own is unbounded, so it remains a counterexample. The page's standing judges the corrected Statement.