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 statement5 of 6

The matching lower bound δ3(5)≥1/12\delta_3(5) \geq 1/12, from the construction of Liu, Reiher, Sharifzadeh, and Staden [LRSS21] (improving the earlier δ3(5)>0\delta_3(5) > 0 of Balogh and Lenz [BaLe13]): for every ϵ,δ>0\epsilon, \delta > 0 and all sufficiently large nn there is a K5K_5-free graph GG on nn vertices in which every triangle-free vertex set has at most δn\delta n vertices, yet which has at least (1/12−ϵ)n2(1/12 - \epsilon)n^2 edges. In particular this refutes erdos_533.

FormalConjectures/ErdosProblems/533.leanErdos533.erdos_533.variants.lrss_lower8 linesExact file
∀ (ε δ : ℝ),  0 < ε →    0 < δ →      ∀ᶠ (n : ℕ) in Filter.atTop,        ∃ G,          G.CliqueFree 5 ∧            (∀ (S : Finset (Fin n)), G.CliqueFreeOn (↑S) 3 → ↑S.card ≤ δ * ↑n) ∧              (1 / 12 - ε) * ↑n ^ 2 ≤ ↑G.edgeFinset.card
SolvedStatement only, no proof