Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a graph with edges and no isolated vertices. Is the Ramsey number maximised when is 'as complete as possible'? That is, if edges with then is
where is the graph formed by connecting a new vertex to of the vertices of ?
Let be a graph with edges and no isolated vertices. Is the Ramsey number maximised when is 'as complete as possible'? That is, for all sufficiently large , if edges with then is
where is the graph formed by connecting a new vertex to of the vertices of ?
Source: erdosproblems.com/545
No claim settles this problem.
OPEN, the site's label (page last edited 2 December 2025), which describes the corrected Statement: the site's commentary records that the displayed statement fails for small and keeps the label, and the formal-conjectures statement takes all sufficiently large . Its one claim page, the account LouisD's small- counterexamples, is rejected because it answers the site's wording, not the corrected Statement, so the frontmatter standing, which judges the corrected Statement, is open with no claim. No proof, disproof or proof claim for the corrected Statement, for any , was found in the search whose scope the Current assessment records; Sudakov (2011, p. 2) reports "no progress" on the case as of 2010. This is a bounded negative finding, not a certificate of openness.
The site's wording quantifies over every and fails at . Here is the least such that every -coloring of the edges of contains a monochromatic copy of , the diagonal graph Ramsey number the site and the formalization use. For , , and , the path with two edges, and : two of the three edges of share a color and any two edges of share a vertex, while has one edge. The graph , two disjoint edges, has two edges, no isolated vertex and : coloring a triangle of red and the three edges at the fourth vertex blue leaves no two disjoint edges of one color, and in any -coloring of the ten edges of one color has at least five edges, while a graph whose edges pairwise share a vertex is a star or a triangle, with at most four edges on five vertices. So at . The same coloring gives : in , a red and blue edges at the other two vertices contain no monochromatic , so . The site's discussion thread records failures for and , all from the matchings , with (Cockayne and Lorimer 1975, as the comments cite them) against values of from Radziszowski's survey and a written argument in the thread; at the comparison holds by Burr's 1989 table, as the curator reports. Every recorded failure lies at , and a matching cannot fail for large , since grows linearly while ; these are boundary failures. The change inserts the words "for all sufficiently large ," after "That is,"; nothing else changes. No source gives a threshold for general , so the form is the one used when boundary failures are treated as exceptions by the poser's framing and the site's commentary. [ErGr75] p. 526 asks the case as an example of an asymptotic question, "Among all such graphs, which have the fastest growing values of ?", and its range ", " is the natural domain, not a print that blocks the change. Its two-color case already fails at (the instance above), so for the defect is in the poser's text and the site inherits it. Burr and Erdős restate that case with ([BuEr76] p. 257), which removes the failures with and says nothing about . The general comes from Chung's problem collection, whose condition , as the thread reports it, still fails at to , so it is not the form. The site's commentary records the small- failures under the label OPEN, and the formal-conjectures statement takes all sufficiently large ; it counts with the site. The form rests on these sources alone; no result settles it. A disproof of the corrected Statement needs failures for infinitely many . The results about the site's wording are thread comments of 28 October 2025 at erdosproblems.com/forum/thread/545: the account Adenwalla's failure at ; the account LouisD's failures at , which the site's commentary credits, on a rejected claim page (LouisD, 2025); and the curator T. F. Bloom's check that holds. They are credited here. The failures answer the site's wording (every ), not the corrected Statement (all sufficiently large ), so they do not count toward the problem's standing, which judges the corrected Statement.