Open-access mathematical research insights
About Contact
Home / Erdos Problems / Problem #575

Problem #575: If $\mathcal{F}$ is a finite set of finite graphs then...

If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have...

Problem Statement

If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs from $\mathcal{F}$. Note that it is trivial that $\mathrm{ex}(n;\mathcal{F})\leq \mathrm{ex}(n;G)$ for every $G\in\mathcal{F}$.

Is it true that, for every $\mathcal{F}$, if there is a bipartite graph in $\mathcal{F}$ then there exists some bipartite $G\in\mathcal{F}$ such that\[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]
Categories: Graph Theory Turan Number

Progress

A problem of Erdős and Simonovits.

See also [180] and the entry in the graphs problem collection.

Source: erdosproblems.com/575 | Last verified: January 15, 2026

Stay Updated

Get weekly digests of new research insights delivered to your inbox.