Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a family of finite graphs such that for every there is some such that if the edges of are coloured with colours then there is a monochromatic triangle.
Is it true that for every infinite cardinal there is a graph of which every finite subgraph is in and if the edges of are coloured with many colours then there is a monochromatic triangle.
Let be a family of finite graphs, closed under taking subgraphs, such that for every there is some such that if the edges of are coloured with colours then there is a monochromatic triangle.
Is it true that for every infinite cardinal there is a graph of which every finite subgraph is in and if the edges of are coloured with many colours then there is a monochromatic triangle.
Source: erdosproblems.com/638
A full solution has been claimed but not yet accepted. The statement is false.
The site shows OPEN, a label that fits the corrected Statement and not the site's wording. A negative answer to the corrected Statement is claimed in an unreviewed note. Main Theorem 1 of an eleven-page note dated 26 April 2026 [Sa26], hosted on a file-sharing site and posted to the site's discussion thread, constructs a class of finite graphs closed under isomorphism and finite subgraphs that contains, for every , a graph forcing a monochromatic triangle under colors, while no graph whose finite subgraphs all lie in the class forces one under any infinite number of colors. The note is a forum-posted claim prepared with the help of Aristotle AI, an automated proof system, with no refereed publication, arXiv record or independent review found on 2026-09-18, and its accompanying Lean project leaves the two combinatorial inputs unproved; it is recorded at claimed on Saturnino's claim page (2026), and the frontmatter standing derives from the claim pages. No other source on the hereditary question was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.
The site's wording asks the question for every family that meets the hypothesis, and it fails at families that are not closed under subgraphs. Let consist of one complete graph for each , of order large enough that every -coloring of its edges has a monochromatic triangle. The hypothesis holds, but every graph on two or more vertices has a subgraph on two vertices with no edge, which is not complete and so not in , and a graph on one vertex contains no triangle; so for no infinite cardinal does the graph asked for exist. The failure uses nothing about triangles or colorings. Kevin Barreto found it in the site's discussion thread on 5 January 2026 (comment, with the family of complete graphs on the successive triangle Ramsey numbers), and the site's commentary records it. The change inserts "closed under taking subgraphs" after "a family of finite graphs", in the words of the site's commentary, which records Barreto's note that is presumably intended to be closed under taking subgraphs, or else a sparse family of complete graphs is a trivial counterexample; the site keeps the label OPEN, which only the hereditary form fits. That is the only evidence for the change, and it is weak: it is the site's own, and no text of Erdős or of the literature independent of a claimant states the hereditary form. Erdős's item 9 of [Er97d] (pp. 83--84), which the site's wording follows nearly word for word, says only "a family of finite graphs" and is silent on closure, so the defect is already in Erdős's text. Barreto's counterexample answers the site's wording (every family meeting the hypothesis), not the corrected Statement (families closed under taking subgraphs), so it does not count toward the problem's standing; it is credited here and on Barreto's claim page (2026), which is rejected.