Erdős problem 533 · problems.science

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, must $G$ contain a set of $\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 statement2 of 6

The contrasting positive result $\delta_3(4) = 0$ of Erdős, Hajnal, Simonovits, Sós, and Szemerédi [EHSSS94]: the $K_4$ analogue of erdos_533 is true. For every $\delta > 0$ there is a $c > 0$ such that for all sufficiently large $n$ , every $K_4$ -free graph $G$ on $n$ vertices with at least $\delta n^2$ edges contains a triangle-free vertex set of size at least $c n$ .

FormalConjectures/ErdosProblems/533.leanErdos533.erdos_533.variants.delta_four_eq_zero7 linesExact file

1∀ (δ : ℝ),2  0 < δ →3    ∃ c,4      0 < c ∧5        ∀ᶠ (n : ℕ) in Filter.atTop,6          ∀ (G : SimpleGraph (Fin n)),7            G.CliqueFree 4 → δ * ↑n ^ 2 ≤ ↑G.edgeFinset.card → ∃ S, c * ↑n ≤ ↑S.card ∧ G.CliqueFreeOn (↑S) 3

SolvedStatement only, no proof

Sources

Search problems.science