Status
On this page
Status
Topics
Status
On this page
Status
Topics
We say is Ramsey size linear if for all graphs with edges and no isolated vertices.
Are there infinitely many graphs which are not Ramsey size linear but such that all of its subgraphs are?
We say is Ramsey size linear if for all graphs with edges and no isolated vertices.
Are there infinitely many graphs which are not Ramsey size linear but such that all of its proper subgraphs are?
Source: erdosproblems.com/79
An accepted solution exists. The statement is true.
Proved. The status-defining source is Theorem 1 (Wigderson 2024) of [Wi24]: infinitely many graphs fail to be Ramsey size-linear while each of their proper subgraphs has the property, which answers the corrected Statement yes. The version cited is arXiv:2409.05931v2 (5 May 2025); the paper appeared in European J. Combin. 128 (2025), 104175 (version of record dated August 2025 under an open license from 8 May 2025), so the result is refereed; the site's curator, T. F. Bloom, credits the paper under the label PROVED. The proof is non-constructive: it exhibits no graph beyond , and the paper's Open problem 5 asks for one, which the site's commentary also records as unknown. The claim page Wigderson 2024 records the result, its postings and the acceptance evidence.
The site's wording fails for every graph. Every graph is one of its own subgraphs, so a graph that is not Ramsey size linear always has a subgraph, itself, that is not Ramsey size linear; no graph qualifies, and the wording's answer is trivially no. The site's own example fails with the rest: is not Ramsey size linear, so not all of its subgraphs are. The change inserts the word "proper" before "subgraphs"; nothing else changes. The posers' own words fix the form. [EFRS93] defines the graphs asked for by edge deletion (Definition 2, p. 395: not Ramsey size linear, "but if any edge is deleted, then the resulting graph is Ramsey size linear"), says on the same page that three candidate graphs "would be minimal, since all of their proper subgraphs are Ramsey size linear", and asks for an infinite family of such graphs, or one other than (Question 6, p. 399). Erdős's restatement in [Er95] (item 9 of the combinatorics part, p. 12 of the reprint) presents as an instance, "known not to be Ramsey size linear but all its subgraph [sic] are Ramsey size linear", which is true only of its proper subgraphs; so the omission of "proper" is already in [Er95], and the site follows that wording. The site's commentary names as the only known example, and the formal-conjectures statement quantifies over subgraphs , the proper ones; it counts with the site. Edge-deletion minimality and proper-subgraph minimality agree for graphs without isolated vertices (an elementary check: Ramsey size-linearity passes to subgraphs, since for , and a graph differing from only by isolated vertices is Ramsey size linear exactly when is, so a minimal graph has no isolated vertices and its proper subgraphs are the subgraphs of its one-edge-deleted graphs). No result about the site's wording is published. The problem's standing judges the corrected Statement.