Erdős problem 579 · problems.science

Let $\delta > 0$ . If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_{2,2,2}$ (the octahedron) and at least $\delta n^2$ edges, must $G$ contain an independent set of size $\gg_\delta n$ ?

No current result

No reviewed Result is current in Vela Mathematics Program. Retained source material is shown below.

Retained declaration

FormalConjectures/ErdosProblems/579.lean

Formal Conjectures

FormalConjectures/ErdosProblems/579.leanErdos579.erdos_5798 linesExact file

1True ↔2  ∀ (δ : ℝ),3    0 < δ →4      ∃ c,5        0 < c ∧6          ∀ᶠ (n : ℕ) in Filter.atTop,7            ∀ (G : SimpleGraph (Fin n)),8              Erdos579.octahedron.Free G → δ * ↑n ^ 2 ≤ ↑G.edgeFinset.card → c * ↑n ≤ ↑G.indepNum

OpenStatement only, no proof

Continue

Start a contribution Browse the source files Open the collection entry

No current result

Continue

Search problems.science