Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. The statement of Problem 533 is false: there is no function c(δ)>0c(\delta)>0 such that every K5K_5-free graph on nn vertices with at least δn2\delta n^2 edges has, for large nn, a set of c(δ)nc(\delta)n vertices spanning no triangle. Balogh and Lenz prove in Theorem 3 that for t≥2t\ge2 and 2≤ℓ≤t2\le\ell\le t, with u=⌈t/2⌉u=\lceil t/2\rceil, θt(Kt+ℓ)≥12(1−1ℓ)2−u2\theta_t(K_{t+\ell})\ge\frac12(1-\frac1\ell)2^{-u^2}, where θt(H)\theta_t(H) is the limit of RTt(n,H,ϵn)/n2\mathrm{RT}_t(n,H,\epsilon n)/n^2 as n→∞n\to\infty and then ϵ→0\epsilon\to0. At t=3t=3, ℓ=2\ell=2 this is θ3(K5)≥1/64\theta_3(K_5)\ge1/64, the site's δ3(5)≥1/64>0\delta_3(5)\ge1/64>0: for every ϵ>0\epsilon>0 and all large nn there is a K5K_5-free graph on nn vertices with α3≤ϵn\alpha_3\le\epsilon n and at least (1/64−o(1))n2(1/64-o(1))n^2 edges. With δ=1/128\delta=1/128 no c(δ)c(\delta) exists; the deduction is written out on the problem page, together with the normalization θ3(K5)=δ3(5)\theta_3(K_5)=\delta_3(5). The paper poses the question as its Problem 2 and calls the answer its main result; the constructions come from a hypergraph statement built with high-dimensional sphere geometry. Liu, Reiher, Sharifzadeh and Staden later fixed the exact threshold δ3(5)=1/12\delta_3(5)=1/12, recorded on their claim page.

Acceptance. Refereed: Israel Journal of Mathematics 194 (2013), no. 1, 45--68, doi:10.1007/s11856-012-0076-2 (published online 29 June 2012; the Crossref record and the arXiv listing's journal reference of 2026-09-18). The text cited is the arXiv v2 of 22 September 2011; the journal text was not compared. Reviewed: the site's curator, Thomas F. Bloom, credits the disproof to Balogh and Lenz in the problem's commentary (page labeled DISPROVED (LEAN), last edited 27 January 2026, accessed 2026-09-18), and the curator's thread comment of 27 January 2026 says that δ>0\delta>0 appears to have been proved earlier by Balogh and Lenz; the proof-claim tab is empty. Not formalized: the Lean file Erdos533.lean in plby/lean-proofs, which formal-conjectures names as the formal proof of erdos_533 (; absent from the commit at main on 2026-09-18), lists Balogh and Lenz among its informal authors, with Codex and GPT-5.6 Sol as formal authors, but builds the Liu--Reiher--Sharifzadeh--Staden construction and not Theorem 3, so it is linked from their claim page; the corpus has not built it. Proof coverage is statements only: Theorem 3, Corollary 4 and the p. 4 displays were checked, and no proof was read. The claim rests on the source card balogh_2013_ramsey_turan_numbers_graphs_hypergraphs and consumes no page of this wiki.