Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let and be minimal such that every graph on vertices with minimal degree contains a . Is it true that, for all large , ?
Source: erdosproblems.com/85
No claim settles this problem.
Open. No source found proves or refutes eventual monotonicity of . The size of is known: (the site, from the bounds of Problem 552; Erdős's display (3) of 1996 for ) and (the site). The site's further bound is an off-by-one error: the counting argument behind it bounds , the largest minimum degree of a -free graph on vertices, by , so and , and Erdős's " is easy" in [Er93] is about his own , which is . The bound fails for the page's : the line graph of the Petersen graph is -regular and -free on vertices, so (Boza's values and give the same through the corrected conversion formula). The closest statements concern the equivalent star Ramsey sequence : Boza's Remark 12 records for with no counterexample known for larger , and Chen's Theorem 4 [Ch97] gives for all positive integers (Boza's Lemma 1 quotes it as ). Since is nondecreasing, the corrected conversion gives for , so exactly when for some . The problem is therefore equivalent to for all large , the negation of the question of Burr, Erdős, Faudree, Rousseau and Schelp whether holds infinitely often ([BEFRS89], p. 89, which also asks whether such have density zero; the site records the question under Problem 552). Boza's Remark 12 is that inequality for , which with gives for ; Chen's theorem gives . The search, whose scope the Current assessment records, found nothing more. This is a bounded negative finding, not a certificate of openness.