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

Browse retained paths and inspect the exact material available for this Problem.

6 retained statements2415f78e850a

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ϵ0limnRT3(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.cardG.CliqueFreeOn (↑S) 3
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page