Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be fixed integers. We define to be the largest such that any graph on vertices where every set of vertices spans at least edges must contain a complete graph on vertices. Is
a strictly increasing function of for ?
Source: erdosproblems.com/667
No claim settles this problem.
The site labels the problem OPEN, with the note that no finite computation can settle it, and no claim about it has been found, so the problem is open. The source records the bounds the site repeats: for the condition says that has no independent set of size , so is governed by Ramsey numbers and ; for the complement of has all components of order below , so has a clique of order at least and (a three-line argument printed in the source); and, without proof or reference, "we have shown that , so ". No source found addresses strict monotonicity for any , and the paper behind the last bound was not identified. The last bound is disputed: a comment in the site's thread (18 April 2026) gives an elementary argument, recomputed below, that for every , and the elementary arguments recorded below show that the bound is incompatible with the source's own conjecture for every , that it fails for odd as well, and that the printed inequality is false for every . The search dated 2026-09-18 UTC, whose scope the Current assessment records, found no proof, disproof, preprint or proof claim for the question. This is a bounded negative finding, not a certificate of openness.