Skip to content

Erdős problem 22

Let ϵ>0\epsilon > 0 and let nn be sufficiently large depending on ϵ\epsilon. Is there a graph on nn vertices with at least n2/8n^2/8 many edges which contains no K4K_4, such that the largest independent set has size at most ϵn\epsilon n?

Sources

The source's own material, retained exactly.

5 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

22.lean

Retained formal statement3 of 5

The quantitative strengthening proved by Fox, Loh, and Zhao [FLZ15]: there is a constant C>0C > 0 such that for all sufficiently large nn there exists a K4K_4-free graph on nn vertices with at least n2/8n^2/8 edges whose largest independent set has size at most C⋅(log⁡log⁡n)3/2(log⁡n)1/2⋅n.C \cdot \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}} \cdot n.

FormalConjectures/ErdosProblems/22.leanErdos22.erdos_22.variants.fox_loh_zhao7 linesExact file
∃ C,  0 < C ∧    ∀ᶠ (n : ℕ) in Filter.atTop,      ∃ G,        G.CliqueFree 4 ∧          ↑G.indepNum ≤ C * Real.log (Real.log ↑n) ^ (3 / 2) / Real.log ↑n ^ (1 / 2) * ↑n ∧            ↑n ^ 2 / 8 ≤ ↑G.edgeFinset.card
SolvedStatement only, no proof