Problem 615

Does there exist some constant $c>0$ such that if $G$ is a graph with $n$ vertices and $\geq (1/8-c)n^2$ edges then $G$ must contain either a $K_4$ or an independent set on at least $n/\log n$ vertices?

Source: erdosproblems.com/615

Graph theory
Ramsey theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

The site labels the problem DISPROVED (LEAN). The status-defining source is Theorem 1.10 of Fox, Loh and Zhao, The critical window for the classical Ramsey-Turán problem, Combinatorica 35 (2015), no. 4, 435--476 (refereed; cited from the arXiv v3): if $m=e^{-o((\log n/\log\log n)^{1/2})}n$ then $\mathbf{RT}(n,K_4,m)\ge(1/8-o(1))n^2$ ; the paper presents it as settling in the negative the question those five authors posed, its Problem 1.4 (the sentence is quoted in the Current assessment). The one-line check that $m=n/\log n$ lies in the theorem's range is written in the Current assessment and named there as authored. So for every $c>0$ and all large $n$ some $K_4$ -free graph on $n$ vertices has at least $(1/8-c)n^2$ edges and no independent set of $n/\log n$ vertices; the answer to the question is no. The site's curator credits Fox, Loh and Zhao with the negative answer. The claim page Fox, Loh and Zhao 2012 records the refereed disproof with its postings and acceptance evidence and carries, as a formalization link, the Lean file behind the site's suffix, linked and not built; the frontmatter standing derives from that page.

FLZ15: Fox, J., Loh, P.-S. and Zhao, Y., The critical window for the classical Ramsey-Turán problem. Combinatorica 35 (2015), no. 4, 435--476, doi:10.1007/s00493-014-3025-3 (published online 22 October 2014; Crossref record and the arXiv listing's journal reference accessed); arXiv:1208.3276v3 (23 September 2014), the edition cited; the journal text was not compared. Problem 1.4, p. 3; Theorem 1.10 and the paragraph before it, p. 4; Theorem 1.11, p. 5. Library home: Fox, Loh and Zhao 2015.
EHSSS93: Erdős, P., Hajnal, A., Simonovits, M., Sós, V. T. and Szemerédi, E., Turán-Ramsey theorems and simple asymptotically extremal structures. Combinatorica 13 (1993), no. 1, 31--56 (received October 31, 1989), doi:10.1007/BF01202788 (Crossref record accessed). Problem 4, p. 54; displays (7)--(8), p. 36. Library home: Erdős et al. 1993.
Su03: Sudakov, B., A few remarks on Ramsey-Turán-type problems. J. Combin. Theory Ser. B 88 (2003), no. 1, 99--106 (received 21 August 2001), doi:10.1016/S0095-8956(02)00038-2 (Crossref record accessed). Problem 1.1, p. 100; Theorem 3.1, p. 102; the $K_4$ corollary, p. 103. Library home: Sudakov 2003.
EHSS83: Erdős, P., Hajnal, A., Sós, V. T. and Szemerédi, E., More results on Ramsey-Turán type problems. Combinatorica 3 (1983), no. 1, 69--81, doi:10.1007/BF02579342. Displays (1.5)--(1.6), p. 71: the threshold, not the question. Library home: Erdős et al. 1983.
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley (1991), 397--406. A site source key; not held (past the Rényi archive's 1989 cutoff); the problem's passage there has not been seen.
BoEr76: Bollobás, B. and Erdős, P., On a Ramsey-Turán type problem. J. Combinatorial Theory Ser. B 21 (1976), 166--168. The construction behind the threshold; not consumed on this page (its card and result pages are on Problem 22).

Problem 615

Status

Proof claims

Discussion