Skip to content

Erdős problem 533

Let δ>0\delta > 0. If nn is sufficiently large and GG is a graph on nn vertices with no K5K_5 and at least δn2\delta n^2 edges, must GG contain a set of ≫δn\gg_\delta n vertices spanning no triangle?

Sources

The source's own material, retained exactly.

6 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

533.lean

Retained formal statement1 of 6

Let δ>0\delta > 0. If nn is sufficiently large and GG is a graph on nn vertices with no K5K_5 and at least δn2\delta n^2 edges, must GG contain a set of ≫δn\gg_\delta n vertices spanning no triangle?

Equivalently, writing RT3(n,K5,m)\mathrm{RT}_3(n, K_5, m) for the maximum number of edges of a K5K_5-free graph on nn vertices in which every triangle-free vertex set has fewer than mm vertices (the *triangle Ramsey–Turán number*), is δ3(5)=lim⁡ϵ→0lim⁡n→∞RT3(n,K5,ϵn)n2=0?\delta_3(5) = \lim_{\epsilon \to 0} \lim_{n \to \infty} \frac{\mathrm{RT}_3(n, K_5, \epsilon n)}{n^2} = 0?

This is a problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi [EHSSS94], who proved δ3(5)≤1/12\delta_3(5) \leq 1/12 and the analogous δ3(4)=0\delta_3(4) = 0, and observed δ3(7)≥1/4\delta_3(7) \geq 1/4 via a construction of Erdős and Rogers [ErRo62].

The answer is no: Balogh and Lenz [BaLe13] disproved it by showing δ3(5)>0\delta_3(5) > 0, and the exact value δ3(5)=1/12\delta_3(5) = 1/12 was determined by the matching lower-bound construction of Liu, Reiher, Sharifzadeh, and Staden [LRSS21] (see erdos_533.variants.lrss_lower).

FormalConjectures/ErdosProblems/533.leanErdos533.erdos_5338 linesExact file
False ↔  ∀ (δ : ℝ),    0 < δ →      ∃ c,        0 < c ∧          ∀ᶠ (n : ℕ) in Filter.atTop,            ∀ (G : SimpleGraph (Fin n)),              G.CliqueFree 5 → δ * ↑n ^ 2 ≤ ↑G.edgeFinset.card → ∃ S, c * ↑n ≤ ↑S.card ∧ G.CliqueFreeOn (↑S) 3
SolvedStatement only, no proof