Erdős Problem #575 — Bipartite witnesses for graph-family extremal numbers

About 44 years old · traced to

If F\mathcal{F} is a finite set of finite graphs then ex(n;F)\mathrm{ex}(n;\mathcal{F}) is the maximum number of edges a graph on nn vertices can have without containing any subgraphs from F\mathcal{F}. Note that it is trivial that ex(n;F)≤ex(n;G)\mathrm{ex}(n;\mathcal{F})\leq \mathrm{ex}(n;G) for every G∈FG\in\mathcal{F}. Is it true that, for every F\mathcal{F}, if there is a bipartite graph in F\mathcal{F} then there exists some bipartite G∈FG\in\mathcal{F} such that ex(n;G)≪Fex(n;F)?\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.