If F is a finite set of finite graphs then ex(n;F) is the maximum number of edges a graph on n vertices can have without containing any subgraphs from F. Note that it is trivial that ex(n;F)≤ ex(n;G) for every G∈F. Is it true that, for every F, there exists G∈F such that ex(n;G)≪_Fex(n;F)?

Erdős Problem #180 — Extremal numbers for finite graph families

The conjecture asks whether every finite family of connected bipartite graphs containing cycles has an individual member whose extremal number is within a constant factor of the family’s extremal number. The original unrestricted formulation is already false when forests are allowed.

Known results

For the unrestricted formulation, $\mathcal F=\{K_{1,2},2K_2\}$ gives $\operatorname{ex}(n,\mathcal F)=1$ , while each member has extremal number $\Theta(n)$ .
Related boundedness results show that certain cyclic bipartite graphs have controlled auxiliary extremal numbers, but they do not settle the finite-family conjecture.

Purported counterexample

An OpenAI document claims a finite family of connected cyclic bipartite graphs with family extremal number $O(n^{21/16})$ , while every member has extremal number $\Omega(n^{4/3})$ . This would refute the corrected conjecture; the construction was reportedly formalized in Lean, but no independently verified preprint or peer-reviewed proof was found.

Current status (as of March 2026): A counterexample is claimed, but the corrected conjecture remains unverified rather than resolved.

Erdős Problem #180 — Extremal numbers for finite graph families

Primary source

Additional references

Progress summary

Solutions 0