Inverting the Turán Problem

Abstract

Classical questions in extremal graph theory concern the asymptotics of $\mathrm{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 $\mathrm{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.

arXiv comment28 pages, 5 figures