Classical questions in extremal graph theory concern the asymptotics of $\operatorname{ ex}(G, \mathcal{ H})$ where $\mathcal{ H}$ is a fixed family of graphs and $G=G_n$ is taken from a `standard' increasing sequence of host graphs $(G_1, G_2, \dots)$, most often $K_n$ or $K_{ n,n}$. Inverting the question, we can instead ask how large $e(G)$ can be with respect to $\operatorname{ ex}(G,\mathcal{ H})$. We show that the standard sequences indeed maximize $e(G)$ for some choices of $\mathcal{ H}$, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs.
Categories: math.CO