Erdős problem 1008 · problems.science

Does every graph with $m$ edges contain a subgraph with $\gg m^{2/3}$ edges which contains no $C_4$ ?

Sources

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

4 retained statements2415f78e850a

FormalConjectures/ErdosProblems/

1008.lean

Retained formal statement2 of 4

Folkman's counterexample $K_{n,n^2}$ , which has $n^3$ edges, and yet every subgraph with $>n^2+\binom{n}{2}$ edges contains a $C_4$ .

FormalConjectures/ErdosProblems/1008.leanErdos1008.erdos_1008.variants.folkman4 linesExact file

1∀ (n : ℕ),2  (completeBipartiteGraph (Fin n) (Fin (n ^ 2))).edgeSet.ncard = n ^ 3 ∧3    ∀ H ≤ completeBipartiteGraph (Fin n) (Fin (n ^ 2)),4      n ^ 2 + n.choose 2 < H.edgeSet.ncard → (SimpleGraph.cycleGraph 4).IsContained H

SolvedStatement only, no proof

Sources

Search problems.science