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 , if there is a bipartite graph in then there exists some bipartite such that
Source: erdosproblems.com/575
An accepted solution exists. The statement is false.
Disproved, on two routes. (1) The statement is false by the
elementary Observation on p. 1 of Wigderson's note [Wig22]
(result page,
recomputed below): for , both members
bipartite, for while
and
for , so no member satisfies the displayed comparison. (2) The
no-forest form is disproved by Theorem 1.1 of Chapter 10 of OpenAI's
technical report Ten Advances in Mathematics and Theoretical Computer
Science (August 6, 2026 version;
result page):
a finite nonempty family of connected bipartite graphs, every
member containing a cycle, with
and for every . Its
author is OpenAI; the announcement attributes the arguments to an internal
model and manuscript preparation to humans working with that model; the
site accepted it as the disproof on 31 August 2026 with the label
DISPROVED. 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, and the
corpus has not built or audited the accompanying Lean file. The claim pages
record both routes:
Wigderson's two-forest observation
is claimed, since no outside acceptance of it is documented (the site's
commentary does not mention it, and the report's p. 237 restates the values
without reviewing the note), and
OpenAI's Theorem 1.1
is accepted on the site's acceptance alone (evidence reviewed: the
curator's label and commentary of 31 August 2026), with no refereed
publication and no independent review. The frontmatter standing is derived
from the accepted claim, so it rests on the site's acceptance of an
AI-generated argument; the elementary route (1) is recomputed below but, as
this project's own check, awards no acceptance.