← All problems

Erdős Problem #146 — Extremal numbers of degenerate bipartite graphs

42 years old · traced to

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

References

Progress summary

Refreshed
Open · solution reported

Erdős’s conjecture, posed in 1967, asks whether every fixed bipartite rr-degenerate graph HH satisfies ex⁡(n,H)=O(n2−1/r)\operatorname{ex}(n,H)=O(n^{2-1/r}), including the r=2r=2 case.

Known results

  • Alon, Krivelevich, and Sudakov (2003): ex⁡(n,H)=O(n2−1/(4r))\operatorname{ex}(n,H)=O(n^{2-1/(4r)}) for every fixed bipartite rr-degenerate HH.
  • Alon, Krivelevich, and Sudakov (2003): the conjectured O(n2−1/r)O(n^{2-1/r}) bound holds when one bipartition class has maximum degree at most rr.
  • The conjectured bound is known for broad families, including rr-degenerate blow-ups of trees.
  • For r=2r=2, a C4C_4-free one-sided degree-22 case has a stronger bound O(n3/2−δ)O(n^{3/2-\delta}).

2026 refutation claim

If correct, this refutes the conjecture; the claim is unverified.

Sources

Solutions 0

No solutions have been posted yet.