Erdős Problem #146 — Extremal numbers of degenerate bipartite graphs
If is bipartite and is -degenerate, that is, every induced subgraph of has minimum degree , then
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Refreshed
Open · solution reported
Erdős’s conjecture, posed in 1967, asks whether every fixed bipartite -degenerate graph satisfies , including the case.
Known results
- Alon, Krivelevich, and Sudakov (2003): for every fixed bipartite -degenerate .
- Alon, Krivelevich, and Sudakov (2003): the conjectured bound holds when one bipartition class has maximum degree at most .
- The conjectured bound is known for broad families, including -degenerate blow-ups of trees.
- For , a -free one-sided degree- case has a stronger bound .
2026 refutation claim
If correct, this refutes the conjecture; the claim is unverified.
Solutions 0
No solutions have been posted yet.