Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be minimal such that every graph on vertices where every set of vertices contains a triangle (a copy of ) must contain a clique on at least vertices. Estimate - in particular, do there exist constants such that
Let be maximal such that every graph on vertices where every set of vertices contains a triangle (a copy of ) must contain a clique on at least vertices. Estimate - in particular, do there exist constants such that
Source: erdosproblems.com/813
No claim settles this problem.
Open, for the corrected Statement; the site labels the problem OPEN. The first inequality is proved: Theorem 1.3 of [BuSu23] (Combinatorica 43 (2023), refereed) gives for every -vertex graph with , so and any works; this is the accepted partial claim on its claim page (Bucić and Sudakov, 2020), whose acceptance evidence is the refereed journal. The second inequality is open: the best upper bound is Erdős and Hajnal's , attested second-hand through [BuSu23] and the site, and Bucić and Sudakov ask whether is the truth (their Question 4.2). No proof, disproof, preprint or proof claim for the second inequality was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness.
As the site words it, is the least threshold that every such graph meets, and every graph meets the threshold (a single vertex is a clique), so for every and the first displayed inequality fails at every ; the question would then have the trivial answer no. The check is the corpus's own. The change replaces the single word "minimal" with "maximal", so that is the largest clique size guaranteed in every such graph, the minimum of the clique number over them. The evidence: Bucić and Sudakov, stating the Erdős--Hajnal question, are "interested in the smallest possible size of in an -vertex graph satisfying " ([BuSu23], p. 2 of arXiv v3), name that quantity (p. 5), and report that Erdős and Hajnal "observed that any graph on vertices with must have " and that some such graph has (p. 2); in the complement these are bounds on the largest clique forced, which is only with "maximal". The site's own commentary credits Erdős and Hajnal with and Bucić and Sudakov with , bounds true only of the corrected form, and keeps the label OPEN, which only the corrected form fits; the word "maximal" is the form the site uses for the neighboring question of Erdős and Hajnal, Problem 804. The poser's own text, Erdős's 1991 paper [Er91], is cited here only through [BuSu23] and the site, so whether the slip is the site's or already in [Er91] is not known. No result about the site's wording is recorded.