Problem 533

Let $\delta>0$ . If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_5$ and at least $\delta n^2$ edges then $G$ contains a set of $\gg_\delta n$ vertices containing no triangle.

Source: erdosproblems.com/533

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN), the site's label on 2026-09-18 (page last edited 27 January 2026). The status-defining source is Theorem 3 of Balogh and Lenz (Israel J. Math. 194 (2013), no. 1, 45--68, refereed; cited from the arXiv v2): for $t\ge2$ and $2\le\ell\le t$ , with $u=\lceil t/2\rceil$ , $\theta_t(K_{t+\ell})\ge\frac12(1-\frac1\ell)2^{-u^2}$ ; at $t=3$ , $\ell=2$ this is $\theta_3(K_5)\ge1/64$ , the value the paper displays after its Problem 5. So $\delta_3(5)\ge1/64>0$ : for every $\epsilon>0$ and all large $n$ there are $K_5$ -free graphs on $n$ vertices with $\alpha_3\le\epsilon n$ and at least $(1/64-o(1))n^2$ edges, and the statement fails for $\delta=1/128$ (the deduction is written out below). The exact threshold is $\delta_3(5)=1/12$ : the upper bound $\delta_3(5)\le1/12$ is the origin paper's (not held; stated first-hand by four of its authors in 1983 and attested by [BaLe13] and [LRSS21]; an accepted partial claim on the Erdős–Hajnal–Simonovits–Sós–Szemerédi claim page (1994)), and the matching construction is Theorem 1.1 of Liu, Reiher, Sharifzadeh and Staden (Corollary 1.2 and Theorem 1.4: $\varrho_3(5)=1/6$ ; J. Eur. Math. Soc., Crossref record of 20 October 2025; cited from the arXiv v2 of 18 August 2025). The two disproofs are recorded as accepted full claims, refereed and credited by the site, on the Balogh–Lenz claim page (2011) and the Liu–Reiher–Sharifzadeh–Staden claim page (2021); the public Lean proof of the disproof, recorded under Formalization, is linked from the second and is not counted as formalized evidence, since the corpus has not built it.

BaLe13: Balogh, J. and Lenz, J., On the Ramsey-Turán numbers of graphs and hypergraphs. Israel J. Math. 194 (2013), no. 1, 45--68, doi:10.1007/s11856-012-0076-2 (published online 29 June 2012; Crossref record and the arXiv listing's journal reference); arXiv:1109.4428v2 (22 September 2011); the journal text was not compared. The definitions, p. 2; Problems 1--2 and Theorem 3, p. 3; Corollary 4, Problem 5 and the display $1/64\le\theta_3(K_5)$ , p. 4; the open problems, p. 18. Library home: Balogh 2013.
LRSS21: Liu, H., Reiher, C., Sharifzadeh, M. and Staden, K., Geometric constructions for Ramsey-Turán theory. arXiv:2103.10423v2 (18 August 2025, "to appear in JEMS"); Journal of the European Mathematical Society, vol. 28, no. 1, 79--112, doi:10.4171/jems/1712 (Crossref record, issued 20 October 2025; the journal text is not held). The definition of $\varrho_p(q)$ , p. 2; the state of the art before the paper, p. 3; Theorem 1.1 and Corollary 1.2, p. 4; Theorem 1.4, p. 5; Problem C, p. 6. Library home: Liu et al. 2021.
ErRo62: Erdős, P. and Rogers, C. A., The construction of certain graphs. Canad. J. Math. 14 (1962), 702--707, doi:10.4153/CJM-1962-060-4 (received October 26, 1961). The Section 3 Theorem, p. 704. Library home: Erdős and Rogers 1962 (a Rényi archive scan).
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. Section 6, p. 80: the $K_3$ -independence variant, the bound $\frac1{12}n^2(1+o(1))$ announced without proof, and the question whether it is best possible. Not a site key for this problem. Library home: Erdős et al. 1983 (a Rényi archive scan).
EHSSS94: Erdős, P., Hajnal, A., Simonovits, M., Sós, V. T. and Szemerédi, E., Turán-Ramsey theorems and $K_p$ -independence numbers. Combin. Probab. Comput. 3 (1994), no. 3, 297--325, doi:10.1017/S0963548300001218 (the site's reference text of 2026-09-18; Crossref record; a reprint in Combinatorics, Geometry and Probability, Cambridge Univ. Press (1997), 253--282, doi:10.1017/CBO9780511662034.025, is also on record). The site cites p. 306. Not held: one request to the DOI resolved to the publisher's abstract page ("Get access"), and no open copy was located. Its bounds are quoted on pp. 3--4 of [BaLe13] and pp. 2--3 of [LRSS21], and the thread cites its Theorem 2.11.
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397--406. Site source key; not held (after the Rényi archive's 1989 cutoff).
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), 31--56. A source of Problem 615; a different paper from the origin [EHSSS94], not consumed by this page. Library home: Erdős et al. 1993.

Problem 533

Status

Proof claims

Discussion