Erdős problem 146 · problems.science

If $H$ is bipartite and $r$ -degenerate, is $\mathrm{ex}(n;H) \ll n^{2-1/r}$ (a $500 Erdős-Simonovits prize conjecture)? A counterexample refutes the degeneracy conjecture.

Sources

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

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

146.lean

Retained formal statement1 of 2

If $H$ is bipartite and is $r$ -degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$ , then $\mathrm{ex}(n;H) \ll n^{2-1/r}.$

The answer is no. OpenAI [OpenAI26] give a connected bipartite 2-degenerate H and constants c, ε > 0 with $\mathrm{ex}(n;H)\geq cn^{3/2+\epsilon}$ for all large n, which exceeds the conjectured $n^{2-1/2}=n^{3/2}$ . See erdos_146.variants.two_degenerate_counterexample.

FormalConjectures/ErdosProblems/146.leanErdos146.erdos_1466 linesExact file

1False ↔2  ∀ (r q : ℕ) (H : SimpleGraph (Fin q)),3    0 < r →4      H.IsBipartite →5        Erdos146.IsDegenerate r H →6          (fun n => ↑(SimpleGraph.extremalNumber n H)) =O[Filter.atTop] fun n => ↑n ^ (2 - 1 / ↑r)

SolvedStatement only, no proof

Sources

Search problems.science