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 statement4 of 4

Originally asked by Bollobás and Erdős in 'a colloquium on graph theory at Tihany' with $m^{2/3}$ replaced by $m^{3/4}$ . Folkman showed this is false with the 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.three_quarters4 linesExact file

1False ↔2  ∃ c > 0,3    ∀ (V : Type) [Fintype V] (G : SimpleGraph V),4      ∃ H ≤ G, (SimpleGraph.cycleGraph 4).Free H ∧ c * ↑G.edgeSet.ncard ^ (3 / 4) ≤ ↑H.edgeSet.ncard

SolvedStatement only, no proof

Sources

Search problems.science